Certifiable Boolean Reasoning Is Universal

• URL: http://arxiv.org/abs/2602.05120v1
• Date: Wed, 04 Feb 2026 23:09:49 GMT
• Title: Certifiable Boolean Reasoning Is Universal
• Authors: Wenhao Li, Anastasis Kratsios, Hrad Ghoukasian, Dennis Zvigelsky,
• Abstract summary: We show that a deep learning model can always reason through any $f:0,1Bto0,1$ task.<n>We then prove a universality theorem: for any Boolean $f:0,1Bto0,1$, there exists a parameter configuration under which the sampled circuit computes $f$ with arbitrarily high probability.
• Score: 17.33786517296165
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The proliferation of agentic systems has thrust the reasoning capabilities of AI into the forefront of contemporary machine learning. While it is known that there \emph{exist} neural networks which can reason through any Boolean task $f:\{0,1\}^B\to\{0,1\}$, in the sense that they emulate Boolean circuits with fan-in $2$ and fan-out $1$ gates, trained models have been repeatedly demonstrated to fall short of these theoretical ideals. This raises the question: \textit{Can one exhibit a deep learning model which \textbf{certifiably} always reasons and can \textbf{universally} reason through any Boolean task?} Moreover, such a model should ideally require few parameters to solve simple Boolean tasks. We answer this question affirmatively by exhibiting a deep learning architecture which parameterizes distributions over Boolean circuits with the guarantee that, for every parameter configuration, a sample is almost surely a valid Boolean circuit (and hence admits an intrinsic circuit-level certificate). We then prove a universality theorem: for any Boolean $f:\{0,1\}^B\to\{0,1\}$, there exists a parameter configuration under which the sampled circuit computes $f$ with arbitrarily high probability. When $f$ is an $\mathcal{O}(\log B)$-junta, the required number of parameters scales linearly with the input dimension $B$. Empirically, on a controlled truth-table completion benchmark aligned with our setting, the proposed architecture trains reliably and achieves high exact-match accuracy while preserving the predicted structure: every internal unit is Boolean-valued on $\{0,1\}^B$. Matched MLP baselines reach comparable accuracy, but only about $10\%$ of hidden units admit a Boolean representation; i.e.\ are two-valued over the Boolean cube.

Related papers

