circuit complexity 2ACC^0 1AND function 1approximation theory 1CC^0 circuits 1linear programming 1lower bounds 1majority function 1symmetry 1torus polynomial approximation 1torus polynomials 1
From the 2 of 3 linked papers with an AI index.
3 papers
cs.CC2026
Degree Lower Bounds for Torus Polynomials and vs
Vaibhav Krishan, Sundar Vishwanathan
The paper studies lower bounds on the degree of torus polynomial approximations for Boolean functions, reducing the Majority‑vs‑ACC^0 conjecture to a family of linear programs and…
cs.CC2026
On Lower Bounds for AND via Torus Polynomials
Vaibhav Krishan, Jayalal Sarma
The paper uses torus polynomial approximations to prove exponential size lower bounds for symmetric CC^0 circuits computing the AND function and provides degree upper bounds for ce…
cs.LO2026
On Proof Systems for #QBF
Sravanthi Chede, Leroy Chew, Vaibhav Krishan +1
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…