Computational Complexity

Authors and titles for recent submissions

• Tue, 5 May 2026
• Mon, 4 May 2026
• Fri, 1 May 2026
• Thu, 30 Apr 2026
• Wed, 29 Apr 2026

See today's new changes

Tue, 5 May 2026 (showing 11 of 11 entries )

[1] arXiv:2605.02845 [pdf, html, other]

Title: The Complexity of Stoquastic Sparse Hamiltonians

Alex B. Grilo, Marios Rozos

Subjects: Computational Complexity (cs.CC); Quantum Physics (quant-ph)

[2] arXiv:2605.02174 [pdf, html, other]

Title: Solution independence and self-referential instances

Guangyan Zhou, Bin Wang, Jianxin Wang, Ke Xu

Comments: 19 pages, 1 figure

Subjects: Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)

[3] arXiv:2605.01038 [pdf, html, other]

Title: Lower Bounds for Approximate Sign Rank

Riju Bindu, Hamed Hatami, Hasti Karimi, Robert Robere

Subjects: Computational Complexity (cs.CC)

[4] arXiv:2605.00995 [pdf, html, other]

Title: On Sampling Lower Bounds for Polynomials

Mohammad Mahdi Khodabandeh, Igor Shinkar

Subjects: Computational Complexity (cs.CC); Combinatorics (math.CO)

[5] arXiv:2605.00947 [pdf, html, other]

Title: Termination of Real Linear Loops

Eike Neumann, Margret Tembo

Subjects: Computational Complexity (cs.CC); Logic in Computer Science (cs.LO)

[6] arXiv:2605.00917 [pdf, html, other]

Title: Tensor Spectral Threshold is $\exists\mathbb{R}$-Hard

Angshul Majumdar

Subjects: Computational Complexity (cs.CC); Signal Processing (eess.SP)

[7] arXiv:2605.02057 (cross-list from quant-ph) [pdf, html, other]

Title: Exponential speedups in fault-tolerant processing of quantum experiments

Ishaan Kannan, Harald Putterman, Jordan Cotler

Comments: 5+48 pages, 4 figures

Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC); Information Theory (cs.IT)

[8] arXiv:2605.01637 (cross-list from cs.LG) [pdf, html, other]

Title: The Banach-Butterfly Invariant: Influence-Adaptive Walsh Geometry for Ternary Polynomial Threshold Functions

Gorgi Pavlov

Comments: 21 pages, 3 figures. Theory paper; LLM-application companion in preparation. Code, certificates, and 616,126 NPN-canonical n=5 representatives in supplementary repository

Subjects: Machine Learning (cs.LG); Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Combinatorics (math.CO)

[9] arXiv:2605.01578 (cross-list from cs.DS) [pdf, html, other]

Title: A fine-grained dichotomy for the center problem on Gromov hyperbolic graphs

Guillaume Ducoffe

Comments: Full version of an ICALP'26 paper

Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)

[10] arXiv:2605.00953 (cross-list from cs.IT) [pdf, html, other]

Title: Information Accessibility Limits in Structured NP Search

Jing-Yuan Wei

Comments: 22 pages. Includes appendices with explicit constructions and numerical examples

Subjects: Information Theory (cs.IT); Computational Complexity (cs.CC); Optimization and Control (math.OC)

[11] arXiv:2605.00834 (cross-list from cs.LG) [pdf, html, other]

Title: Polynomial-Time Optimal Group Selection via the Double-Commutator Eigenvalue Problem

Mitchell A. Thornton

Subjects: Machine Learning (cs.LG); Computational Complexity (cs.CC); Information Theory (cs.IT)

Mon, 4 May 2026 (showing 1 of 1 entries )

[12] arXiv:2605.00594 (cross-list from math.OC) [pdf, html, other]

Title: On the Distribution of Unweighted Minimum Knapsack Instances with Large SOS Rank

Adam Kurpisz, Lucas Slot, Mikhail Zaytsev

Subjects: Optimization and Control (math.OC); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)

Fri, 1 May 2026 (showing 9 of 9 entries )

[13] arXiv:2604.28172 [pdf, html, other]

Title: Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size

Susanna F. de Rezende, David Engström, Yassine Ghannane, Kilian Risse

Subjects: Computational Complexity (cs.CC)

[14] arXiv:2604.28019 [pdf, other]

Title: On the Principal Minor Expansion and Complexity of the Symmetrized Determinant

