Computational Complexity

Authors and titles for recent submissions

• Mon, 6 Oct 2025
• Fri, 3 Oct 2025
• Thu, 2 Oct 2025
• Wed, 1 Oct 2025
• Tue, 30 Sep 2025

See today's new changes

Mon, 6 Oct 2025 (showing 4 of 4 entries )

[1] arXiv:2510.03143 [pdf, other]

Title: The Computational Complexity of Almost Stable Clustering with Penalties

Kamyar Khodamoradi, Farnam Mansouri, Sandra Zilles

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

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

Title: The Log-Rank Conjecture: New Equivalent Formulations

Lianna Hambardzumyan, Shachar Lovett, Morgan Shirley

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

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

Title: How Pinball Wizards Simulate a Turing Machine

Rosemary Adejoh, Andreas Jakoby, Sneha Mohanty, Christian Schindelhauer

Comments: 29 pages, 28 figures

Subjects: Computational Complexity (cs.CC)

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

Title: Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices

Pravesh K. Kothari, Jeff Xu

Comments: SODA'26

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

Fri, 3 Oct 2025 (showing 4 of 4 entries )

[5] arXiv:2510.01701 [pdf, other]

Title: Positive Univariate Polynomials: SOS certificates, algorithms, bit complexity, and T-systems

Matías Bender (TROPICAL), Philipp Di Dio, Elias Tsigaridas (OURAGAN)

Subjects: Computational Complexity (cs.CC)

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

Title: Formal Framework for Quantum Advantage

Harry Buhrman, Niklas Galke, Konstantinos Meichanetzidis

Comments: 5 pages, proofs in Appendix

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

[7] arXiv:2510.01931 (cross-list from cs.CG) [pdf, html, other]

Title: Minimum Selective Subset on Unit Disk Graphs and Circle Graphs

Bubai Manna

Subjects: Computational Geometry (cs.CG); Computational Complexity (cs.CC)

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

Title: Derandomised tensor product gap amplification for quantum Hamiltonians

Thiago Bergamaschi, Tony Metger, Thomas Vidick, Tina Zhang

Comments: 42 pages

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

Thu, 2 Oct 2025 (showing 4 of 4 entries )

[9] arXiv:2510.00759 (cross-list from math.LO) [pdf, html, other]

Title: Cubic incompleteness: Hilbert's tenth problem begins at degree three

Milan Rosko

Comments: We construct an explicit cubic Diophantine equation independent of PA. The result follows via Zeckendorf-based arithmetization and a reduction from the halting problem. 1+10+1 pages. Overall Difficulty: Assumes knowledge of Göodel numbering, MRDP theorem, algebra, complexity theory, primitive recursive functions, and formal theories P

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

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

Title: On Estimating the Quantum Tsallis Relative Entropy

Jinge Bao, Minbo Gao, Qisheng Wang

Comments: 44 pages, 1 table, 2 algorithms

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

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

Title: Privately Estimating Black-Box Statistics

Günter F. Steinke, Thomas Steinke

Subjects: Cryptography and Security (cs.CR); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG)

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

Title: Complexity and hardness of random peaked circuits

Yuxuan Zhang

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

Wed, 1 Oct 2025 (showing 6 of 6 entries )

[13] arXiv:2509.26248 [pdf, other]

Title: On Boolean PCSPs with Polynomial Threshold Polymorphisms

Katzper Michno

Subjects: Computational Complexity (cs.CC)

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

Title: Strong random unitaries and fast scrambling

Thomas Schuster, Fermi Ma, Alex Lombardi, Fernando Brandao, Hsin-Yuan Huang

Comments: 101 pages, 5 figures

Subjects: Quantum Physics (quant-ph); Strongly Correlated Electrons (cond-mat.str-el); Computational Complexity (cs.CC); Cryptography and Security (cs.CR); High Energy Physics - Theory (hep-th)

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

Title: The Guided Local Hamiltonian Problem for Stoquastic Hamiltonians

Gabriel Waite

Comments: 12 + 4 pages, 1 figure, 1 table

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

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

Title: On the Complexity of the Succinct State Local Hamiltonian Problem

Gabriel Waite, Karl Lin

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

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

Title: Physically-Motivated Guiding States for Local Hamiltonians

Gabriel Waite, Karl Lin, Samuel J Elman, Michael J Bremner

Comments: 16 + 21 pages, 3 + 8 figures

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

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

Title: Unitary synthesis with fewer T gates

Xinyu Tan

Comments: 13 pages

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

Tue, 30 Sep 2025 (showing 5 of 5 entries )

[19] arXiv:2509.24280 [pdf, html, other]

Title: An SoS Entropy Dichotomy via Windowed Hypercontractivity

Marko Lela

Comments: 41 pages, 2 tables. Part II (IECZ-II) of a series; complements IECZ-I (calibration/blueprint) and a planned IECZ-III (lifting to families). Compiles with pdfLaTeX; bibliography provided as .bbl. A minimal Python helper for packaging sources accompanies the submission; an archived code bundle for reproducibility will be released on Zenodo (DOI to be added in a revised version)

Subjects: Computational Complexity (cs.CC)

[20] arXiv:2509.23615 [pdf, html, other]

Title: Hardness and Algorithmic Results for Roman \{3\}-Domination

Sangam Balchandar Reddy

Comments: 20 pages, 4 figures

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

[21] arXiv:2509.22849 [pdf, html, other]

Title: Parameterized Hardness of Zonotope Containment and Neural Network Verification

Vincent Froese, Moritz Grillo, Christoph Hertrich, Moritz Stargalla

Comments: 19 pages, 5 figures

Subjects: Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Machine Learning (cs.LG); Neural and Evolutionary Computing (cs.NE)

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

Title: Two bases suffice for QMA1-completeness

Henry Ma, Anand Natarajan

Comments: 26 pages

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

[23] arXiv:2509.22995 (cross-list from cs.LO) [pdf, html, other]

Title: Structural Separation and Semantic Incompatibility in the P vs. NP Problem: Computational Complexity Analysis with Construction Defining Functionality

Yumiko Nishiyama

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