A pruning procedure maps a Boolean circuit to a circuit on the same variables that accepts only satisfying assignments of the original.
Valiant and Vazirani give a pruning procedure that leaves exactly one satisfying assignment of every satisfiable circuit with probability $\Omega(1/n)$, where $n$ is the number of variables. Dell, ... more >>>

Border complexity captures polynomials that can be approximated arbitrarily well by small algebraic circuits, and debordering asks how efficiently such an approximation can be converted into an exact computation. Debordering lies at the heart of the gap between Valiant's determinant versus permanent conjecture and its strengthening by Mulmuley and Sohoni ... more >>>

We prove an $\Omega((\log n/\log\log n)^2)$ unconditional lower bound on the maximum of the query time and update time for dynamic data structures supporting reachability queries in $n$-node directed acyclic graphs under edge insertions. This improves the $\widetilde{\Omega}(\log^{3/2} n)$ lower bound of Larsen and Yu [SICOMP 2025], and matches the ... more >>>