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.

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 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 |

Francis Crick in 89.

You and Your Research by Richard Hamming.

Office:

University of Toronto

Department of Computer Science