• Optimal Anytime-Valid Tests for Composite Nulls [12.048034578791954]
  We consider the problem of designing optimal level-$$ power-one tests for composite nulls.<n>We first consider the finite-alphabet case($|mathcalX| = m infty$, and show that a test based on emphuniversal $e$-process(formed by the ratio of a universal predictor and the running null MLE) is optimal.
  arXiv  Detail & Related papers  (2025-12-23T04:14:56Z)
• Bias-Class Discrimination of Universal QRAM Boolean Memories [0.0]
  Given query access to a quantum memory, we ask: what can be inferred about the bias class of $f$ using coherent, addressable queries?<n>We show that for exact-weight bias classes, the induced single-query ensemble state on the address register has a two-eigenspace structure that yields closed-form expressions for the single-copy Helstrom-equivalent measurement and success probability.<n>This goes beyond the perfect-discrimination case of Deutsch-Jozsa and complements exact-identification settings such as Bernstein-Vazirani.
  arXiv  Detail & Related papers  (2025-12-19T12:14:18Z)
• Minimalist Softmax Attention Provably Learns Constrained Boolean Functions [11.701612413596482]
  We show that simple $mathrmAND$ and $mathrmOR$ functions are unsolvable with a single-head softmax-attention mechanism alone.<n>With teacher forcing, the same minimalist attention is capable of solving them.
  arXiv  Detail & Related papers  (2025-05-26T05:33:26Z)
• ProofWala: Multilingual Proof Data Synthesis and Theorem-Proving [53.67926215943612]
  $rm Psmall ROOFWsmall ALA$ allows interaction between neural theorem-provers and two established interactive proof assistants (ITPs)<n>We show that a model trained on a mix of $rm Psmall ROOFWsmall ALA$-generated Coq and Lean data outperforms Lean-only and Coq-only models on the standard prove-at-$k$ metric.
  arXiv  Detail & Related papers  (2025-02-07T05:35:46Z)
• Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
  We propose two algorithms that enjoy provable scaling laws for the test-time compute of large language models.<n>One is a two-stage knockout-style algorithm, where each candidate is evaluated by its average win rate against multiple opponents.<n>The other is a two-stage league-style algorithm, where each candidate is evaluated by its average win rate against multiple opponents.
  arXiv  Detail & Related papers  (2024-11-29T05:29:47Z)
• Approximation Rates and VC-Dimension Bounds for (P)ReLU MLP Mixture of Experts [17.022107735675046]
  Mixture-of-Experts (MoEs) can scale up beyond traditional deep learning models. We show that MoMLPs can generalize since the entire MoMLP model has a (finite) VC dimension of $tildeO(LmaxnL,JW)$.
  arXiv  Detail & Related papers  (2024-02-05T19:11:57Z)
• Extending Universal Approximation Guarantees: A Theoretical Justification for the Continuity of Real-World Learning Tasks [0.0]
  We consider learning tasks given by conditional expectations $x mapsto mathrmEleft[Y mid X = xright]$. We motivate the realism of our conditions using the example of randomized stable matching.
  arXiv  Detail & Related papers  (2022-12-06T23:33:04Z)
• On Symmetric Pseudo-Boolean Functions: Factorization, Kernels and Applications [0.0]
  We prove that any symmetric pseudo-Boolean function can be equivalently expressed as a power series or factorized. We use these results to analyze symmetric pseudo-Boolean functions appearing in the literature of spin glass energy functions, quantum information and tensor networks.
  arXiv  Detail & Related papers  (2022-09-29T18:00:07Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  For every $delta>0,$ we construct CNF and formulas of size with approximate degree $Omega(n1-delta),$ essentially matching the trivial upper bound of $n. We show that for every $delta>0$, these models require $Omega(n1-delta)$, $Omega(n/4kk2)1-delta$, and $Omega(n/4kk2)1-delta$, respectively.
  arXiv  Detail & Related papers  (2022-09-04T10:01:39Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  We consider the problem of quantizing a linear model learned from measurements. We derive an information-theoretic lower bound for the minimax risk under this setting. We show that our method and upper-bounds can be extended for two-layer ReLU neural networks.
  arXiv  Detail & Related papers  (2022-02-23T02:39:04Z)
• On the Optimal Memorization Power of ReLU Neural Networks [53.15475693468925]
  We show that feedforward ReLU neural networks can memorization any $N$ points that satisfy a mild separability assumption. We prove that having such a large bit complexity is both necessary and sufficient for memorization with a sub-linear number of parameters.
  arXiv  Detail & Related papers  (2021-10-07T05:25:23Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  We study the problem of PAC learning halfspaces on $mathbbRd$ with Massart noise under Gaussian marginals. Our results qualitatively characterize the complexity of learning halfspaces in the Massart model.
  arXiv  Detail & Related papers  (2021-08-19T16:16:48Z)
• Nonparametric Learning of Two-Layer ReLU Residual Units [22.870658194212744]
  We describe an algorithm that learns two-layer residual units with rectified linear unit (ReLU) activation. We design layer-wise objectives as functionals whose analytic minimizers express the exact ground-truth network in terms of its parameters and nonlinearities. We prove the statistical strong consistency of our algorithm, and demonstrate the robustness and sample efficiency of our algorithm by experiments.
  arXiv  Detail & Related papers  (2020-08-17T22:11:26Z)
• A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
  Given a discrete probability measure supported on $N$ atoms and a set of $n$ real-valued functions, there exists a probability measure that is supported on a subset of $n+1$ of the original $N$ atoms. We give a simple geometric characterization of barycenters via negative cones and derive a randomized algorithm that computes this new measure by "greedy geometric sampling" We then study its properties, and benchmark it on synthetic and real-world data to show that it can be very beneficial in the $Ngg n$ regime.
  arXiv  Detail & Related papers  (2020-06-02T16:38:36Z)
• Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
  We give scalable, explicit digital quantum algorithms to simulate the lattice Schwinger model in both NISQ and fault-tolerant settings. In lattice units, we find a Schwinger model on $N/2$ physical sites with coupling constant $x-1/2$ and electric field cutoff $x-1/2Lambda$. We estimate observables which we cost in both the NISQ and fault-tolerant settings by assuming a simple target observable---the mean pair density.
  arXiv  Detail & Related papers  (2020-02-25T19:18:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.