Computational Complexity

Authors and titles for recent submissions

• Fri, 17 Jan 2025
• Thu, 16 Jan 2025
• Wed, 15 Jan 2025
• Tue, 14 Jan 2025
• Mon, 13 Jan 2025

See today's new changes

Fri, 17 Jan 2025 (showing 1 of 1 entries )

[1] arXiv:2501.09545 [pdf, other]

Title: Hardness of clique approximation for monotone circuits

Jarosław Błasiok, Linus Meierhöfer

Subjects: Computational Complexity (cs.CC)

Thu, 16 Jan 2025 (showing 2 of 2 entries )

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

Title: Computing Game Symmetries and Equilibria That Respect Them

Emanuel Tewolde, Brian Hu Zhang, Caspar Oesterheld, Tuomas Sandholm, Vincent Conitzer

Comments: Long and updated version to the published paper in the Proceedings of the 39th Annual AAAI Conference on Artificial Intelligence (AAAI 2025). 24 pages, 2 figures, 1 table

Subjects: Computer Science and Game Theory (cs.GT); Artificial Intelligence (cs.AI); Computational Complexity (cs.CC); Multiagent Systems (cs.MA)

[3] arXiv:2501.08735 (cross-list from math.CO) [pdf, html, other]

Title: Matching Cut and Variants on Bipartite Graphs of Bounded Radius and Diameter

Felicia Lucke

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

Wed, 15 Jan 2025 (showing 2 of 2 entries )

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

Title: Towards the Pseudorandomness of Expander Random Walks for Read-Once ACC0 circuits

Emile Anand

Comments: 28 pages, 4 figures

Subjects: Computational Complexity (cs.CC)

[5] arXiv:2501.05283 (cross-list from math.GR) [pdf, html, other]

Title: On the complexity of epimorphism testing with virtually abelian targets

Murray Elder, Jerry Shen, Armin Weiß

Comments: 41 pages, 2 tables

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

Tue, 14 Jan 2025 (showing 5 of 5 entries )

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

Title: Determining distances and consensus between mutation trees

Luís Cunha, Jack Kuipers, Thiago Lopes

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

[7] arXiv:2501.06574 [pdf, other]

Title: Col is PSPACE-complete on Triangular Grids

Kyle Burke, Craig Tennenhouse

Comments: 10 pages, 16 figures

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

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

Title: Stable Set Polytopes with Rank $|V(G)|/3$ for the Lov\'{a}sz--Schrijver SDP Operator

Yu Hin Au, Levent Tunçel

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

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

Title: On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective

Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song, Wei Wang, Jiahao Zhang

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

[10] arXiv:2501.06427 (cross-list from cond-mat.dis-nn) [pdf, html, other]

Title: Strong Low Degree Hardness for Stable Local Optima in Spin Glasses

Brice Huang, Mark Sellke

Subjects: Disordered Systems and Neural Networks (cond-mat.dis-nn); Computational Complexity (cs.CC); Mathematical Physics (math-ph); Probability (math.PR)

Mon, 13 Jan 2025 (showing 1 of 1 entries )

[11] arXiv:2501.05638 [pdf, other]

Title: Mim-Width is paraNP-complete

Benjamin Bergougnoux, Édouard Bonnet, Julien Duron

Comments: 27 pages, 9 figures

Subjects: Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS); Combinatorics (math.CO)