Copertina

Certifiable Boolean Reasoning Is Universal

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Li, Wenhao, Kratsios, Anastasis, Ghoukasian, Hrad, Zvigelsky, Dennis
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Computational Complexity Machine Learning
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

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

Differentially Private Fair Binary Classifications
di: Ghoukasian, Hrad, et al.
Pubblicazione: (2024)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Proximity to Losslessly Compressible Parameters
di: Farrugia-Roberts, Matthew
Pubblicazione: (2023)