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

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.
Boolean threshold functions, neuron capacity, and memory retrieval
Sep 24, 2026Xinyuan XieBoolean Function Learning Neural Network Memorization
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.
Fitting and Learning Basis-Restricted Propositional Formulas
Sep 8, 2026Balder ten CateBoolean Function Learning Empirical Risk Minimization
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
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 VasilyanBoolean Function Learning Statistical Learning Theory
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
Lehigh University · Johnson and Johnson
TT-Sparse: Learning Sparse Rule Models with Differentiable Truth Tables
Mar 8, 2026Hans Farrell Soegeng, Sarthak Ketanbhai Modi, Thomas PeyrinBoolean Function Learning Interpretable ML
School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore.
Actively Learning Halfspaces without Synthetic Data
Sep 25, 2025Hadley Black, Kasper Green Larsen, Arya Mazumdar +2Query Complexity Boolean Function Learning
Baruch College, CUNY · Aarhus University · University of California, San Diego
Neural Logic Networks for Interpretable Classification
Aug 11, 2025Vincent Perreault, Katsumi Inoue, Richard Labib +1Boolean Function Learning Neural Network Interpretability
Department of Mathematics and Industrial Engineering Polytechnique Montréal · National Institute of Informatics, Tokyo

Oct 4, 2026, cs.LGJ/K move · Enter open · S save

Private Component-by-Component Learning

Dvir Karni, Eliad Tsfadia

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

Boolean Function Learning Privacy-Preserving ML

Open paper AskPDF arXiv

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)

Momentum

Related topics

Latest papers 25