| Title | : | How (not) to prove circuit lower bounds. |
| Speaker | : | Vaibhav Krishan (IMSc Chennai) |
| Details | : | Tue, Jan 28, 2025 4:00 PM, @ Turing Hall (SSB 334) |
| Abstract | : | Proving lower bounds for Boolean circuits is a notoriously difficult task. A Boolean circuit is a natural model of computation, using logical primitives, such as the AND, OR and NOT functions, to compute a certain Boolean function. Naturally, to efficiently compute a function is to say that a small size circuit computes it. Circuits of large enough size can compute all functions, and they can even compute certain uncomputable functions with very small size. The goal is to prove that any circuit computing a specific hard function, such as checking the existence of a hamiltonian cycle in a graph, must have large size. Proving this would resolve the P vs NP question, a million-dollar-prize open problem in computer science.
Despite more than half a century of work, it is widely agreed upon that the best lower bounds for the size required are "pathetic". Naturally, researchers started looking at restrictions of Boolean circuits, such as those with constant-depth, essentially equivalent to constant-time massively parallel algorithms with sufficiently many processors. Here, there was considerable early success, with the works of Hastad (STOC 1986), Razborov (Math. Notes of the Academy of Sciences of the USSR 1987), and Smolensky (STOC 1987). Progress stalled thereafter, until a breakthrough work of Williams (CCC 2011). Williams proved the existence of functions, albeit from a very powerful class, that require large ACC0 circuits to compute. Note that no strong lower bounds were known against ACC0 circuits prior to this work. The goal of our work is to prove a much stronger statement, an almost 40 years old conjecture by Barrington. Barrington conjectured that any ACC0 circuit computing the voting function (aka the majority function) must have large size. This conjecture is still wide open, with only a handful of proposed techniques towards resolving it. In this talk, we will look at certain approaches towards this conjecture. We will see why several of our attempts, based on natural approaches, were doomed to fail. Our failures, as for Edison, may have helped us find the right approach for our main problem. Hence, we will discuss our proposed approach, based on linear programming, polyhedral geometry, inclusion matrices, and the geometry of numbers. We will briefly consider our progress using this approach. Our work naturally leads to a host of open directions, and related open problems, appearing at the end of the talk. This is a joint work with S. Vishwanathan at CSE, IITB. Speaker Bio: Vaibhav is a postdoc at IMSc, Chennai. He obtained his PhD from CSE, IITB, under the guidance of Prof. Nutan Limaye and Prof. Sundar Vishwanathan. |