Boolean Function Learning

Follow this topic Ask about this topic

Momentum

5 papers in the last four weeks, with none the four weeks before. 0.0% of all new papers.

Jul 13Week of Sep 28

Latest papers 25

All topics

Oct 4, 2026cs.LG

Private Component-by-Component Learning

We study differentially private learning problems in the realizable setting, where a hypothesis is specified by

k

components. A direct iteration of private component learners is obstructed by a simple difficulty: an approximate choice of the next component may destroy exact realizability of the labeled sample, even when the next component is locally accurate. We restore realizability using the LabelBoost procedure of Beimel, Nissim, and Stemmer [SODA '15, Algorithmica '21] and recycle data through two alternating reservoirs. The resulting learner, for a target privacy

\varepsilon

, pays only

\widetilde O(\sqrt{k}/\varepsilon)

overhead relative to the active sample requirement of a single component learning step at target accuracy

Θ(α/k)

. For learning

d

-dimensional halfspaces over a finite coordinate grid of size

L

, exact realizability makes the direct component-depth objective quasi-concave. Instantiating the framework with the IPConcave algorithm of Nissim, Tsfadia, and Yan [SODA '26] and with the quasi-concave optimizer of Cohen, Lyu, Nelson, Sarl'os, and Stemmer [STOC '23] yields a realizable sample complexity of

\widetilde{O}\left(\frac{1}{\varepsilon α}\cdot \min\{d^{2.5} \log^*L, \:\: d^{2.5} + d^{1.5} 2^{\log^*L}\}\right),

which improves on the previously known bound of

\widetilde{O}\left(\frac{1}{\varepsilon α}\cdot\min\{\frac{1}α\cdot d^{5.5}\log^*L,\:\: d^{2.5}2^{\log^*L}\}\right).

We also apply the framework to Boolean compositions: given proper private learners for classes

H_1,\ldots,H_k

, we obtain a proper private learner for

G(H_1,\ldots,H_k)

for any fixed Boolean function

G:\{0,1\}^k\to\{0,1\}

. Compared with the closure theorem of Alon, Beimel, Moran, and Stemmer [COLT '20], this reduces the overhead on a common component sample bound from

\widetilde O(k/\varepsilon)

\widetilde O(\sqrt{k}/\varepsilon)

Dvir Karni, Eliad Tsfadia

Department of Computer Science and Artificial Intelligence, Bar-Ilan University.

Boolean Function Learning Privacy-Preserving ML

Ask PDF

Sep 24, 2026math.PR

Boolean threshold functions, neuron capacity, and memory retrieval

How much information can a single neuron remember? How many memories can neural networks retrieve without creating false memories? These questions are related to a basic question: how many Boolean threshold functions

f(x)=\operatorname{sgn}(a_0+\langle a,x\rangle)

x\in\{-1,1\}^n

, are there? In this paper, we show that the number

T_n

of distinct Boolean threshold functions is

T_n=2\binom{2^n-1}{n}\bigl(1+O(n^{-99})\bigr).

Equivalently, the capacity of a single threshold neuron is

n^2-\log_2(n!)+1+O(n^{-99})

bits, improving the

O(n)

error term in the result of Kahn--Komlós--Szemerédi to

O(n^{-99})

. To prove this, we show that, for

1\le r\le n-1

, and

v_1,\ldots,v_r

are chosen at random from

\{-1,1\}^n

\mathbb P\!\left\{ \langle v_1,\ldots,v_r\rangle\cap\{-1,1\}^n =\{\pm v_1,\ldots,\pm v_r\} \right\} =1-O(n^{-99}).

In the context of the Kanter--Sompolinsky Hamiltonian for memory retrieval, this identifies

r=n-1

as a sharp threshold, at which, for almost every collection of

r

memories, the only ground states are these memories and their negatives, confirming a weaker form of the Kalai--Linial--Odlyzko conjecture. It also settles a recent open problem posed by M. Anthony on the specification number of Boolean threshold functions. In addition, we show that, for every

1\le r\le n-1

\mathbb P\{v_1,\ldots,v_r\text{ are linearly dependent}\} =2\binom r2\,2^{-n}+O\!\left(2^{-n}e^{-cn}\right),

confirming a conjecture of Kahn--Komlós--Szemerédi.

Xinyuan Xie

Boolean Function Learning Neural Network Memorization Associative Memory

Ask PDF

Sep 15, 2026cs.DS

Efficient Robust Learning at the Information-Theoretic Limit

In an important recent work, Blanc (2026) gave an algorithm for robustly learning Boolean concept classes with respect to a fixed distribution that outputs a (randomized) classifier achieving the optimal error of

η+ \varepsilon

where

η

is the noise rate. In contrast, it is well known that deterministic hypotheses cannot achieve error less than

2η+ \varepsilon.

Blanc's algorithm is computationally inefficient, and the main problem left open in his work is to find a polynomial-time algorithm given access to an oracle for empirical risk minimization (ERM). In this paper, we resolve this problem and give such an algorithm. Perhaps surprisingly, our techniques make crucial use of various types of no-regret learners. Additionally, we give an efficient algorithm (no ERM oracle required) for robustly learning any function class that admits sandwiching polynomials with respect to hypercontractive distributions. As one consequence, we give the first polynomial-time algorithm for robustly learning a halfspace with respect to Gaussian marginals that achieves error

η+ \varepsilon

for any constant

\varepsilon

Adam R. Klivans, Konstantinos Stavropoulos, Sergei Tikhonov +1

UT Austin · Institute for Advanced Study · Aarhus University

Boolean Function Learning Learning with Noisy Labels

Ask PDF

Sep 14, 2026cs.LG

Learning CNF Formulas from Uniform Random Solutions: Near-Tight Sample Complexity for Valiant's Algorithm

We revisit Valiant's algorithm (Commun. ACM'84) for learning

n

-variable CNF formulas with clause size

k

and variable degree

d

from i.i.d. uniform random solutions in the local lemma regime. For fixed

t\geq1

, under

k\gtrsim(1+1/t)\log d

, Valiant's algorithm achieves total variation error

\varepsilon

with

\widetilde{O}(n^{\lceil t \rceil}/\varepsilon)

sample complexity. For

t>1

, we prove a matching lower bound for Valiant's algorithm. At

t=1

(covering

0<t<1

), we show Valiant's algorithm has optimal sample complexity up to logarithmic factors by an information-theoretic lower bound

\widetildeΩ(n/\varepsilon)

Weiming Feng, Yixiao Yu, Yiyao Zhang

School of Computing and Data Science, The University of Hong Kong. · State Key Laboratory for Novel Software Technology, New Cornerstone Science Laboratory, Nanjing University.

Boolean Function Learning Sample Complexity PAC Learning Information-Theoretic Lower Bounds

Ask PDF

Sep 8, 2026cs.LO

Fitting and Learning Basis-Restricted Propositional Formulas

For a finite set

O

of Boolean functions, we consider the class of propositional formulas built using the functions in

O

as connectives. We determine, for each possible choice of

O

, the complexity of various fitting and learning problems. These include: finding a formula that fits a given labeled sample, finding a small one (an Occam algorithm), minimizing the number of misclassified examples when the sample is not realizable (empirical risk minimization), and several forms of PAC learning. Our results apply both to formulas (represented as trees) and to circuits. We also briefly discuss the status of the same questions for other kinds of propositional fragments.

Balder ten Cate

Boolean Function Learning Empirical Risk Minimization

Ask PDF

Jul 28, 2026cs.LG

Algorithmic Separation between Constant-Depth and Logarithmic-Depth Neural Networks

Despite the empirical advantages of deep networks over shallow ones, theoretical depth separations largely concern approximation power, while algorithmic results are mostly limited to comparisons between two- and three-layer networks. In this work, we prove the first algorithmic separation between constant-depth and logarithmic-depth networks. Specifically, we identify a class of Boolean functions with hierarchically structured Fourier spectra that logarithmic-depth networks can learn efficiently using layerwise coordinate descent by reconstructing the spectra hierarchically and adaptively. We also exhibit a subclass for which every constant-depth, polynomial-width network with sufficiently regular activations and controlled spectral norms must incur constant

L^2

approximation error under the uniform distribution over the hypercube.

Yunwei Ren, Zihao Wang, Jason D. Lee

Princeton University · Stanford University · University of California, Berkeley

Boolean Function Learning Neural Network Approximation Theory Feedforward Neural Networks

Ask PDF

Jul 9, 2026cs.LG

Learning $\mathsf{AC}^0$ under Locally Sampleable Graphical Models

The problem of learning constant-depth circuits holds profound implications for computational learning theory. In a seminal result, by introducing the low-degree algorithm, Linial, Mansour, and Nisan (J. ACM 1993) presented a quasipolynomial-time learner for

\mathsf{AC}^0

under the uniform distribution. However, obtaining comparable learning guarantees for broader classes of correlated distributions has remained a longstanding challenge. Recently, Chandrasekaran, Gaitonde, Moitra, and Vasilyan (arXiv 2026) extended these guarantees to Gibbs distributions on bounded-degree graphical models with both strong spatial mixing and polynomial growth. In this paper, we give a quasipolynomial-time learner for

\mathsf{AC}^0

under graphical models that admit efficient local samplers, circumventing the polynomial-growth requirement in prior work. The key ingredient is a new low-degree approximation for Gibbs distributions, established by simulating and suitably truncating the classical Glauber dynamics. As applications, this framework yields learners for two-spin systems, including the hard-core model and Ising model, on arbitrary bounded-degree graphs, in regimes approaching their respective sampling thresholds.

Weiming Feng, Xiongxin Yang, Yixiao Yu +1

School of Computing and Data Science, The University of Hong Kong. · Department of Computer Science, University of California, Santa Barbara. · State Key Laboratory for Novel Software Technology, New Cornerstone Science Laboratory, Nanjing University.

Boolean Function Learning

Ask PDF

Jun 28, 2026cs.DM

Chamber geometry and specification numbers of Boolean threshold functions

The specification number

σ_n(f)

of a Boolean threshold function

f

n

variables is the least number of points whose

f

-values determine

f

uniquely among all threshold functions. Its essential points form the unique minimum such set. We develop Zuev's geometric interpretation: the threshold functions are the chambers of a central hyperplane arrangement in the

(n+1)

-dimensional space of weights and thresholds, and the essential points of a function correspond exactly to the facets of its chamber, so the specification number is the chamber's facet number. The lower bound

σ_n(f)\ge n+1

becomes the fact that a pointed full-dimensional cone has at least

n+1

facets, with equality for simplicial chambers. The average specification number

\overlineσ_n

becomes an average facet count. We evaluate this average exactly via the resonance arrangement and bound it through a theorem of Fukuda, Tamura, and Tokuyama, obtaining

\overlineσ_n\le 2n

; hence

\overlineσ_n=Θ(n)

. This settles a question of Gutekunst, Mészáros, and Petersen. The method also extends to polynomial threshold functions. The same geometry links threshold functions with a threshold zonotope, whose vertices are modified Chow vectors. Its one-skeleton is the one-inclusion graph, and a vertex's degree is the specification number of that function. Finally, we treat the operations of Lozin et al. on functions of minimum specification number. Adding a variable and extending on a variable both take the product of a chamber closure with a half-line, preserving simpliciality. For the symmetric-variables extension we give an exact thresholdness criterion and show that minimum specification number is preserved whenever the extension is a threshold function. We also resolve a question they pose concerning a fourth operation.

Martin Anthony

Department of Mathematics, London School of Economics

Boolean Function Learning

Ask PDF

Jun 22, 2026cs.AI

Teaching LLMs String Matching, Backtracking, and Error Recovery to Deduce Bases and Truth Tables for the Combinatorially Exploding Bit Manipulation Puzzles

This paper presents our algorithmic innovations for the NVIDIA Nemotron Model Reasoning Challenge, focusing on Bit Manipulation Puzzles. In this task, the objective is to discover a hidden logical rule transforming input binary strings to outputs, then apply it to unseen inputs. Large Language Models (LLMs) notoriously struggle here; traditional methods force them to simulate complex boolean logic and arithmetic, leading to hallucinations. Furthermore, the search space of bitwise operations (combinations of shifts, rotations, and logic gates) suffers from a severe combinatorial explosion. To overcome this computational intractability, we present a novel approach that abandons arithmetic logic entirely in favor of string similarity, structured search, and autonomous error recovery. Our core contributions are: 1. Bases and Truth Table Formulation: We reframe logic-gate deduction into a base-selection task, leveraging string similarity (minimal bit flips) to isolate primitive transformations ("bases") and deduce truth tables without complex arithmetic. 2. Backtracking DFS and Error Recovery: We formalize a search process that tests candidate bases, detects logical collisions across examples, and backtracks upon failure to perform robust error recovery. 3. Bit Tokenization and Interactive Reasoning SFT: We force the tokenizer to encode binary strings as individual single-bit tokens. We use dynamic masking to simulate external oracle feedback, training the model to hypothesize, self-evaluate, and backtrack natively. Evaluated on bit manipulation puzzles, our approach achieved over 96% validation accuracy. This represents the highest performance in this category, driving our 7th Place overall finish in the contest.

Prateek Agnihotri, Sanchit Jain, Prabhat Agnihotri +2

7th Place NVIDIA Nemotron Challenge Team

Boolean Function Learning Program Synthesis

Ask PDF

Jun 15, 2026stat.ML

Tight $L_\infty$ Sample Complexity for Low-Degree and Sparse Boolean Polynomials

Motivated by the optimization of bounded binary black-box functions, we study the problem of learning polynomial surrogates over the Boolean hypercube. To ensure that optimizing the surrogate yields good solutions for the underlying objective, we require uniform

L_\infty

-error guarantees rather than the usual

L_2

-type guarantees. We characterize the minimax sample complexity of uniform estimation under subgaussian noise for two classes of bounded polynomials. First, for polynomials of degree at most

d

n

variables, the sample complexity scales as

n^{d+1}

. Second, for

s

-sparse Fourier-Walsh polynomials with

s \leq n

, it scales as

ns^2

. These rates differ structurally from the noiseless setting, where uniform exact recovery scales as

n^d

and

ns

, respectively. Our lower bounds hold even for arbitrary adaptive learners, showing that the additional factors are intrinsic to the noisy cases. Standard Fourier-analysis tools for the

L_2

-norm do not naturally extend to the

L_\infty

-setting in a way that yields uniform guarantees. Our proofs overcome this difficulty by relying on suitably chosen auxiliary norms that serve as proxies for controlling the

L_\infty

-error. Together, our results provide a tight characterization of the sample complexity of learning optimization-safe polynomial surrogates.

Jasper van Doornmalen, Mathieu Molina, Victor Verdugo +1

Institute for Mathematical and Computational Engineering, Pontificia Universidad Católica de Chile, Chile · Blavatnik School of Computer Science and AI, Tel Aviv University, Israel · Institute for Mathematical and Computational Engineering, and Department of Industrial and Systems Engineering, Pontificia Universidad Católica de Chile, Chile

Surrogate Modeling Boolean Function Learning Sample Complexity

Ask PDF

Jun 15, 2026cs.CC

Polynomial-Time Mistake-Bounded Language Generation

In this note, we introduce a polynomial-time version of the mistake-bounded language generation (MBLG) framework due to Kleinberg, Peale, and Reingold (2026). We observe that the family of parities of variables, and the family of conjunctions of literals, are polynomial-time MBLG. Our main result states that the family of monotone Boolean functions with polynomially-many maxterms is polynomial-time MBLG. This family includes all monotone Boolean functions, computable by polynomial-size decision trees. Our technique can be presented as a new combinatorial game about writing numbers on a board.

Héctor Jimenez, Alexander Kozachinskiy, Vicente Opazo

University of Chile · CENIA

Boolean Function Learning

Ask PDF

Jun 14, 2026cs.NE

Runtime Analysis of Cartesian Genetic Programming in Evolving Boolean Functions

Cartesian Genetic Programming (CGP) is among the practical and popular forms of Genetic Programming as it uses a graph-based representation of programs. This paper presents a first runtime analysis of CGP in evolving Boolean functions using complete training sets. We prove an asymptotic bound

O(n D^5)

for the expected number of fitness evaluations of CGP to construct a conjunction of

n

inputs using at most

D \geq n-1

binary gates, a minimal function set, and even with a strict survival selection. When the non-strict selection is used, the bound is improved to

O(n D^4)

. Our analysis reveals interesting characteristics of CGP induced search, which have been only observed empirically. In particular, enabling the acceptance of equally good solutions, including those with connected gates non-contributing to fitness, can lead to a speedup, and consequently a better asymptotic time bound. In contrast to conjunctions, we also prove a negative result which shows that CGP requires exponential time to evolve an exclusive disjunction. Experiments evolving conjunctions complement our theoretical findings. The use of incomplete training sets is found to further reduce the average number of fitness evaluations while maintaining a good level of generalisation.

Duc-Cuong Dang, Roman Kalkreuth, Andre Opris

University of Passau, Passau, Germany · RWTH Aachen University, Aachen, Germany

Boolean Function Learning Genetic Programming Runtime Analysis of Evolutionary Algorithms

Ask PDF

Jun 7, 2026cs.LG

Understanding the Parameter Space Geometry of Transformers Encoding Boolean Functions

Transformers consistently fail to learn certain simple functions that are provably expressible with specific parameter settings. This gap between learnability and expressivity is particularly prominent for sensitive functions -- functions whose output is likely to change if a single bit of the input is flipped -- for example, PARITY. While prior work has established that transformers exhibit a bias toward functions with low average sensitivity, the precise mechanism underlying this bias remains poorly understood. To shed light on this phenomenon, we study the geometry of transformers' parameter space. We show that sensitive functions -- even when representable -- occupy a vanishingly small region that random initialization is very likely to miss. Specifically, we shift the focus from average sensitivity to the full sensitivity profile -- the distribution of sensitivity values across all inputs -- and prove that randomly initialized transformers almost surely compute functions which have low-sensitivity strings. Consequently, any function that lacks such strings is provably unlearnable.

Blanka Köver, Alexandra Butoi, Anej Svete +2

Department of Mathematics, ETH Zürich, Zürich, Switzerland · Department of Computer Science, ETH Zürich, Zürich, Switzerland · Department of Language Science and Technology, Saarland University, Saarbrücken, Germany.

Transformer Expressivity Boolean Function Learning Transformer

Ask PDF

May 27, 2026cs.LG

Learning High-Dimensional Parity Functions with Product Networks using Gradient Descent

Parity functions are fundamental Boolean operations with critical applications across machine learning, cryptography, and error correction. Yet, learning high-dimensional parity functions poses significant challenges: in a general setting, standard neural network architectures typically require exponential sample complexity, making gradient-based optimization intractable for large number of inputs

N

. We demonstrate that compact product-based neural architectures combined with stochastic data sparsity (Bernoulli inputs with

p_e \leq 1/N

) and appropriate hyperparameter choice enable efficient parity learning, with theoretical guarantees of convergence. Experiments validate our theory across dimensions up to

N = 100{,}000

, with empirical evidence showing optimal hyperparameter choices for

p_e

and learning rate

α

, as well as polynomial complexity scaling laws. This work establishes fundamental connections between architectural inductive bias and data sparsity, opening new possibilities for neural arithmetic, structured reasoning, binary neural networks, and machine learning applied to automated protocol discovery.

Guillaume Larue, Louis-Adrien Dufrène, Quentin Lampin +2

Orange Research, Meylan, France · Télécom Paris, Institut Polytechnique de Paris, Palaiseau, France · Télécom Paris, Institut Polytechnique de Paris, Palaiseau, France.

Boolean Function Learning Neural Network Optimization

Ask PDF

May 26, 2026cs.DS

Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginals

We study the problem of computationally efficient proper agnostic learning of multidimensional concept classes under the Gaussian distribution. In this setting, given i.i.d. labeled samples from an unknown distribution over

\mathbb{R}^d \times \{\pm 1\}

whose marginal on

\mathbb{R}^d

is Gaussian, the goal is to output a hypothesis from a target class

\mathcal{F}

whose 0-1 loss is within

ε

of that of the best classifier in

\mathcal{F}

. We give the first efficient proper agnostic learning algorithm for arbitrary Boolean functions of

K

halfspaces under Gaussian marginals. Our algorithm runs in time

d^{O(K^2 \log(1/ε)/ε^2)} + (K/ε)^{O(K^3/ε^{2.5})}

. Prior to our work, the only known algorithm for

K \geq 2

was brute-force search, with run-time exponential in

d

. Moreover, the dependence of our run-time on the dimension

d

matches that of the best known improper learning algorithm, namely

d^{\widetilde{O}(K^2/ε^2)}

. For the special case of a single halfspace (

K=1

), the best previous run-time was

d^{O(1/ε^4)} + (1/ε)^{O(1/ε^6)}

. Our algorithm improves this to

d^{O(1/ε^2)} + (1/ε)^{O(1/ε^{2.5})}

. Once again, the dependence on

d

matches that of the best known improper algorithm, namely

d^{O(1/ε^2)}

. Furthermore, the dependence of our run-time on the dimension

d

is essentially optimal in the statistical query model.

Sergei Tikhonov, Arsen Vasilyan

UT Austin

Boolean Function Learning Statistical Learning Theory

Ask PDF

May 20, 2026cs.LG

A Sharper Picture of Generalization in Transformers

We study transformers' generalization behavior on boolean domains from the perspective of the Fourier spectra of their target functions. In contrast to prior work (Edelman et al., 2022; Trauger & Tosh, 2024), which derived generalization bounds from Rademacher complexity, we investigate the feasibility of obtaining generalization bounds via PAC-Bayes theory. We show that sparse spectra concentrated on low-degree components enable low-sharpness constructions with good generalization properties. Our idea is to show the existence of flat minima implementing any boolean function of sparsity no greater than the context length, and then apply a PAC-Bayes bound to an idealized low-sharpness learner, resulting in a non-vacuous generalization bound. We use this to give a formal account of why chain-of-thought improves generalization for high-degree target functions, and show that the complexity parameters in our bound can be efficiently estimated via property testing. We evaluate predictions empirically and conduct a mechanistic interpretability study to support the realism of our theoretical construction in real transformers.

Paul Lintilhac, Sair Shaikh

Thayer School of Engineering Dartmouth College · Dartmouth College

Neural Network Generalization PAC-Bayesian Generalization Bounds Boolean Function Learning

Ask PDF

May 17, 2026cs.DS

Iterative Chow Filtering for Learning with Distribution Shift

Recent work due to Goel et al. gave the first efficient algorithms for learning with distribution shift in the challenging PQ framework. In this setting, a learner receives labeled training examples, unlabeled test examples, and must make correct predictions on the test set but is allowed to abstain from predicting on out-of-distribution points. Their results rely on

{\cal L}_2

sandwiching approximations, a strong requirement that leads to poor bounds for several basic function classes such as DNF formulas. Here, we show that the weaker notion of

{\cal L}_1

sandwiching suffices for efficient PQ learning. As a consequence, we obtain the first quasipolynomial-time PQ learning algorithm for DNFs under the uniform distribution and essentially match the guarantees known for ordinary PAC learning. More broadly, our bounds provide exponential improvements for several classes including constant depth circuits and constant degree polynomial threshold functions. Our main technical ingredient is Iterative Chow Filtering, a new procedure that uses low-degree Chow parameters to identify and remove test points incompatible with the training distribution.

Gautam Chandrasekaran, Georgios Gkrinias, Adam R. Klivans +2

UT Austin

Distribution Shift Robustness Boolean Function Learning

Ask PDF

May 12, 2026cs.AI

BoolXLLM: LLM-Assisted Explainability for Boolean Models

Interpretable machine learning aims to provide transparent models whose decision-making processes can be readily understood by humans. Recent advances in rule-based approaches, such as expressive Boolean formulas (BoolXAI), offer faithful and compact representations of model behavior. However, for non-technical stakeholders, main challenges remain in practice: (i) selecting semantically meaningful features and (ii) translating formal logical rules into accessible explanations. In this work, we propose BoolXLLM , as a hybrid framework that integrates Large Language Models (LLMs) into the end-to-end pipeline of Boolean rule learning. We augment BoolXAI , an expressive Boolean rule-based classifier, with LLMs at three critical stages: (1) feature selection, where LLMs guide the identification of domain-relevant variables; (2) threshold recommendation, where LLMs propose semantically meaningful discretization strategies for numerical features; and (3) rule compression and interpretation, where Boolean rules are translated into natural language explanations at both global and local levels. This integration bridges formal, faithful explanations with human-understandable narratives. This allows build an explainable AI system that is both theoretically grounded and accessible to non-experts. Early empirical results demonstrate that LLM-assisted pipelines improve interpretability while maintaining competitive predictive performance. Our work highlights the promise of combining symbolic reasoning with language-based models for human-centered explainability.

Du Cheng, Serdar Kadioglu, Xin Wang

AI Center of Excellence, Fidelity Investments, MA, USA · Department of Computer Science, Brown University, RI, USA

Explainable Artificial Intelligence Boolean Function Learning Interpretable ML

Ask PDF

May 9, 2026cs.LG

Fitting Multilinear Polynomials for Logic Gate Networks

We study learnable logic gate networks that stack layers of 2-input Boolean gates to build combinational circuits. Every 2-input gate has a unique multilinear polynomial with 4 coefficients, so the 16 Boolean gates form a codebook of prototypes in a 4-dimensional space, reducing training to a vector-quantization problem. The baseline method, Soft-Mix, learns a 16-dimensional softmax over gate identities, but the codebook has rank~4: 11 of 15 simplex directions carry nullspace gradient, and at uniform initialization the backward signal vanishes exactly. We prove that no affine product reparameterization fixes the resulting interaction-coefficient starvation under STE, and show that the covariance Jacobian of soft-VQ selection bypasses it by coupling the starved coefficient to the always-active constant channel. Working in the 4-dimensional polynomial space reduces each neuron from 16 to 4 parameters. On seven datasets, at least one 4-parameter method matches or exceeds Soft-Mix on every dataset; the CovJac advantage over STE grows monotonically with interaction demand across all seven datasets. At depth, Soft-Mix collapses (

-37.3

pp on CIFAR-10 at 12 layers) while CovJac holds (

-0.5

pp on CIFAR-10, stable on MNIST).

Youngsung Kim

Department of AI; and Department of ECE, Inha University

Boolean Function Learning Neural Network Optimization Vector Quantization

Ask PDF

May 8, 2026cs.LG

Learning Large-Scale Modular Addition with an Auxiliary Modulus

Learning parity functions, more general modular addition, is a challenging machine learning task due to its input sensitivity. A recent study substantially scaled modular addition learning in both the number of summands and the modulus. Its key idea is to increase zeros in training sequences, reducing the effective number of summands and thus controlling training difficulty; however, this induces covariate shift between training and test input distributions. This study theoretically and empirically analyzes this side effect and proposes a covariate-shift-free method for modular addition. Specifically, we introduce an auxiliary modulus

Kq

during training, which reduces wrap-around frequency and problem difficulty while preserving the same input distribution across training and testing. Experiments show strong scalability and sample efficiency: even for large input length

N

, large modulus

q

, and small datasets -- where the sparse method fails to learn -- our method achieves equal or better match accuracy and relaxed

τ

-accuracy. For example, at

N=64

and

q=974269

, our method trained on 100K samples achieves

97.0\%

τ

-accuracy at

τ=0.05

, while the sparse method achieves only

9.5\%

with the same data size and

93.9\%

even when extended to 1M samples.

Hanato Kikuchi, Ryosuke Masuya, Kazuhiko Kawamoto +1

Chiba University · National Institute of Informatics

Boolean Function Learning Distribution Shift Covariate Shift Modular Arithmetic Data-Efficient Learning

Ask PDF

May 4, 2026cs.LG

A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces

We study the complexity of smoothed agnostic learning of halfspaces on

\{\pm 1\}^n

under uniform marginals in the model of~\cite{KM25}, where each input coordinate is independently flipped with probability

σ\in (0, {1}/{2})

. We show that

L^1

polynomial regression achieves runtime and sample complexity

\tilde{O}(n^{O(\log(1/\varepsilon)/σ)})

, and prove a nearly matching Statistical Query complexity lower bound of

n^{Ω(\log(1+σ/\varepsilon^2)/σ)}

. This complements the recent work of~\cite{DK26}, which established analogous bounds in the continuous setting under Gaussian marginals.

Tim Sinen

University of Bonn, Germany

Boolean Function Learning Statistical Learning Theory

Ask PDF

May 2, 2026cs.LG

The Banach-Butterfly Invariant: Influence-Adaptive Walsh Geometry for Ternary Polynomial Threshold Functions

We introduce the Banach-Butterfly Invariant (BBT), an influence-adaptive Banach geometry on the Walsh-Hadamard butterfly factorization. For a Boolean function

f:\{-1,+1\}^n\to\{-1,+1\}

with coordinate influences

\mathrm{Inf}_\ell(f)

, BBT assigns exponent

p_\ell = 1+\mathrm{Inf}_\ell(f)

to butterfly layer

\ell

, yielding the contraction invariant

μ(f)=\prod_\ell 2^{-\mathrm{Inf}_\ell/(1+\mathrm{Inf}_\ell)}

. We prove a Jensen lower bound

\log_2μ(f) \ge -I(f)/(1+I(f)/n)

and that

μ

is strictly Schur-convex in the influence vector (modulo permutation), giving scaling classes

μ\sim 2^{-n/2}

(parity),

2^{-Θ(\sqrt{n})}

(majority),

2^{-1/2}

(dictators).

\log_2μ

is rational but not polynomial in the Fourier coefficients while

μ

is algebraic, and

μ

separates functions with identical total influence (122 pairs at

n=3

). Using the certified

n \le 4

ternary Walsh-threshold universe from a companion synthesis manuscript as a finite testbed, we compute exact MILP minimum-support certificates for all 65,536 Boolean functions at

n=4

(mean 6.42, max 9, all-odd by a parity argument) and on 10,000 of the 616,126 NPN-canonical representatives we enumerate at

n=5

(matching OEIS A000370). Conditional Spearman

ρ(μ,|\mathrm{supp}|)

at fixed total influence is

+0.571

in the largest stratum at

n=4

but reverses to

-0.38

n=5

under both function-uniform and NPN-canonical sampling:

μ

is a valid Schur-convex concentration invariant, not a universal monotone predictor of minimum support across

n

. A companion application paper validates a real-valued WHT activation-energy proxy inspired by this theory on five pretrained LLMs at W2A16, cutting wikitext-2 perplexity by 15-58% versus vanilla auto-round; the transfer from Boolean theory to the real-valued proxy is qualitative, not formal.

Gorgi Pavlov

Lehigh University · Johnson and Johnson

Boolean Function Learning

Ask PDF

Mar 8, 2026cs.LG

TT-Sparse: Learning Sparse Rule Models with Differentiable Truth Tables

Interpretable machine learning is essential in high-stakes domains where decision-making requires accountability, transparency, and trust. While rule-based models offer global and exact interpretability, learning rule sets that simultaneously achieve high predictive performance and low, human-understandable complexity remains challenging. To address this, we introduce TT-Sparse, a flexible neural building block that leverages differentiable truth tables as nodes to learn sparse, effective connections. A key contribution of our approach is a new soft TopK operator with straight-through estimation for learning discrete, cardinality-constrained feature selection in an end-to-end differentiable manner. Crucially, the forward pass remains sparse, enabling efficient computation and exact symbolic rule extraction. As a result, each node (and the entire model) can be transformed exactly into compact, globally interpretable DNF/CNF Boolean formulas via Quine-McCluskey minimization. Extensive empirical results across 28 datasets spanning binary, multiclass, and regression tasks show that the learned sparse rules exhibit superior predictive performance with lower complexity compared to existing state-of-the-art methods.

Hans Farrell Soegeng, Sarthak Ketanbhai Modi, Thomas Peyrin

School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore.

Boolean Function Learning Interpretable ML Neuro-Symbolic Reasoning

Ask PDF

Sep 25, 2025cs.DS

Actively Learning Halfspaces without Synthetic Data

In the classic point location problem, one is given an arbitrary dataset

X \subset \mathbb{R}^d

n

points with query access to an unknown halfspace

f : \mathbb{R}^d \to \{0,1\}

, and the goal is to learn the label of every point in

X

. This problem is extremely well-studied and a nearly-optimal

\widetilde{O}(d \log n)

query algorithm is known due to Hopkins-Kane-Lovett-Mahajan (FOCS 2020). However, their algorithm is granted the power to query arbitrary points outside of

X

(point synthesis), and in fact without this power there is an

Ω(n)

query lower bound due to Dasgupta (NeurIPS 2004). In this work our goal is to design efficient algorithms for learning halfspaces without point synthesis. To circumvent the

Ω(n)

lower bound, we consider learning halfspaces whose normal vectors come from a set of size

D

, and show tight bounds of

Θ(D + \log n)

. As a corollary, we obtain an optimal

O(d + \log n)

query deterministic learner for axis-aligned halfspaces, closing a previous gap of

O(d \log n)

vs.

Ω(d + \log n)

. In fact, our algorithm solves the more general problem of learning a Boolean function

f

over

n

elements which is monotone under at least one of

D

provided orderings. Our technical insight is to exploit the structure in these orderings to perform a binary search in parallel rather than considering each ordering sequentially, and we believe our approach may be of broader interest. Furthermore, we use our exact learning algorithm to obtain nearly optimal algorithms for PAC-learning. We show that

O(\min(D + \log(1/\varepsilon), 1/\varepsilon) \cdot \log D)

queries suffice to learn

f

within error

\varepsilon

, even in a setting when

f

can be adversarially corrupted on a

c\varepsilon

-fraction of points, for a sufficiently small constant

c

. This bound is optimal up to a

\log D

factor, including in the realizable setting.

Hadley Black, Kasper Green Larsen, Arya Mazumdar +2

Baruch College, CUNY · Aarhus University · University of California, San Diego

Query Complexity Boolean Function Learning Active Learning PAC Learning

Ask PDF

Aug 11, 2025cs.LG

Neural Logic Networks for Interpretable Classification

Traditional neural networks have an impressive classification performance, but what they learn cannot be inspected, verified or extracted. Neural Logic Networks on the other hand have an interpretable structure that enables them to learn a logical mechanism relating the inputs and outputs with AND and OR operations. We generalize these networks with NOT operations and biases that take into account unobserved data and develop a rigorous logical and probabilistic modeling in terms of concept combinations to motivate their use. We also propose a novel factorized IF-THEN rule structure for the model as well as a modified learning algorithm. Our method improves the state-of-the-art in Boolean networks discovery and is able to learn relevant, interpretable rules in tabular classification, notably on examples from the medical and industrial fields where interpretability has tangible value.

Vincent Perreault, Katsumi Inoue, Richard Labib +1

Department of Mathematics and Industrial Engineering Polytechnique Montréal · National Institute of Informatics, Tokyo

Boolean Function Learning Neural Network Interpretability Neurosymbolic Learning

Ask PDF

Momentum

Related topics

Latest papers 25