| Title | : | New Circuit Lower and Upper Bounds via Combinatorial Arguments |
| Speaker | : | Balagopal Komarath (IITM) |
| Details | : | Tue, 24 Feb, 2015 3:00 PM @ BSB 361 |
| Abstract: | : | We study the space complexity of the Tree Evaluation Problem (TEP).
This problem was introduced by Cook et. al. to separate the complexity
classes P (polynomial-time) and L (logspace). The approach suggested
is to consider models of computation that captures larger and larger
classes of algorithms solving TEP and prove lower bounds against them.
We introduce a restricted form of the well-studied branching program
model, called Bitwise Independent Non-deterministic Thrifty Branching
Programs (BINTBP), and show that BINTBPs capture the most space
etcient algorithms used for solving TEP. We then prove tight lower
bounds for BINTBPs essentially showing that currently known algorithms
are the best possible ones on the BINTBP model.
We also study circuit complexity of deciding graph properties (such as Perfect Matching, 2-colourability etc.) on constant-width grid graphs. The objective is to design polynomial-size constant-depth circuits for these problems. For example, adding two n-bit numbers using carry-lookahead logic only takes polynomial (in n) number of gates and constant depth. We show that deciding 2-colourability, existence of perfect matching and deciding if vertex/edge-disjoint paths exist between two designated vertices in constant-width grid graphs can be done using polynomial-size constant depth circuits. |
