me

Venkatesh Medabalimi

I'm a recent PhD graduate of the University of Toronto. My thesis was done under the surpevision of Prof. Stephen A.Cook. My research interests are primarily in Computational Complexity and Machine Learning. I am also very curious about the nature of computation in the brain. Before coming to Toronto, I did my undergrad in Computer Science with a minor in Mathematics at IIT Madras.

A longstanding open problem in complexity theory is whether the class Polytime (P) is the same as LogSpace (L) or nondeterministic LogSpace (NL). In my thesis, we explore this problem by studying time/space tradeoffs for problems in P. As in, for some natural problem in P, does the addition of a space restriction prevent a polynomial time solution ? We show this is indeed the case for certain restricted models of computation. One promising approach to show a separation is via proving space lower bounds against composition (See [1] or [2] ). We also show such a conjecture about function composition indeed holds true in these restricted models.

Papers and Manuscripts

Lower bounds and Space Efficient Algorithms for Composed functions via Communication Analogues
(In preparation.)
with Jeff Edmonds
Hardness of Function Composition for Semantic Read once Branching Programs
with Jeff Edmonds and Toniann Pitassi
in CCC 2018, slides
Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs
with Jeff Edmonds, Toniann Pitassi and Stephen Cook
in ICALP 2016, slides
Here's a compact Exposition of this result by Stasys Jukna
On the Expressive Efficiency of Sum Product Networks (a.k.a SPNs)
with James Martens

Some Great Reads

Barrington in 87.
Francis Crick in 89.
You and Your Research by Richard Hamming.

Miscellaneous

Narrow Nets with Top-down Attention are Universal (yields a much simpler proof of this result)
Convergence Dynamics in Feudal Networks(Hierarchical Reinforcement Learning)
On Learning to Compose

Contact info

Email: venkatm at cs dot toronto dot edu

Office: SF4301D, Department of Computer Science, Sanford Felming Building, King's College Road, Toronto
University of Toronto
Department of Computer Science