Showing 2026Show all
3 papers · 1 filter
cs.CC2026
Approximate Polynomial Satisfiability and Integral Closure Membership in the Counting Hierarchy
Sanyam Agarwal, Archit Hari, Anurag Pandey +1
Andrews, Garg, and Schost (FOCS~2026) recently, in a breakthrough result, placed Hilbert's Nullstellensatz (HN) in the Counting Hierarchy ($\CH$) using constant-depth circuits for…
cs.CC2026
Deterministic NC Quadratic Root Counting in Characteristic Two
Sanyam Agarwal, Gorav Jindal
Counting satisfying assignments of Boolean formulas is a basic problem in theoretical computer science, with $\#3\text{-}\SAT$ as the standard $\SharpP$-complete problem. More gene…
cs.CC2026
On the Principal Minor Expansion and Complexity of the Symmetrized Determinant
Sanyam Agarwal, Markus Bläser, Mridul Gupta
Barvinok introduced the symmetrized determinant ($\sdet$) as a \emph{non-commutative} analogue of the determinant. Intuitively, given a square matrix over an associative algebra, w…