4 papers
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…
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…
The Limits of Tractable Marginalization
Oliver Broadrick, Sanyam Agarwal, Guy Van den Broeck +1
Marginalization -- summing a function over all assignments to a subset of its inputs -- is a fundamental computational problem with applications from probabilistic inference to for…
Probabilistic Generating Circuits -- Demystified
Sanyam Agarwal, Markus Bläser
Zhang et al. (ICML 2021, PLMR 139, pp. 12447-1245) introduced probabilistic generating circuits (PGCs) as a probabilistic model to unify probabilistic circuits (PCs) and determinan…