Frontiers in Boolean Circuit Lower Bounds

Title of the Talk: FHE advances and HW acceleration opportunities
Speakers: Vaibhav Krishan (IMSc, Chennai)
Host Faculty: Dr.Nitin Saurabh
Date: Nov 12, 2025
Time: 2:30 pm to 3:30 pm
Venue: CS - LH-01

Abstract: Boolean circuits provide a combinatorial representation of computation, where the number of gates (the size) represents running time, and the number of layers (the depth) capture parallel running time. They form a framework for answering fundamental questions such as P vs NP: proving that some NP problem requires circuits of superpolynomial size would separate P from NP.

With limited progress on this question for general circuits, early breakthroughs focused on restricted circuit classes. Håstad (STOC 86) proved that constant-depth circuits with AND, OR, and NOT gates require exponential size to compute the parity function (which determines whether the sum of inputs is even or odd). Razborov (Matematicheskie Zametki 87) and, independently, Smolensky (STOC `87), extended this to circuits augmented with parity or modular gates (for prime moduli), showing that such circuits require exponential size to compute the majority function (which determines whether the sum of inputs is at least half their number).

Following these foundational results, research has advanced along two principal directions, though further progress has become increasingly challenging. In this talk, I will present some of my work contributing new advances at the frontier of both directions. _____ Part I: Threshold Circuits.

The first part of the talk will focus on constant-depth threshold circuits, circuits that can use majority gates, or more generally, threshold gates. Threshold gates can be seen as a simple abstraction for neurons, and threshold circuits were among the earliest models studied to understand the computational power of neural networks. These circuits are quite powerful; for instance, they can efficiently implement integer arithmetic operations such as exponentiation and square root.

In joint work with Bajpai, Kush, Limaye, and Srinivasan, Algorithmica 21, we study a generalization of threshold circuits, called polynomial threshold circuits, that use polynomial threshold gates. A polynomial threshold gate outputs a Boolean value based on the sign of a polynomial evaluated over the inputs. We design an algorithm to count the number of assignments on which a polynomial threshold circuit outputs 1. For any constant depth, our algorithm runs faster-than-brute-force when the circuit size is slightly superlinear and the degree of each gate is bounded by a constant. Prior to our work, no such algorithm was known even for a single polynomial threshold gate, except in the special case of degree 2. Faster-than-brute-force algorithms are known to imply circuit lower bounds (Williams, JACM 14), although the particular lower bounds implied by our work were already established by Kane, Kabanets, and Lu (STOC `17).

Our work builds on a long line of research initiated by Impagliazzo, Paturi, and Saks (SIAM J. Comput. 97), who proved a tight lower bound for threshold circuits with a slightly superlinear number of wires computing the parity function. Their core idea, simplification of threshold circuits under random partial assignments, has inspired a series of influential results, leading to average-case lower bounds and satisfiability algorithms (Chen, Santhanam, and Srinivasan, Theory Comput. 18), as well as pseudorandom generator constructions (Hatami, Hoza, Tal, and Tell, FOCS 22). Even seemingly small improvements to these results could lead to major breakthroughs in circuit complexity (Chen and Tell, STOC 19), marking a central frontier for the community. _____ Part II: Modular Circuits

The second part of my talk will focus on circuits with modular gates for general (not necessarily prime) moduli. Here, in a joint work with S. Vishwanathan, we develop an approach toward resolving a long-standing conjecture (Barrington, JCSS 89), that constant-depth circuits with modular gates (the modulus does not grow with input size) require superpolynomial size to compute the majority function. The classical lower-bound techniques of Håstad and Razborov-Smolensky fail to extend to this setting, while the algorithms-to-lower bounds framework of Williams (JACM 14) does not apply to simple functions such as majority, making new ideas necessary.

Various approaches to this conjecture have been proposed over the years. In earlier work (Krishan, CSR 2019), I showed that torus polynomials provide the most refined framework for tackling this problem. Torus polynomials were introduced by Bhrushundi, Hosseini, Lovett, and Rao (ITCS `19) for proving lower bounds against such modular circuits. Using torus polynomials, we translate the lower bound conjecture to the task of finding feasible solutions to an infinite family of linear programs. This reformulation allows for incremental progress, by finding solutions for progressively larger sets from the family.

We find solutions for almost all of these programs, leaving only a finite set unresolved. Finding feasible solutions for the remaining cases would lead to a resolution of the conjecture. To make this task more tractable, we show that the family of programs has far fewer degrees of freedom than initially expected, and we describe a potential set of feasible solutions for some of the remaining cases. I will conclude the talk with open problems and directions for future progress.

Bio: Vaibhav is a postdoctoral researcher at The Institute of Mathematical Sciences (IMSc), Chennai. He completed his Ph.D. at IIT Bombay under the supervision of Prof. Sundar Vishwanathan and Prof. Nutan Limaye. Before beginning his Ph.D., he worked as a quantitative researcher and a data scientist for four years.