The class ACC⁰ consists of Boolean functions that can be computed by constant-depth circuits of polynomial size with AND, NOT and MOD_m gates, where m is a natural number. At the frontier of our understanding lies a widely believed conjecture asserting that MAJORITY does not belong to ACC⁰. A few years ago, Bhrushundi, Hosseini, Lovett and Rao (ITCS 2019) introduced torus polynomial approximations as an approach towards this conjecture. Torus polynomials approximate Boolean functions when the fractional part of their value on Boolean points is close to half the value of the function. They reduced the conjecture that MAJORITY ∉ ACC⁰ to a conjecture concerning the non-existence of low degree torus polynomials that approximate MAJORITY. We reduce the non-existence problem further, to a statement about finding feasible solutions for an infinite family of linear programs. The main advantage of this statement is that it allows for incremental progress, which means finding feasible solutions for successively larger collections of these programs. As an immediate first step, we find feasible solutions for a large class of these linear programs, leaving only a finite set for further consideration. Our method is inspired by the method of dual polynomials, which is used to study the approximate degree of Boolean functions. Using our method, we also propose a way to progress further. We prove several additional key results with the same method, which include: - A lower bound on the degree of symmetric torus polynomials that approximate the AND function. As a consequence, we get a separation that symmetric torus polynomials are weaker than their asymmetric counterparts. - An error-degree trade-off for symmetric torus polynomials approximating the MAJORITY function, strengthening the corresponding result of Bhrushundi, Hosseini, Lovett and Rao (ITCS 2019). - The first lower bounds against torus polynomials approximating AND, showcasing the power of the machinery we develop. This lower bound nearly matches the corresponding upper bound. Hence, we get an almost complete characterization of the torus polynomial approximation degree of AND. - Lower bounds against asymmetric torus polynomials approximating MAJORITY, or AND, in the very low error regime. This partially answers a question posed in Bhrushundi, Hosseini, Lovett and Rao (ITCS 2019) about error-reduction for torus polynomials.

We explore the torus polynomial approximation based approach towards a long-standing question: whether AND can be computed by CC⁰ circuits - the class of constant-depth polynomial size circuits containing MOD_m gates for some natural number m. Bhrushundi, Hosseini, Lovett and Rao (ITCS 2019) introduced torus polynomial approximations as an approach for proving lower bounds against ACC⁰ - a class containing CC⁰ where the circuits are also allowed AND, OR and NOT gates. We show how lower bounds for torus polynomials approximating AND can be used to make progress on this question. Using lower bounds on the degree of symmetric torus polynomials approximating AND, proved by Krishan and Vishwanathan (ITCS 2026), we prove size lower bounds for symmetric CC⁰-circuits computing AND. More precisely, we prove that any depth h symmetric CC⁰ circuit requires 2^Ω̃(n^{1/O(h)}) size to compute AND. A key ingredient in our proof is an argument that we can construct symmetric torus polynomials to approximate symmetric CC⁰ circuits. Our construction exhibits an explicit correspondence between the symmetry of the circuit and that of the polynomial. Using this, we also establish lower bounds for weaker notions of circuit symmetry. Lower bounds for symmetric CC⁰ circuits were also independently established by Pago (ICALP 2026) using different techniques. In the asymmetric regime, we establish degree upper bounds for depth three circuits of the form MOD_p∘MOD_m∘AND_O(1) where m = pq is a semiprime. This circuit class is a special case of the constant degree hypothesis, introduced by Barrington, Straubing and Thérien (Information and Computation, 1990), where m could be an arbitrary composite number. We argue that improved lower bounds for asymmetric torus polynomials approximating AND imply size lower bounds for semiprime m and hence progress on the constant-degree hypothesis.

For a quantified Boolean formula (QBF), the problem of computing the number of winning strategies is known as the #QBF problem. This problem is considered harder than the analogous #SAT problem. Recently, important proof systems for QBFs and #SAT have been studied. By extending the ideas from both fields, we show that it is possible to design proof systems for #QBF. Such proof systems are important not only for advancing the theory of #QBF but also for certifying and designing better #QBF solvers, an area that is still in its early stages. In this paper, we explore #QBF proof systems to count the number of Skolem functions. In addition to a naive system, we study #QBF systems based on the ∀-expansion rule of QBFs. We observe that these systems have inherent structural weaknesses that lead to lower bounds. As an alternative, we propose a #QBF proof system that we call Q-MICE, which consists of sound inference rules for computing and certifying the #QBF solution, similar to the line-based #SAT proof system MICE. To demonstrate the strength of Q-MICE, we present various upper bounds, such as the quantified version of the propositional XOR-PAIRS formula, which are known to be hard for MICE. Consequently, we also separate Q-MICE from ∀-expansion based #QBF proof systems.

Proving super-polynomial size lower bounds for $\textsf{TC}^0$, the class of constant-depth, polynomial-size circuits of Majority gates, is a notorious open problem in complexity theory. A major frontier is to prove that $\textsf{NEXP}$ does not have poly-size $\textsf{THR} \circ \textsf{THR}$ circuit (depth-two circuits with linear threshold gates). In recent years, R.~Williams proposed a program to prove circuit lower bounds via improved algorithms. In this paper, following Williams' framework, we show that the above frontier question can be resolved by devising slightly faster algorithms for several fundamental problems: 1. Shaving Logs for $\textsf{$\ell_2$-Furthest-Pair}$. An $n^2 \textrm{poly}(d) / \log^{ω(1)} n$ time algorithm for $\textsf{$\ell_2$-Furthest-Pair}$ in $\mathbb{R}^d$ for polylogarithmic $d$ implies $\textsf{NEXP}$ has no polynomial size $\textsf{THR} \circ \textsf{THR}$ circuits. The same holds for Hopcroft's problem, $\textsf{Bichrom.-$\ell_2$-Closest-Pair}$ and Integer $\textsf{Max-IP}$. 2. Shaving Logs for Approximate $\textsf{Bichrom.-$\ell_2$-Closest-Pair}$. An $n^2 \textrm(d) / \log^{ω(1)} n$ time algorithm for $(1+1/\log^{ω(1)} n)$-approximation to $\textsf{Bichrom.-$\ell_2$-Closest-Pair}$ or $\textsf{Bichrom.-$\ell_1$-Closest-Pair}$ for polylogarithmic $d$ implies $\textsf{NEXP}$ has no polynomial size $\textsf{SYM}\circ\textsf{THR}$ circuits. 3. Shaving Logs for Modest Dimension Boolean $\textsf{Max-IP}$. An $n^2 / \log^{ω(1)} n$ time algorithm for Bichromatic Maximum Inner Product with vector dimension $d = n^ε$ for any small constant $ε$ would imply $\textsf{NEXP}$ has no polynomial size $\textsf{THR} \circ \textsf{THR}$ circuits. Note there is an $n^2\textrm{polylog}(n)$ time algorithm via fast rectangle matrix multiplication. Our results build on two structure lemmas for threshold circuits.