001 Learning-Augmented and Randomized Algorithms for Line Aggregation with Delays arXiv Paper Tianhang Lu et al. Yesterday 002 Explicit Separations for One-Query Unitary Synthesis arXiv Paper Fangqi Dong et al. 2 days ago 003 Field Codes for Distributed Coupling Samplers and Certified Empirical Transport arXiv Paper Hung Mai et al. 2 days ago 004 Maximum Satisfiability of Simple Temporal Problems arXiv Paper Johannes K. Fichte et al. 5 days ago 005 Exponentially Fewer-Server PIR from Sparser $S$-Decoding Polynomials arXiv Paper A. Gupte, Seyoon Ragavan 7 days ago 006 Representative Sets in Propositional Abduction arXiv Paper J. Schmidt, Mohamed Maizia et al. Jul 23 007 The Dimension of Nonterminating Resampling Computations arXiv Paper Yunbei Xu Jul 20 008 Tight Sample Bounds for Renyi and Min-Entropy Estimation arXiv Paper Arman Adibi, Piotr Krysta Jul 18 009 Testing Distributions Against Bounded Distinguishers arXiv Paper Mark Bun, Rathin Desai et al. Jul 17 010 Random Parameter Noise Does Not Make Exact ReLU Verification Easy arXiv Paper Mojtaba Soltanalian Jul 15 011 Regularity as seen by Alice and Bob arXiv Paper Omid Yaghoubi, Mikolaj Boja'nczyk et al. Jul 15 012 Tropical Circuits with Scalar Multiplication Gates arXiv Paper Christoph Hertrich, Moritz Stargalla Jul 13 013 Computing with Stochastic Oracles in AI-Augmented Computation arXiv Paper Jie Wang Jul 8 014 Boosting with List-Decodable Codes arXiv Paper Addison Prairie, Li-Yang Tan Jul 7 015 Lower Bounds for PIR with Preprocessing from Blackbox Cryptography arXiv Paper Alexander Hoover, Giuseppe Persiano et al. Jul 7 016 When Does Tool Use Increase the Expressive Power of Finite-Precision Recurrent Models? arXiv Paper Nikola Zubic, Qian Li et al. Jul 7 017 On the Complexity of Low-Rank Matrix Signing and Entrywise Power Matrix Factorization arXiv Paper Nicolas Gillis et al. Jul 6 018 Complexity of Normalized Persistence Problems for Topological Data Analysis and Local Hamiltonians arXiv Paper Dominic Lowe, M. S. Kim et al. Jul 3 019 How to Avoid Debate: Scalable AI Safety via Doubly-Efficient Interactive Proofs arXiv Paper Liyan Chen, Y. Kalai et al. Jul 3 020 Optimal Stabilizer Testing and Learning with Limited Quantum Memory arXiv Paper Srinivasan Arunachalam, Louis Schatzki Jul 2 021 Witness Complexity of Short Descriptions: A Cryptographic Perspective arXiv Paper Fabio F. G. Buono Jun 30 022 Quantum Lazy Sampling and Path Recording for Any Group arXiv Paper Ben Foxman, Alex Lombardi et al. Jun 29 023 The Unverifiability of Artificial General Intelligence (AGI) Alignment, Static and Dynamic: From Trakhtenbrot's Wall to the Safety-Generality Tension arXiv Paper Jose Pascual Gumbau Mezquita Jun 26 024 The Observer World: A Cryptographic Extension of Impagliazzo's Five Worlds arXiv Paper Fabio F. G. Buono Jun 25 025 Discrepancy for Random Linear Codes arXiv Paper Dean Doron, T. Leonov et al. Jun 23 026 Token Complexity of Certifying Stochastic-Oracle Reliability arXiv Paper Jie Wang Jun 23 027 Learning-Augmented Algorithms for Online Vertex Cover arXiv Paper Tianhan Lu, Runtian Ren et al. Jun 22 028 Towards a Doubly Efficient IP=PSPACE arXiv Paper Liyan Chen, Matthew M. Hong et al. Jun 19 029 Some Complexity Results for Robustness Verification for Binarized Neural Networks arXiv Paper Harshit Goyal, Sudakshina Dutta Jun 17 030 Polynomial-Time Mistake-Bounded Language Generation arXiv Paper Hector Jimenez, Alexander Kozachinskiy et al. Jun 15 031 The Complexity of Min-Max Optimization for Quadratic Polynomials arXiv Paper Martino Bernasconi, Matteo Castiglioni et al. Jun 15 032 Learning with Simulators: No Regret in a Computationally Bounded World arXiv Paper S. Voitovych, Abhishek Shetty et al. Jun 11 033 The Program Is Still There: A Conservation Law for Program Discovery arXiv Paper J. M. Silva Jun 11 034 A Five-Plane Reference Architecture for Runtime Governance of Production AI Agents arXiv Paper K. Tallam Jun 10 035 Neuro-Relational Programs: Unifying Queries and Neural Computation over Structured Data arXiv Paper Arie Soeteman, B. T. Cate et al. Jun 10 036 Token Complexity Theory for AI-Augmented Computing arXiv Paper Jie Wang Jun 10 037 A Modular Approach to Succinct Arguments for QMA arXiv Paper James Bartusek, Jiahui Liu et al. Jun 3 038 Sharp Low-Degree Thresholds for Planted-vs-Planted Testing arXiv Paper Anda Skeja, Daniel G. Espinoza et al. Jun 3 039 Token Rankings are Unforgeable Language Model Signatures arXiv Paper Matthew Finlayson, Andreas Grivas et al. Jun 3 040 Collision Resistance of Single-Layer Neural Nets arXiv Paper Marco Benedetti, Andrej Bogdanov et al. Jun 2 041 Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete arXiv Paper Qian Li, Xinyu Mao et al. Jun 1 042 Revisiting Padded Transformer Expressivity: Which Architectural Choices Matter and Which Don't arXiv Paper Anej Svete, William Merrill et al. May 28 043 The Complexity of Verifying Feedforward Neural Networks in Quantised Settings arXiv Paper Eric Alsmann, Martin Lange et al. May 28 044 2-ASP(Q) programs with weak constraints: Complexity and efficient implementation arXiv Paper Andrea Cuteri, Giuseppe Mazzotta et al. May 26 045 A computational phase transition for learning-to-sample from Ising models arXiv Paper Andrej Risteski, T. Vuong May 23 046 The Deterministic Horizon: Impossibility Results as Design Specifications for Trustworthy AI Systems arXiv Paper Dongxing Guo May 21 047 A Measure-Theoretic Analysis of Reasoning: Structural Generalization and Approximation Limits arXiv Paper Yuyang Zhang, Yifu Zhang et al. May 19 048 Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation arXiv Paper P. Jacobs, Jeff M. Phillips May 19 049 The Expressive Power of Low Precision Softmax Transformers with (Summarized) Chain-of-Thought arXiv Paper Moritz Brosamle, Stephan Eckstein May 18 050 The Extremum Stack is a Minimal Sufficient Statistic for Rate-Independent Functionals: A Kolmogorov Complexity Characterisation arXiv Paper P. Frydrych May 16 051 Decision Tree Learning on Product Spaces arXiv Paper Arshia Soltani Moakahr, Faraz Ghahremani et al. May 13 052 Diversity of Extensions in Abstract Argumentation arXiv Paper J. Fichte, Markus Hecher et al. May 13 053 Enhanced and Efficient Reasoning in Large Learning Models arXiv Paper Leslie Valiant May 13 054 Min-Max Optimization Requires Exponentially Many Queries arXiv Paper Martino Bernasconi, Matteo Castiglioni et al. May 13 055 Polyhedral Instability Governs Regret in Online Learning arXiv Paper Yuetai Li, Fengqing Jiang et al. May 13 056 Clausal Deletion Backdoors for QBF: a Parameterized Complexity Approach arXiv Paper Leif Eriksson, Victor Lagerkvist et al. May 12 057 Hardness Amplification for (Sparse) LPN arXiv Paper Divesh Aggarwal, Rishav Gupta et al. May 11 058 Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Losses arXiv Paper Yuhan Ye May 11 059 The two clocks and the innovation window: When and how generative models learn rules arXiv Paper Binxu Wang, Emma Finn et al. May 11 060 CARMEN: CORDIC-Accelerated Resource-Efficient Multi-Precision Inference Engine for Deep Learning arXiv Paper Sonu Kumar, Mukul Lokhande et al. May 7