CS Paper Radar

A Version Space Approach for Digital Circuit Analysis

Mitchell A. Thornton

cs.CR cs.AR ·submitted 2026-09-01 02:49 UTC · v1
code/data

Abstract

Many questions about a digital circuit take the same form. A hidden object is consistent with a set of observations, and one wants to know how many remain consistent and which observation to make next. The set of surviving candidates is the version space, and its size, on a logarithmic scale, measures how much the observations have settled. This paper develops the version-space view as one method and applies it to two circuit-analysis problems usually treated as unrelated. The first is probabilistic combinational equivalence checking, where the candidates are Boolean functions and the observations are modified-Haar spectral coefficients. A method proposed in 2002 posed this counting problem and solved only two special cases, leaving the general case an enumeration exponential in the number of observations. We close it. A reparameterization onto block sums turns the dependence among nested coefficients into locality, a sum--product recursion counts the surviving functions exactly in time polynomial in the truth-table size, closed forms follow for a single coefficient, a coefficient pair, and every ancestor-closed set, and the error of the independence approximation the 2002 work resorted to equals a computable lattice index. Every formula is checked against exhaustive enumeration and reproduces the 2002 tables. The second application is key counting for logic-locked netlists, where the candidates are keys and the observations are oracle responses. The same recursion, run over the gate-level factor graph, computes the number of keys still consistent with a set of queries; across seventy instances of the TrustHub obfuscation release the surviving entropy falls below the advertised key length every time. The two applications are one method: a witness supplies observations, each removes candidates, and the version space is counted exactly.

Comment
23 pages, 3 figures. Code: https://github.com/mitch-thornton/locked-logic-key-counting, archived at https://doi.org/10.5281/zenodo.22218068

Closest papers

Nearest neighbours by meaning across the whole index.

A Little Derandomization Goes a Long Way: Unconditional Circuit Lower Bounds using Low-Degree PIT

cs.CC ·2026-11-05 ·Nikolai Chukhin, Karthik Gajulapalli, Alexander Golovnev, Ivan Mihajlin
theory similarity 0.61
Abstract

We prove unconditionally that either NE contains a language requiring Boolean circuits of size at least $2^n/(2n)$, or $VP^0_{\mathbb{Z}}\ne VNP^0_{\mathbb{Z}}$, a constant-free version of Valiant's conjecture over the integers. The Boolean alternative implies that $NP\not\subseteq SIZE[n^k]$ for every constant $k\ge1$. Our proof gives a fine-grained variant of the connection between Polynomial Identity Testing (PIT) and circuit lower bounds established by Kabanets and Impagliazzo (2004). We show that the specific identity tests required by this argument can be performed over the integers without a derandomization assumption. Over a fixed finite field $\mathbb{F}$, we first give a deterministic $O(st^{d-1})$-time algorithm for PIT on size-$s$ circuits computing degree-$d$ polynomials in $t$ variables. We further show that, for any fixed $d\ge2$ and $\varepsilon>0$, improving this running time by a factor of $t^{\varepsilon}$, even nondeterministically, implies either the same Boolean lower bound or an arithmetic circuit lower bound of $t^{1+\varepsilon/2}$ for a polynomial family from $VNP_{\mathbb{F}}$. If nondeterministic PIT instead runs in time $s^{o(d)}t^{(1-\varepsilon)d}$ for infinitely many degrees $d$, then the arithmetic lower bound strengthens to $VP_{\mathbb{F}}\ne VNP_{\mathbb{F}}$. Over the integers, we give a deterministic PIT algorithm for syntactically set-multilinear circuits running in time $s^{O(1)}t^{5d/6}$, which yields the unconditional result above. Combining the Kabanets-Impagliazzo argument with range avoidance, we show that an NP algorithm for PIT over $\mathbb{Z}$ gives a purely arithmetic win-win: either $VP_{\mathbb{Z}}\ne VNP_{\mathbb{Z}}$, or constant-degree polynomials of maximum circuit complexity can be constructed in FNP.

0.23

Applicative theories can count

cs.LO ·2026-11-07 ·Melissa Antonelli, Marcel Ertel, Eduardo Skapinakis
hot direction similarity 0.60
Abstract

