Cover Image

Certifiable Boolean Reasoning Is Universal

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Li, Wenhao, Kratsios, Anastasis, Ghoukasian, Hrad, Zvigelsky, Dennis
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Quantifying The Limits of AI Reasoning: Systematic Neural Network Representations of Algorithms
by: Kratsios, Anastasis, et al.
Published: (2025)

Optimal Fairness under Local Differential Privacy
by: Ghoukasian, Hrad, et al.
Published: (2025)

Differentially Private Fair Binary Classifications
by: Ghoukasian, Hrad, et al.
Published: (2024)

Statistical Guarantees for Reasoning Probes on Looped Boolean Circuits
by: Kratsios, Anastasis, et al.
Published: (2026)

Is In-Context Universality Enough? MLPs are Also Universal In-Context
by: Kratsios, Anastasis, et al.
Published: (2025)

Locally Optimal Private Sampling: Beyond the Global Minimax
by: Ghoukasian, Hrad, et al.
Published: (2025)

Learning-Augmented Algorithms for Boolean Satisfiability
by: Attias, Idan, et al.
Published: (2025)

Designing Universal Causal Deep Learning Models: The Case of Infinite-Dimensional Dynamical Systems from Stochastic Analysis
by: Galimberti, Luca, et al.
Published: (2022)

Hardness of Learning Boolean Functions from Label Proportions
by: Guruswami, Venkatesan, et al.
Published: (2024)

Provable Failure of Language Models in Learning Majority Boolean Logic via Gradient Descent
by: Chen, Bo, et al.
Published: (2025)

Polynomial Scaling is Possible For Neural Operator Approximations of Structured Families of BSDEs
by: Furuya, Takashi, et al.
Published: (2024)

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers
by: Amiri, Alireza, et al.
Published: (2025)

Incremental Generation is Necessary and Sufficient for Universality in Flow-Based Modelling
by: Rouhvarzi, Hossein, et al.
Published: (2025)

Structure-Preserving Reconstruction of Convex Lipschitz Functionals on Hilbert Spaces from Finite Samples
by: Kratsios, Anastasis
Published: (2026)

Neural Snowflakes: Universal Latent Graph Inference via Trainable Latent Geometries
by: Borde, Haitz Sáez de Ocáriz, et al.
Published: (2023)

A Closer Look at Personalized Fine-Tuning in Heterogeneous Federated Learning
by: Chen, Minghui, et al.
Published: (2025)

Inference Scaling vs Reasoning: An Empirical Analysis of Compute-Optimal LLM Problem-Solving
by: AbdElhameed, Marwan, et al.
Published: (2024)

Generative Neural Operators of Log-Complexity Can Simultaneously Solve Infinitely Many Convex Programs
by: Kratsios, Anastasis, et al.
Published: (2025)

Constant Bit-size Transformers Are Turing Complete
by: Li, Qian, et al.
Published: (2025)

Limitations on Accurate, Trusted, Human-level Reasoning
by: Panigrahy, Rina, et al.
Published: (2025)

Bridging the Gap Between Approximation and Learning via Optimal Approximation by ReLU MLPs of Maximal Regularity
by: Hong, Ruiyang, et al.
Published: (2024)

Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete
by: Li, Qian, et al.
Published: (2026)

Chain of Thought Empowers Transformers to Solve Inherently Serial Problems
by: Li, Zhiyuan, et al.
Published: (2024)

Polyhedral Instability Governs Regret in Online Learning
by: Li, Yuetai, et al.
Published: (2026)

How Much Cache Does Reasoning Need? Depth-Cache Tradeoffs in KV-Compressed Transformers
by: Wang, Xiao
Published: (2026)

Have Large Language Models Learned to Reason? A Characterization via 3-SAT Phase Transition
by: Hazra, Rishi, et al.
Published: (2025)

NPHardEval: Dynamic Benchmark on Reasoning Ability of Large Language Models via Complexity Classes
by: Fan, Lizhou, et al.
Published: (2023)

Neural Algorithmic Reasoning for Hypergraphs with Looped Transformers
by: Huang, Zekai, et al.
Published: (2025)

How Hard Is Continuous Clustering? Lower Bounds from the Existential Theory of the Reals
by: Majumdar, Angshul
Published: (2026)

Spiky Rank and Its Applications to Rigidity and Circuits
by: Hambardzumyan, Lianna, et al.
Published: (2026)

Decision Tree Learning on Product Spaces
by: Moakahr, Arshia Soltani, et al.
Published: (2026)

Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation
by: Jacobs, Peter Matthew, et al.
Published: (2026)

On the Computational Hardness of Transformers
by: Saha, Barna, et al.
Published: (2026)

Hidden costs for inference with deep network on embedded system devices
by: Lee, Chankyu, et al.
Published: (2026)

Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension
by: Klivans, Adam R., et al.
Published: (2026)

On the Hardness of Learning Regular Expressions
by: Attias, Idan, et al.
Published: (2025)

Learnability of Parameter-Bounded Bayes Nets
by: Bhattacharyya, Arnab, et al.
Published: (2024)

A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers
by: Merrill, William, et al.
Published: (2025)

Low-Rank Matrix Approximation for Neural Network Compression
by: Cherukuri, Kalyan, et al.
Published: (2025)

Proximity to Losslessly Compressible Parameters
by: Farrugia-Roberts, Matthew
Published: (2023)