CS Paper Radar

Products of Distinguisher Hulls

John Paul Steinberger, Zhe Zhang

cs.CC cs.CR ·submitted 2026-11-19 14:19 UTC · v1
theory

Abstract

The distinguisher hull of two distributions is the convex hull of the pairs of acceptance probabilities of tests in a specified class. We study its behavior under independent products for size-bounded Boolean circuits. We derive a geometric consequence of Dwork and Tankala's supersimulator theorem (FOCS 2026), giving a substantially different proof of approximate product containment for distinguisher hulls. In particular, our construction uses nonadaptive sampling in place of adaptive score corrections.

Closest papers

Nearest neighbours by meaning across the whole index.

A Separation Between Distribution-Free SQ Learning and Dimension Complexity

cs.CC ·2026-09-17 ·Shyamal Patel
hot direction similarity 0.58
Abstract

We show that there exists a class of boolean functions C such that $(i)$ there is a distribution-independent statistical query algorithm for learning C that makes a polynomial number of queries of inverse polynomial tolerance and $(ii)$ for any set of functions $Φ_1, \dots, Φ_r$ such that for all $f \in$ C we can write $f(x) = \text{sign} \left( \sum_{i = 1}^r w_i Φ_i(x) \right)$ for some set of weights $w_i \in \mathbb{R}$, we must have that $r \geq n^{ω(1)}$. This gives a superpolynomial separation between dimension complexity and the query complexity of distribution-free learning in the statistical query model, negatively answering a question of Feldman, Kamath, and Srebro [FKS26]. Our construction C is a subclass of DNFs, and the proof is a simple consequence of recent progress on agnostically learning conjunctions [DKR25,CPS26] and the work of Razborov and Sherstov on the sign rank of DNFs [RS10].

0.28

Counting and Covering in Nearest-Neighbour Representations of Boolean Functions

cs.DM cs.LGmath.CO ·2026-09-19 ·Martin Anthony
theory similarity 0.58
Abstract · 55 pages, 1 diagram, 1 table

We study the number of prototypes needed to represent Boolean functions by nearest-neighbour classification. There are two distinct settings: the prototypes may be arbitrary points of Euclidean space, or they may themselves be required to lie in the Boolean cube. For unrestricted prototypes, we strengthen a known lower bound for almost all Boolean functions. The bound applies simultaneously to nearest-neighbour voting rules with any number of voting neighbours, and substantially narrows the gap with the known general upper bound. We obtain a VC-dimension bound for classes with a bounded number of prototypes, and show that it is sharp in order in dimensions at least four. We then study Boolean prototypes, beginning with symmetric threshold functions. A connection with covering designs expresses the minimum number of prototypes at every threshold level exactly in terms of a covering number, and leads to further exact results for related monotone functions, including disjunctive extensions and a characterisation of when a representation with a single negative prototype is possible. For a uniformly random Boolean function, the Boolean nearest-neighbour complexity, as a proportion of the cube, is asymptotically close either to one half or to one, with explicit limiting probabilities. In particular, almost every Boolean function requires at least approximately half as many prototypes as there are points in the cube, and one half is the largest proportion for which such a lower bound holds. Finally, we consider arbitrary symmetric Boolean functions. Their Boolean nearest-neighbour complexity is closely approximated by a weighted vertex-cover problem on paths. As a consequence, a uniformly random symmetric function typically requires prototypes amounting to $11/20$ of the cube. This is much larger than the upper bounds known when the prototypes are allowed to lie anywhere in Euclidean space.

0.31

A Version Space Approach for Digital Circuit Analysis

cs.CR cs.AR ·2026-09-01 ·Mitchell A. Thornton
code/data similarity 0.57
Abstract · 23 pages, 3 figures. Code: https://github.com/mitch-thornton/locked-logic-key-counting, archived at https://doi.org/10.5281/zenodo.22218068

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.

0.43

Universal Hardness From Masking Channels

cs.LG cs.CC ·2026-11-03 ·Parikshit Gopalan, Manoj Prabhakaran, Pranay Tankala
theory similarity 0.56
Abstract

We prove a broad learning-theoretic generalization of the celebrated hardcore lemma concerning the average-case complexity of computing a Boolean function (Impagliazzo, 1995). Our starting point is the observation that the classic notion of a hardcore measure, which reweights a function's input distribution, is equivalent to an input-dependent masking channel that injects randomness into the function's output distribution until it appears fully pseudorandom. The analogue of density of the measure is the fidelity of the channel. From this viewpoint, we develop a general framework for certifying hardness that allows for non-Boolean functions $f$ and a wide range of notions of hardness besides the classic 0-1 loss, by choosing the right notion of fidelity via convex duality. We show the difficulty of learning $f$ using a class $\mathcal{C}$ to minimize a convex loss is tightly characterized by the maximum fidelity possible for a masking channel, which measures the least amount of noise the channel must add to hide the structure of $f$ and make it $\mathcal{C}$-indistinguishable from random noise. Using our framework, we derive a number of multiclass generalizations of the hardcore lemma, and reveal some unexpected subtleties in going to larger alphabets. We construct a universal masking channel that applies to many natural notions of hardness simultaneously. Such channels are dual to omnipredictors, which optimize multiple losses at once (Gopalan, Kalai, Reingold, Sharan, and Wieder, 2022). We observe a symmetry between masking channels and generalizations of the hardcore lemma using pseudoentropy. We present a tight characterization of pseudoentropy using the MaxEnt algorithm from machine learning. A long line of research has shown that learning and hardness are two sides of the same coin; our framework gives a crisp and general formulation of this principle via convex duality.

