Skip to main content
We gratefully acknowledge support from the Simons Foundation, member institutions, and all contributors. Donate
arXiv logo
Cornell University Logo

Computational Complexity

Authors and titles for recent submissions

See today's new changes

Total of 18 entries
Showing up to 25 entries per page: fewer | more | all

Fri, 21 Jun 2024

No updates for this time period.

Wed, 19 Jun 2024 (showing 4 of 4 entries )

[1] arXiv:2406.12717 [pdf, html, other]
Title: Parameterized Shortest Path Reconfiguration
Nicolas Bousquet, Kshitij Gajjar, Abhiruk Lahiri, Amer E. Mouawad
Subjects: Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS); Combinatorics (math.CO)
[2] arXiv:2406.12176 [pdf, other]
Title: Assembly Theory and its Relationship with Computational Complexity
Christopher Kempes, Sara I. Walker, Michael Lachmann, Leroy Cronin
Comments: 36 pages, 4 figures, 1 table, and 81 references
Subjects: Computational Complexity (cs.CC)
[3] arXiv:2406.12322 (cross-list from math.GR) [pdf, html, other]
Title: Orbit-blocking words and the average-case complexity of Whitehead's problem in the free group of rank 2
Lucy Hyde, Siobhan O'Connor, Vladimir Shpilrain
Comments: 7 pages. arXiv admin note: text overlap with arXiv:2401.09218
Subjects: Group Theory (math.GR); Computational Complexity (cs.CC)
[4] arXiv:2406.12149 (cross-list from cs.DS) [pdf, html, other]
Title: Tight Streaming Lower Bounds for Deterministic Approximate Counting
Yichuan Wang
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)

Tue, 18 Jun 2024 (showing 4 of 4 entries )

[5] arXiv:2406.11628 [pdf, html, other]
Title: Treewidth Inapproximability and Tight ETH Lower Bound
Édouard Bonnet
Comments: 10 pages, 1 figure
Subjects: Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS); Combinatorics (math.CO)
[6] arXiv:2406.10476 [pdf, html, other]
Title: On $NP$ versus ${\rm co}NP$
Tianrong Lin
Comments: initial version; 20 pages; 2 figures; comments are welcome. arXiv admin note: substantial text overlap with arXiv:2110.06211
Subjects: Computational Complexity (cs.CC)
[7] arXiv:2406.11270 (cross-list from quant-ph) [pdf, html, other]
Title: Quantum Property Testing Algorithm for the Concatenation of Two Palindromes Language
Kamil Khadiev, Danil Serov
Comments: Proceedings of UCNC 2024
Journal-ref: LNCS, Vol. 14776, 2024
Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)
[8] arXiv:2406.10849 (cross-list from math.OC) [pdf, html, other]
Title: A parallel framework for graphical optimal transport
Jiaojiao Fan, Isabel Haasler, Qinsheng Zhang, Johan Karlsson, Yongxin Chen
Subjects: Optimization and Control (math.OC); Computational Complexity (cs.CC)

Mon, 17 Jun 2024

No updates for this time period.

Fri, 14 Jun 2024 (showing 10 of 10 entries )

[9] arXiv:2406.09351 [pdf, html, other]
Title: On the Expressibility of the Reconstructional Color Refinement
V. Arvind, Johannes Köbler, Oleg Verbitsky
Comments: 9 pages
Subjects: Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Machine Learning (cs.LG); Combinatorics (math.CO)
[10] arXiv:2406.08600 [pdf, html, other]
Title: A Refinement of the McCreight-Meyer Union Theorem
Matthew Fox, Chaitanya Karamchedu
Comments: 11 pages
Subjects: Computational Complexity (cs.CC)
[11] arXiv:2406.08500 [pdf, html, other]
Title: Newman's theorem via Carath\'eodory
Ali Mohammad Lavasani, Yaqiao Li, Mehran Shakerinava
Subjects: Computational Complexity (cs.CC)
[12] arXiv:2406.08499 [pdf, html, other]
Title: More Efficient $k$-wise Independent Permutations from Random Reversible Circuits via log-Sobolev Inequalities
Lucas Gretta, William He, Angelos Pelecanos
Comments: 19 pages
Subjects: Computational Complexity (cs.CC); Cryptography and Security (cs.CR)
[13] arXiv:2406.08497 [pdf, other]
Title: On the Simulation Power of Surface Chemical Reaction Networks
Yi-Xuan Lee, Ho-Lin Chen
Comments: 46 pages, 8 figures
Subjects: Computational Complexity (cs.CC); Emerging Technologies (cs.ET)
[14] arXiv:2406.08495 [pdf, html, other]
Title: A Brief Note on a Recent Claim About NP-Hard Problems and BQP
Michael C. Chavrimootoo
Comments: Comment on arXiv:2311.05624
Subjects: Computational Complexity (cs.CC)
[15] arXiv:2406.08494 [pdf, other]
Title: What If Turing Had Preceded G\"odel?
Sebastian Oberhoff
Subjects: Computational Complexity (cs.CC); Logic in Computer Science (cs.LO)
[16] arXiv:2406.08493 [pdf, other]
Title: Equivalence of Countable and Computable
Hantao Zhang
Comments: A preliminary version of this article was submitted to Conference of Computing Complexity (CCC-24)
Subjects: Computational Complexity (cs.CC)
[17] arXiv:2406.08490 [pdf, other]
Title: An origami Universal Turing Machine design
Michael Assis
Subjects: Computational Complexity (cs.CC)
[18] arXiv:2406.08489 [pdf, other]
Title: A Polynomial Time Algorithm for 3SAT
Robert Quigley
Comments: 23 pages, 6 figures
Subjects: Computational Complexity (cs.CC)
Total of 18 entries
Showing up to 25 entries per page: fewer | more | all