Applicative theories offer a proof-theoretic framework for studying complexity. In this paper, we introduce a family of applicative theories to characterize classes ranging from constant-depth circuits to polynomial space. Our approach relies on a simple axiom scheme, the small variations of which allows to capture various forms of counting and alternation. This leads to highly uniform results. When applied on notation, the scheme captures bit counting, yielding a characterization of the functions computable by constant-depth, polynomial-size threshold circuits ($\textbf{FTC}^0$); when applied lexicographically, it allows for the counting of accepting computations, yielding a characterization of the functions in the counting hierarchy ($\textbf{FCH}$). Increasing the logical complexity of the induction formulas allowed in the scheme, we obtain characterizations of the functions computable by bounded Boolean circuits of logarithmic-depth and polynomial-size ($\textbf{FNC}^1$) and of the functions computable in polynomial space ($\textbf{FPSPACE}$). The latter characterization solves an open problem in the field. Finally, we investigate separation results. While it is unknown whether $\textbf{FNC}^1$ and $\textbf{FCH}$ are different, there is an oracle relative to which (relativized) $\textbf{FNC}^1$ is strictly contained in (relativized) $\textbf{FCH}$. We use this fact to separate the theories characterizing them, by exploring their ability to represent higher-order functionals.

0.29

count-catcher: Lean Theorems from Model Counting Certificates

cs.LO cs.AI ·2026-10-26 ·Johannes K. Fichte, Stefan Szeider
theory similarity 0.59
Abstract

We present count-catcher, a tool that turns a CPOG certificate of a count by the exact model counter d4 into a Lean theorem that a CNF formula defined in Lean has exactly N models over V variables. With an encoding lemma, this theorem becomes a theorem about the number of combinatorial objects. A CPOG certificate consists of a Boolean circuit equivalent to the formula and a proof of equivalence. count-catcher checks in Lean that the formula implies the circuit (forward check) and the circuit implies the formula (reverse check). For the forward check, lrat-catcher streams a refutation through the LRAT checker of Lean's standard library. The reverse check and the validity check of the circuit are computations proved correct in Lean. Lean runs all three checks as compiled code, so the theorem depends on Lean's kernel, compiler and runtime, as does CPOG's verified checker. We combine the theorem with results from Mathlib, for instance with Burnside's lemma to count graphs up to isomorphism. We prove the number of Latin squares of order 8 as a weighted sum of hundreds of certified counts from about eight terabytes of certificates. We turn about half of the 2022 Model Counting Competition formulas into theorems, with the three checks taking about a quarter of the time of CPOG's verified checker. We found that CPOG's unverified checker reported wrong counts, and removed its verified checker's dependence on two unproved lemmas. End to end, a theorem costs about the same as a checked count.

0.36

Sumset Structure in Local Computation

cs.CC ·2026-09-19 ·Alexander Golovnev, Mohit Gurumukhani
publishedtheory similarity 0.58
Abstract

We introduce and study a new model of decision trees that lies at the frontier of provable circuit lower bounds. We study $\ell$-local decision trees, in which each internal node queries an $\ell$-local function of the input. We show that sufficiently strong lower bounds for $\ell$-local decision trees would imply several breakthrough circuit lower bounds, including super-linear size lower bounds for log-depth circuits and improved bounds for unrestricted-depth circuits. Previously, such consequences were known to follow from strong lower bounds for depth-$3$ circuits, which has been the main prior approach in attempting to prove these results. Since local decision trees are strictly weaker than depth-$3$ circuits, this provides a formally easier route to the same circuit lower-bound consequences. We prove essentially optimal lower bounds for a weaker variant that we call oblivious $\ell$-local decision trees, where all nodes at the same depth query the same function. Our lower bounds follow from a new technique that uncovers sumset structure in local maps, and our hard functions are sumset dispersers, sumset condensers, and directional affine dispersers. Along the way, we give an explicit construction of a sumset condenser with small entropy loss. As an additional contribution, we initiate the study of degree-$2$ decision trees, in which each query is a quadratic polynomial of the input. We show that proving lower bounds in this model is a natural stepping stone toward constructing dispersers for degree-$2$ variety sources, which imply improved circuit lower bounds for unrestricted depth circuits. We prove nearly maximal lower bounds for the oblivious variant of the model.

0.35

An $n^2\log\log n$ Lower Bound for Permanent Circuits with Valid Division

cs.CC math.AG ·2026-08-26 ·Jizhou Guo
theoryhot direction similarity 0.58
Abstract · 14 pages. Version 2: the passage to valid division is credited to Strassen and Baur-Strassen (version 1 presented it as new); refines the cr…

We record lower bounds for permanent circuits with valid division over characteristic zero, counting nonscalar multiplications and divisions while additions and scalar operations are free. Chapter 5 of OpenAI's Ten Advances supplies the block construction and critical-locus estimate; these, with the parameter choice made here and the classical bounds of Strassen and Baur-Strassen, give liminf as n tends to infinity of L_div(per_n)/(n^2 log_2 log_2 n) >= 1/12. Our finite-parameter refinement for matching-minor polynomials observes that the coefficient vector at deletion size h lies in a space of dimension at most min{binom(t,h), binom(t,d-h)}. Twelve machine-checked declarations of the Lean development accompanying OpenAI's manuscript on border determinantal complexity of the permanent (September 24, 2026) imply, by a short written argument, the existence of a geometric slice; a further written, unformalized application of the same criterion gives L_div(per_n) >= (n^2/119790) log_2(n/44) for n >= 1936. Assuming Proposition 7.3 of that manuscript gives the bound (n^2/86400) log_2(n/48) for n >= 1408. These are order-of-growth results; the elementary Hessian bound n^2/2 is larger at practical orders.