Sanyam Agarwal, Markus Bläser, Mridul Gupta

Subjects: Computational Complexity (cs.CC)

[15] arXiv:2604.27787 [pdf, html, other]

Title: Toward a Characterization of Simulation Between Arithmetic Theories

Hunter Monroe

Subjects: Computational Complexity (cs.CC); Logic (math.LO)

[16] arXiv:2604.27336 [pdf, html, other]

Title: Strongly Refuting Random CSP without Literals

Siu On Chan, Tommaso d'Orsi, Jeff Xu

Subjects: Computational Complexity (cs.CC)

[17] arXiv:2604.26972 [pdf, html, other]

Title: How Hard Is Continuous Clustering? Lower Bounds from the Existential Theory of the Reals

Angshul Majumdar

Subjects: Computational Complexity (cs.CC); Machine Learning (cs.LG)

[18] arXiv:2604.28186 (cross-list from cs.GT) [pdf, html, other]

Title: Computing Equilibrium beyond Unilateral Deviation

Mingyang Liu, Gabriele Farina, Asuman Ozdaglar

Subjects: Computer Science and Game Theory (cs.GT); Artificial Intelligence (cs.AI); Computational Complexity (cs.CC); Machine Learning (cs.LG); Theoretical Economics (econ.TH)

[19] arXiv:2604.27886 (cross-list from quant-ph) [pdf, html, other]

Title: Unentangled stoquastic Merlin-Arthur proof systems: the power of unentanglement without destructive interference

Yupan Liu, Pei Wu

Comments: 72 pages, 3 figures, 6 protocols, and 1 algorithm. Abstract shortened due to the arXiv length restriction

Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC)

[20] arXiv:2604.27645 (cross-list from cs.DS) [pdf, html, other]

Title: An Exact 56-Addition, Rank-23 Scheme for General 3*3 Matrix Multiplication

Yinqi Sun

Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)

[21] arXiv:2604.27276 (cross-list from cs.GT) [pdf, html, other]

Title: Fisher Markets with Approximately Optimal Bundles and the Need for a PCP Theorem for PPAD

Argyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis Melissourgos

Subjects: Computer Science and Game Theory (cs.GT); Computational Complexity (cs.CC)

Thu, 30 Apr 2026 (showing 3 of 3 entries )

[22] arXiv:2604.26179 [pdf, html, other]

Title: Hard-to-Sample Distributions from Robust Extractors

Farzan Byramji, Daniel M. Kane, Jackson Morris, Anthony Ostuni

Subjects: Computational Complexity (cs.CC)

[23] arXiv:2604.26921 (cross-list from quant-ph) [pdf, html, other]

Title: En Route to a Standard QMA1 vs. QCMA Oracle Separation

David Miloschewsky, Supartha Podder, Dorian Rudolph

Comments: 25 pages

Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC)

[24] arXiv:2604.26900 (cross-list from quant-ph) [pdf, html, other]

Title: Strict Hierarchy for Quantum Channel Certification to Unitary

Kean Chen, Qisheng Wang, Zhicheng Zhang

Comments: 13 pages, 3 algorithms

Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)

Wed, 29 Apr 2026 (showing 4 of 4 entries )

[25] arXiv:2604.25734 (cross-list from cs.DS) [pdf, html, other]

Title: Clustering Permutations under the Ulam Metric: A Parameterized Complexity Study

Tian Bai, Fedor V. Fomin, Petr A. Golovach, Yash Hiren More, Simon Wietheger

Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)

[26] arXiv:2604.25251 (cross-list from math.LO) [pdf, other]

Title: From Gödel incompleteness to the consistency of circuit lower bounds

Albert Atserias, Moritz Müller

Subjects: Logic (math.LO); Computational Complexity (cs.CC)

[27] arXiv:2604.24879 (cross-list from math.AG) [pdf, html, other]

Title: Unrestrictions and concise secant varieties

Jakub Jagiełła, Joachim Jelisiejew

Comments: Intro 10 pages, comments welcome!

Subjects: Algebraic Geometry (math.AG); Computational Complexity (cs.CC)

[28] arXiv:2604.10873 (cross-list from cs.AI) [pdf, html, other]

Title: A Quantitative Definition of Intelligence

Kang-Sin Choi

Comments: 27 pages; v2: syntax is semantics

Subjects: Artificial Intelligence (cs.AI); Computational Complexity (cs.CC); Machine Learning (cs.LG)