Tessera

Vincent Liew Associativity of Multiplication Is Hard for Resolution https://arxiv.org/abs/2610.08988

Yohan Finet, Victor Drouin-Touchette Separating comb inequalities is NP-hard https://arxiv.org/abs/2610.09065

Nicolas Bousquet, Remy El Sabeh, Amer E. Mouawad, Naomi Nishimura On the complexity of the single-move labeled token routing problem https://arxiv.org/abs/2610.09084

Markel Zubia, Nils Jansen On the Computational Complexity of Hidden Markov Model Identification https://arxiv.org/abs/2610.09104

Jihan Wang Fine-Grained Hardness of Approximating Dynamic Time Warping https://arxiv.org/abs/2610.09233

Shuhong Gao Improving the Constant in the Aharonov--Regev Theorem https://arxiv.org/abs/2610.09290

Mingyu Lee, Sanghyun Lee, Kabgyun Jeong Optimal (Parallel) Spooky Pebbling on Binary Trees https://arxiv.org/abs/2610.09434

J. Andres Montoya The smallest programmable machine and the hardness of analyzing it https://arxiv.org/abs/2610.10399

Steven Heilman, Chris Jones, Giulio Malavolta Primal/Dual Method for the Grothendieck Constant https://arxiv.org/abs/2610.10477

Alex Meiburg $\exists \mathbb{R} \subseteq \textsf{CH}$ https://arxiv.org/abs/2610.10514

Oliver Korten Top-Down Lower Bounds for All Depths https://arxiv.org/abs/2609.38677

Eshan Chattopadhyay, Oren Renard, Nicholas Spooner Frustration Free Stoquastic Local Hamiltonian with Sub-Constant Gap is in NP https://arxiv.org/abs/2609.38910

Haoyu Wang, Pei Wu, Guangxu Yang Exponential Quantum Advantage in Numbers-on-Forehead Communication https://arxiv.org/abs/2609.40273

Jeremy Huang, Young Kun Ko, Chunhao Wang Quantum Fine-Grained Lower Bounds for SetDisjointness via Sub-Linear Reductions from 3SUM https://arxiv.org/abs/2609.40293

Paul Beame, Blake Holman, Niels Kornerup A Noise Operator Approach to Quantum Query Complexity and Time-Space Tradeoff Lower Bounds https://arxiv.org/abs/2609.40334

Dejan Delic, Ali Syed Maltsev Constraint Satisfaction Problems and Deterministic Logspace With Counting https://arxiv.org/abs/2609.30757

Sebastian Ben Daniel Linear Certificates for Membership Comparability, Quadratic Barriers for Selectors https://arxiv.org/abs/2609.31053

Jean-Fran\c{c}ois Biasse, Giacomo Micheli, Benjamin Prada, Philip Waitkevich A search-to-decision reduction for the linear code equivalence problem https://arxiv.org/abs/2609.31517

Simon Mackenzie Lossless Hardness Condensation in Deterministic Communication Complexity https://arxiv.org/abs/2609.28691

Zhi-Long Chen (University of Maryland), Nicholas G. Hall (The Ohio State University) Strong NP-Hardness and Approximation Algorithm for Weighted Tardiness with Release Dates and Identical Processing Times https://arxiv.org/abs/2609.28751

Eshan Chattopadhyay, Pooya Hatami, Chin Ho Lee, Shachar Lovett, Avishay Tal, Emanuele Viola Exponential Correlation Bounds for Polynomials https://arxiv.org/abs/2609.28839

Daqing Wan, Jun Zhang NP-Hardness of Bounded Distance Decoding for Reed-Solomon Codes https://arxiv.org/abs/2609.29120

Sebastian Ben Daniel Constant-Probability Witness Isolation Implies $\mathrm{NP}\subseteq\mathrm{P/poly}$ https://arxiv.org/abs/2609.29302

Jizhou Guo An $n^2\log\log n$ Lower Bound for Permanent Circuits with Valid Division https://arxiv.org/abs/2609.29568

Kirill Osipov Step Recursion: Mixed Stride Spectra, Path Factorization, and Synchronization Geometry https://arxiv.org/abs/2609.29585

Bo Liu A New Gap Sequence for Shellsort: RL-Driven Algorithm Discovery Beyond $N^{4/3}$ https://arxiv.org/abs/2609.29881

Max G\"ottlicher, Lennard Hofmann, Christoph Niederbudde From FPT to W[P]: Classifying Zero Forcing, Power Domination and Their Variants https://arxiv.org/abs/2609.29966

Aaron Potechin, Jeff Xu Sharp Lovasz-Theta Bounds on Random Graphs https://arxiv.org/abs/2609.30064

Samruddhi Pednekar, Supartha Podder A General Composition Theorem for Approximate Degree https://arxiv.org/abs/2609.30139