Computational Complexity

Authors and titles for cs.CC in Mar 2024, skipping first 50

[51]  arXiv:2403.02968 (cross-list from quant-ph) [pdf, other]

Title: Hamiltonian Property Testing

Authors: Andreas Bluhm, Matthias C. Caro, Aadil Oufkir

Comments: 39+21 pages, 3 figures; improved upper bounds, added tolerant tester, corrected some typos

Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS); Information Theory (cs.IT); Machine Learning (cs.LG)

[52]  arXiv:2403.03237 (cross-list from quant-ph) [pdf, other]

Title: Efficiency of k-Local Quantum Search and its Adiabatic Variant on Random k-SAT

Authors: Mingyou Wu

Comments: 28 pages, 6 figures

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

[53]  arXiv:2403.03295 (cross-list from quant-ph) [pdf, ps, other]

Title: Proper vs Improper Quantum PAC learning

Authors: Ashwin Nayak, Pulkit Sinha

Comments: 23 Pages

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

[54]  arXiv:2403.03668 (cross-list from math.CO) [pdf, other]

Title: On the Structure of Hamiltonian Graphs with Small Independence Number

Authors: Nikola Jedličková, Jan Kratochvíl

Comments: arXiv admin note: text overlap with arXiv:2309.09228

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

[55]  arXiv:2403.04126 (cross-list from quant-ph) [pdf, other]

Title: Optimal Scheduling of Graph States via Path Decompositions

Authors: Samuel J. Elman, Jason Gavriel, Ryan L. Mann

Comments: 5 pages, 1 figure

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

[56]  arXiv:2403.04170 (cross-list from quant-ph) [pdf, ps, other]

Title: The Power of Lorentz Quantum Computer

Authors: Qi Zhang, Biao Wu

Comments: 14 pages, 9 figures

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

[57]  arXiv:2403.04841 (cross-list from quant-ph) [pdf, other]

Title: Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians

Authors: Harry Buhrman, Jonas Helsen, Jordi Weggemans

Comments: 39 pages, 1 figure

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

[58]  arXiv:2403.05418 (cross-list from math.CO) [pdf, ps, other]

Title: On balanceable and simply balanceable regular graphs

Authors: Milad Ahanjideh, Martin Milanič, Mary Servatius

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

[59]  arXiv:2403.05630 (cross-list from math.CO) [pdf, ps, other]

Title: The metric Menger problem

Authors: Júlia Baligács, Joseph MacManus

Comments: 9 pages, 2 figures. Comments welcome!

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

[60]  arXiv:2403.06694 (cross-list from math.CO) [pdf, ps, other]

Title: $C_{2k+1}$-coloring of bounded-diameter graphs

Authors: Marta Piecyk

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

[61]  arXiv:2403.08195 (cross-list from quant-ph) [pdf, ps, other]

Title: Efficiently verifiable quantum advantage on near-term analog quantum simulators

Authors: Zhenning Liu, Dhruv Devulapalli, Dominik Hangleiter, Yi-Kai Liu, Alicia J. Kollár, Alexey V. Gorshkov, Andrew M. Childs

Comments: 20 pages, 6 figures

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

[62]  arXiv:2403.12674 (cross-list from math.GR) [pdf, ps, other]

Title: Some properties of Higman-Thompson monoids and digital circuits

Authors: J.C. Birget

Comments: 59 p

Subjects: Group Theory (math.GR); Computational Complexity (cs.CC)

[63]  arXiv:2403.13084 (cross-list from quant-ph) [pdf, ps, other]

Title: The status of the quantum PCP conjecture (games version)

Authors: Anand Natarajan, Chinmay Nirkhe

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

[64]  arXiv:2403.13472 (cross-list from math.CO) [pdf, ps, other]

Title: A proof of Ollinger's conjecture: undecidability of tiling the plane with a set of $8$ polyominoes

Authors: Chao Yang, Zhujun Zhang

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

[65]  arXiv:2403.14556 (cross-list from math.OC) [pdf, other]

Title: Rescue Craft Allocation in Tidal Waters of the North and Baltic Sea

Authors: Tom Mucke, Alexander Renneke, Finn Seesemann, Felix Engelhardt

Comments: Code URL: this https URL

Subjects: Optimization and Control (math.OC); Computational Complexity (cs.CC); Discrete Mathematics (cs.DM)

[66]  arXiv:2403.14607 (cross-list from quant-ph) [pdf, other]

Title: Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth

Authors: Joel Rajakumar, James D. Watson, Yi-Kai Liu

Comments: 17 pages, 5 figures

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

[67]  arXiv:2403.15749 (cross-list from math.OC) [pdf, other]

Title: Horoballs and the subgradient method

Authors: Adrian S. Lewis, Genaro Lopez-Acedo, Adriana Nicolae

Subjects: Optimization and Control (math.OC); Computational Complexity (cs.CC); Machine Learning (cs.LG)

[68]  arXiv:2403.16671 (cross-list from math.GR) [pdf, ps, other]

Title: Twisted conjugacy in dihedral Artin groups I: Torus Knot groups

Authors: Gemma Crowe

Comments: Comments welcome!

Subjects: Group Theory (math.GR); Computational Complexity (cs.CC)

[69]  arXiv:2403.17766 (cross-list from math.ST) [pdf, ps, other]

Title: Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph

Authors: Xifan Yu, Ilias Zadik, Peiyuan Zhang

Subjects: Statistics Theory (math.ST); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)

[70]  arXiv:2403.19388 (cross-list from math.CO) [pdf, ps, other]

Title: Cosystolic Expansion of Sheaves on Posets with Applications to Good 2-Query Locally Testable Codes and Lifted Codes

Authors: Uriya A. First, Tali Kaufman

Comments: This subsumes sections 1-8 of arXiv:2208.01778. Final version. Comments are welcome

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