Circuit Lower Bounds

Rahul Santhanam, Postdoctoral Researcher
Department of Computer Science
University of Toronto

Abstract

A Boolean circuit lower bound for a computational problem states that the problem cannot be solved by logical circuits (composed of AND, OR and NOT gates) of a certain size. Proving superlinear Boolean circuit lower bounds for explicit problems is one of the fundamental questions in theoretical computer science. This question is related to the celebrated P vs NP question, and also has connections with cryptography and the theory of machine learning. I will first give background and motivation for this question. Then I will talk about some recent results of mine that make progress on this question from a variety of angles.

Speaker Bio

Rahul Santhanam is currently a postdoctoral researcher in the Department of Computer Science at the University of Toronto. He received a Bachelors degree in Computer Science from the Indian Instute of Technology, Chennai in 1998, a Masters degree in Computer Science from the University of Chicago in 2001, and a PhD degree in Computer Science from the University of Chicago in 2005. From September 2005 to Janaury 2007, he was a postdoctoral associate at Simon Fraser University. His main research interest is in computational complexity theory, with side interests in cryptography, theory of machine learning and theory of networks.