0.39

The Complexity of Choosing Parity Projections

cs.CC ·2026-10-30 ·Karthik Sheshadri, Nicholas Smirnov
theory similarity 0.57
Abstract

Cube attacks in cryptanalysis seek small sets of Boolean variables (cubes) whose parity sum is constant. We study the bounded constant derivative problem introduced by Smirnov (2026), which seeks a smallest cube with sum 1, and its sum-0 analogue. Despite their similarity, the problems differ sharply in parameterized complexity: the sum-1 problem admits a $2^{O(k^2)}\operatorname{poly}(N)$-time algorithm, where $k$ is cube size, whereas the sum-0 problem is not fixed-parameter tractable unless $\mathrm{FPT}=\mathrm{W}[1]$. Without a bound on cube size, both problems are $Σ_2^{\oplus\mathrm{P}}$-complete and NP-hard to approximate within $N^{1-\varepsilon}$ for every fixed $0<\varepsilon<1$. Our hardness proofs use a crown construction that embeds maximal monomials of parity-projected circuits into positive 2CNF. This yields completeness and inapproximability results, as well as a dichotomy for Boolean constraint languages of arity at most two: the bounded constant derivative problem is in P when all relations are affine and $Σ_2^{\oplus\mathrm{P}}$-complete otherwise. We also give algorithms parameterized by the number of quadratic rounds, treewidth, or ordered branching-program width, with lower bounds for the first two unless $\mathrm{NP}\subseteq\mathrm{SUBEXP}$. The treewidth lower bound holds for circuits; the case of 2CNF remains open.

0.23

Optimal Shallow Circuits for Majority

cs.CC ·2026-09-27 ·Victor Lecomte, Prasanna Ramakrishnan
theoryhighly cited similarity 0.57
Abstract

Four decades on, Håstad's classical $2^{Ω(n^{1/(d-1)})}$ lower bound for depth-$d$ circuits computing Parity remains the best known $\mathrm{AC}^0$ circuit lower bound for any explicit function. Majority has long been a compelling candidate for stronger lower bounds: the most natural circuits computing it are substantially larger than those for Parity and have repeatedly been conjectured to be optimal. We present a simple construction, found by GPT-6 Astra, of depth-$d$ circuits of size $2^{O(n^{1/(d-1)})}$ for any symmetric function. This result settles the asymptotic $\mathrm{AC}^0$ circuit complexity of Majority, matching Håstad's lower bound. The proof draws inspiration from well-loved combinatorial tools, including the color-coding technique of Alon, Yuster, and Zwick (1995).

0.33

Deterministic factorization of constant depth circuits from whitebox PIT

cs.CC ·2026-11-06 ·Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan, Ramprasad Saptharishi +1 more
similarity 0.57
Abstract

We show that over the field of rational numbers, there is a deterministic algorithm for factorization of constant depth circuits that makes calls to a (whitebox or blackbox) PIT algorithm for such circuits. The time complexity of the algorithm (and hence the number of calls to the PIT oracle) is polynomially bounded in the size and degree of the input circuit. Our reduction to PIT is fairly simple and general and applies as it is to other natural classes of algebraic circuits like formulas and algebraic branching programs. Prior to this work, the known deterministic factorization algorithms for constant depth circuits crucially relied on \emph{blackbox} PIT [Bhattacharjee et al.]. Our main technical ingredient is an efficient, deterministic algorithm that, when given access to sufficiently high degree truncations of \emph{all} the power series roots of a constant depth circuit, uses oracle calls to any (whitebox or blackbox) PIT algorithm for these circuits, and partitions the roots into the sets of conjugates; thereby identifying the irreducible factors. For our proof, we rely on a root recombination criterion using logarithmic derivatives [Sasaki et al., Bostan et al., Lecerf] and show that this criterion can be efficiently and deterministically implemented for power series roots of constant depth circuits using access to any PIT oracle. On the way, we discuss an algorithm that may be of independent interest: it takes as input a matrix whose entries are multivariate constant depth circuits over a field $\mathbb{F}$, requires oracle access to any PIT algorithm for these circuits and outputs a basis for the $\mathbb{F}$-kernel of this matrix in polynomial time.

0.33