Boolean Function Learning

Follow this topic Ask about this topic

Boolean function learning asks how to recover a rule that maps binary inputs to binary outputs, and how well that rule will work on unseen cases. Approaches include Fourier and low-degree polynomial methods, threshold and circuit models, active or exact querying, and neural or symbolic rule learning. Researchers study guarantees in settings such as uniform, Gaussian, and correlated input distributions, including noisy labels and distribution shift. A central tension is that broad classes of rules may be statistically learnable but computationally difficult, while efficient or interpretable methods often rely on stronger assumptions about structure.

Latest papers

36 papers3 papers in the last four weeks, down 57% on the four weeks before. 0.0% of all new papers.

On the VC Dimension of Autoregressive Linear Threshold Functions
Oct 27, 2026Ilan Doron-Arad, Idan Mehalel, Elchanan MosselVC Dimension Boolean Function Learning
MIT · The Hebrew University
Optimizing Sparse Boolean Rule Networks using Mixed Integer Linear Programming
Oct 14, 2026Thomas Pammer, Johannes Fürnkranz, Markus SinnlBoolean Function Learning Interpretable ML
Institute for Application-Oriented Knowledge Processing (FAW), Johannes Kepler University Linz, Austria · LIT AI Lab, Johannes Kepler University Linz, Austria · Institute of Business Analytics & Technology Transformation/JKU Business School, Johannes Kepler University Linz, Austria
Private Component-by-Component Learning
Oct 4, 2026Dvir Karni, Eliad TsfadiaBoolean Function Learning Privacy-Preserving ML
Department of Computer Science and Artificial Intelligence, Bar-Ilan University.
Optimal Quantum-Classical Separations for Exact Learning
Sep 29, 2026Srinivasan Arunachalam, Amin Shiraz Gilani, Nikhil S. MandeBoolean Function Learning
IBM Research · QuICS, University of Maryland · University of Liverpool
Boolean threshold functions, neuron capacity, and memory retrieval
Sep 24, 2026Xinyuan XieBoolean Function Learning Neural Network Memorization
Counting and Covering in Nearest-Neighbour Representations of Boolean Functions
Sep 19, 2026Martin AnthonyVC Dimension Prototype-Based Classification
Department of Mathematics London School of Economics and Political Science, London, UK
Efficient Robust Learning at the Information-Theoretic Limit
Sep 15, 2026Adam R. Klivans, Konstantinos Stavropoulos, Sergei Tikhonov +1Boolean Function Learning Learning with Noisy Labels
UT Austin · Institute for Advanced Study · Aarhus University
Learning CNF Formulas from Uniform Random Solutions: Near-Tight Sample Complexity for Valiant's Algorithm
Sep 14, 2026Weiming Feng, Yixiao Yu, Yiyao ZhangBoolean Function Learning Sample Complexity
School of Computing and Data Science, The University of Hong Kong. · State Key Laboratory for Novel Software Technology, New Cornerstone Science Laboratory, Nanjing University.
Certifiably Interpretable Training of ReLU-MLPs for Boolean Tasks with Guaranteed Truth-Table Generalization
Sep 11, 2026Hrad Ghoukasian, Anastasis KratsiosInterpretable ML Neural Network Interpretability
Department of Electrical & Computer Engineering University of Toronto 40 St George St, Toronto, Ontario, M5S 2E4, Canada · Department of Mathematics McMaster University and Vector Institute 1280 Main Street West, Hamilton, Ontario, L8S 4K1, Canada
Fitting and Learning Basis-Restricted Propositional Formulas
Sep 8, 2026Balder ten CateBoolean Function Learning Empirical Risk Minimization
Representation Redundancy and Structural Complexity in Finite-Field Inversion
Sep 4, 2026Zheng Zhang, Na ZhangBoolean Function Learning
Department of Mathematics, Towson University, 7800 York Rd, Towson, MD 21204, USA.
A Learning Algorithm for Threshold Boolean Networks with Prescribed Fixed Points
Aug 18, 2026Gonzalo A. RuzBoolean Function Learning Gene Regulatory Network Inference
Facultad de Ingeniería y Ciencias, Universidad Adolfo Ibáñez, Santiago, Chile · Millennium Nucleus for Social Data Science (SODAS), Santiago, Chile · Millennium Nucleus in Data Science for Plant Resilience (PhytoLearning), Santiago, Chile +1
Algorithmic Separation between Constant-Depth and Logarithmic-Depth Neural Networks
Jul 28, 2026Yunwei Ren, Zihao Wang, Jason D. LeeBoolean Function Learning Neural Network Approximation Theory
Princeton University · Stanford University · University of California, Berkeley
Learning $\mathsf{AC}^0$ under Locally Sampleable Graphical Models
Jul 9, 2026Weiming Feng, Xiongxin Yang, Yixiao Yu +1Boolean Function Learning Low-Degree Polynomial Method
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.
Chamber geometry and specification numbers of Boolean threshold functions
Jun 28, 2026Martin AnthonyBoolean Function Learning
Department of Mathematics, London School of Economics
Teaching LLMs String Matching, Backtracking, and Error Recovery to Deduce Bases and Truth Tables for the Combinatorially Exploding Bit Manipulation Puzzles
Jun 22, 2026Prateek Agnihotri, Sanchit Jain, Prabhat Agnihotri +2Boolean Function Learning Program Synthesis
7th Place NVIDIA Nemotron Challenge Team
Tight $L_\infty$ Sample Complexity for Low-Degree and Sparse Boolean Polynomials
Jun 15, 2026Jasper van Doornmalen, Mathieu Molina, Victor Verdugo +1Surrogate Modeling Boolean Function Learning
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
Polynomial-Time Mistake-Bounded Language Generation
Jun 15, 2026Héctor Jimenez, Alexander Kozachinskiy, Vicente OpazoBoolean Function Learning
University of Chile · CENIA
Runtime Analysis of Cartesian Genetic Programming in Evolving Boolean Functions
Jun 14, 2026Duc-Cuong Dang, Roman Kalkreuth, Andre OprisBoolean Function Learning Genetic Programming
University of Passau, Passau, Germany · RWTH Aachen University, Aachen, Germany
Understanding the Parameter Space Geometry of Transformers Encoding Boolean Functions
Jun 7, 2026Blanka Köver, Alexandra Butoi, Anej Svete +2Transformer Expressivity Boolean Function Learning
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.
Learning High-Dimensional Parity Functions with Product Networks using Gradient Descent
May 27, 2026Guillaume Larue, Louis-Adrien Dufrène, Quentin Lampin +2Boolean Function Learning Neural Network Optimization
Orange Research, Meylan, France · Télécom Paris, Institut Polytechnique de Paris, Palaiseau, France · Télécom Paris, Institut Polytechnique de Paris, Palaiseau, France.
Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginals
May 26, 2026Sergei Tikhonov, Arsen VasilyanAgnostic Learning Boolean Function Learning
UT Austin
A Sharper Picture of Generalization in Transformers
May 20, 2026Paul Lintilhac, Sair ShaikhNeural Network Generalization PAC-Bayesian Generalization Bounds
Thayer School of Engineering Dartmouth College · Dartmouth College
Iterative Chow Filtering for Learning with Distribution Shift
May 17, 2026Gautam Chandrasekaran, Georgios Gkrinias, Adam R. Klivans +2Distribution Shift Robustness Boolean Function Learning
UT Austin
BoolXLLM: LLM-Assisted Explainability for Boolean Models
May 12, 2026Du Cheng, Serdar Kadioglu, Xin WangExplainable Artificial Intelligence Boolean Function Learning
AI Center of Excellence, Fidelity Investments, MA, USA · Department of Computer Science, Brown University, RI, USA
Fitting Multilinear Polynomials for Logic Gate Networks
May 9, 2026Youngsung KimBoolean Function Learning Neural Network Optimization
Department of AI; and Department of ECE, Inha University
Learning Large-Scale Modular Addition with an Auxiliary Modulus
May 8, 2026Hanato Kikuchi, Ryosuke Masuya, Kazuhiko Kawamoto +1Boolean Function Learning Distribution Shift
Chiba University · National Institute of Informatics
A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces
May 4, 2026Tim SinenBoolean Function Learning Statistical Learning Theory
University of Bonn, Germany
The Banach-Butterfly Invariant: Influence-Adaptive Walsh Geometry for Ternary Polynomial Threshold Functions
May 2, 2026Gorgi PavlovBoolean Function Learning Walsh-Hadamard Transform
Lehigh University · Johnson and Johnson
Learning $\mathsf{AC}^0$ Under Graphical Models
Apr 7, 2026Gautam Chandrasekaran, Jason Gaitonde, Ankur Moitra +1Low-Degree Polynomial Method Boolean Function Learning
University of Texas at Austin. · Duke University. · Massachusetts Institute of Technology.

Oct 27, 2026J/K move · Enter open · S save

On the VC Dimension of Autoregressive Linear Threshold Functions

Ilan Doron-Arad, Idan Mehalel, Elchanan Mossel

MIT · The Hebrew University

VC Dimension Boolean Function Learning Linear Classification Autoregressive Modeling

Open paper AskPDF arXiv

Linear threshold functions (LTFs) are a canonical class of Boolean predictors. In the autoregressive setting, the same LTF reads the most recent

d

bits, generates the next bit, and returns the bit produced after

T

steps. While the one-step class has VC dimension

d

, for general

T

the counting upper bound is

O(d^2)

. We prove that the VC dimension is

Θ(d^2)

for every

T\ge d^2

, resolving the quadratic gap for deterministic autoregressive LTFs. We then adapt the same technique to show an exponential separation between deterministic and stochastic autoregressive models: replacing the sign of LTFs by logistic sampling can increase the VC dimension of the final majority prediction class from quadratic to exponential in

d