0.26

Sensitivity and Block Sensitivity of Elementary Symmetric Boolean Functions of Arbitrary Degree

cs.DM math.CO ·2026-09-20 ·Yuan Li, Jing Zhang
theoryhot direction similarity 0.55
Abstract · 26 pages

Let $σ_{n,d}$ denote the elementary symmetric Boolean function of $n$ variables and degree $d$. We completely determine the sensitivity, average sensitivity, and block sensitivity of $σ_{n,d}$ for every $1\le d\le n$. Using Lucas' theorem, we obtain a uniform binary description of the Hamming-weight value sequence, from which the sensitivity and average-sensitivity formulas follow and the computation of block sensitivity reduces to at most four explicit candidates. Combining these results with the arbitrary-degree formula for certificate complexity, we determine the exact relations among sensitivity, block sensitivity, and certificate complexity. We also prove a general result for symmetric Boolean functions: every nonconstant symmetric Boolean function $f$ satisfies \[ \bs(f)\le \max\{s(f),C(f)-1\}. \] Consequently, only the three patterns \[ s=\bs=C,\qquad s=\bs<C,\qquad s<\bs<C \] can occur for nonconstant symmetric Boolean functions. For elementary symmetric Boolean functions, we give necessary and sufficient conditions for each of these three patterns, thereby completely classifying the relations among $s(σ_{n,d})$, $\bs(σ_{n,d})$, and $C(σ_{n,d})$. In particular, we obtain a necessary and sufficient characterization of the full strict hierarchy \[ s(σ_{n,d})<\bs(σ_{n,d})<C(σ_{n,d}), \] and exhibit infinite families for which it holds.

0.47

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.55
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

Ancilla-free randomized Toffoli gates and the T-count of Boolean oracles

cs.CC quant-ph ·2026-10-28 ·Arul Rhik Mazumder
code/data similarity 0.55
Abstract · 27 pages, 4 figures, 1 table. Verification scripts: https://github.com/arulrhikm/randomized-oracle-checks

In fault-tolerant Clifford+T circuits, a Boolean oracle costs T gates and extra qubits, and on four or more qubits every exact Toffoli gate needs an extra qubit. Gosset, Kothari and Zhang showed that sampling a fresh random circuit for each call makes the T-count of the Toffoli gate independent of its size, but a direct implementation of their sampler uses about one extra qubit per bit of precision. We show that computing the sampled parities in place, on the gate's own controls, removes every extra qubit once the gate is large enough: each random circuit then uses about 8 T gates per bit of precision and borrows only the gate's own idle inputs. This is one T gate more per circuit than the best measurement-free variant that keeps one clean ancilla. The same holds for exclusive-ors of indicators of affine subspaces, such as equality tests and checks of linear equations. For randomized circuits that do not measure, this is within a factor of eight of optimal up to an additive constant, even with extra qubits, and when each random circuit computes a Boolean function exactly, closing the factor asymptotically is equivalent to determining the leading constant in the T-count of exact multi-controlled Toffoli gates. Finally, the oracle of the indicator of a random set of fixed density needs exponentially many T gates at constant error, while that of an affine subspace of the same density needs a constant number, and extra qubits reduce the exponential cost only quadratically.

0.35

Multiplicative and Additive Extractors for Low Entropy Samplable Sources Under Reduced Assumptions

cs.CC ·2026-11-05 ·Marshall Ball, Eshan Chattopadhyay, Mohit Gurumukhani, Ronen Shaltiel, Yunya Zhao
hot direction similarity 0.55
Abstract

Trevisan and Vadhan [TV, FOCS'00] constructed (seedless) extractors for distributions samplable by poly-size circuits that have very high min-entropy, under the very strong complexity theoretic hardness assumption that $\mathsf{E}=\mathsf{DTIME}(2^{O(n)})$ requires size $2^{Ω(n)}$ circuits that have oracle access to $Σ_6^{\text{P}}$. In this paper we give three new explicit constructions of extractors for samplable distributions. First, we construct an extractor that extracts one bit, with constant error, for min-entropy $k=O(\log n)$, which matches the non-constructive probabilistic argument. This result uses hardness for nondeterministic circuits, and achieves the same parameters as the recent extractor of Oh and Shaltiel [OS, STOC'26] under an incomparable hardness assumption. In contrast to the extractor of [OS26], our extractor (and, similarly, the constructions below) also works for the more general class of distributions samplable with postselection (a model introduced by [BGDM, FOCS'23] that generalizes samplable and recognizable sources). Second, we construct an extractor that extracts almost all the entropy, with polynomially small error, for min-entropy $k=n^α$, where $α>0$ is an arbitrary constant. This result also uses hardness for nondeterministic circuits, and significantly improves upon the recent extractor of [Shaltiel, FOCS'25] which required a much stronger assumption. This extractor is also \textit{multiplicative}: a stronger notion suggested in [AASY, Comp. Complexity'16; Shaltiel, CCC'25] to make extractors for samplable distributions suitable for selecting keys for cryptographic protocols. Third, we construct an extractor that extracts almost all the entropy, with polynomially small error, for min-entropy $k=\mathrm{polylog}(n)$. This result uses hardness for circuits that have oracle access to $Σ_2^{\text{P}}$.

0.30