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 aspects of Machine Learning. 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.)
Jeff Edmonds
Hardness of Function Composition for Semantic Read once Branching Programs
Jeff Edmonds and Toniann Pitassi
in CCC 2018, slides
Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs
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)
James Martens

Some Great Reads

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

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