Computational Complexity

Authors and titles for cs.CC in Apr 2024

[1]  arXiv:2404.00006 [pdf, ps, other]

Title: A Critique of Chen's "The 2-MAXSAT Problem Can Be Solved in Polynomial Time"

Authors: Tran Duy Anh Le, Michael P. Reidy, Eliot J. Smith

Comments:

Subjects: Computational Complexity (cs.CC)

[2]  arXiv:2404.00812 [pdf, ps, other]

Title: No Complete Problem for Constant-Cost Randomized Communication

Authors: Yuting Fang, Lianna Hambardzumyan, Nathaniel Harms, Pooya Hatami

Comments: 24 pages

Subjects: Computational Complexity (cs.CC)

[3]  arXiv:2404.01080 [pdf, ps, other]

Title: A simplified proof of the CSP Dichotomy Conjecture and XY-symmetric operations

Authors: Dmitriy Zhuk

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

[4]  arXiv:2404.02912 [pdf, ps, other]

Title: Probabilistic Generating Circuits -- Demystified

Authors: Sanyam Agarwal, Markus Bläser

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

[5]  arXiv:2404.03842 [pdf, ps, other]

Title: The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs

Authors: Abhishek Dhawan, Yuzhou Wang

Comments: 52 pages. arXiv admin note: text overlap with arXiv:2010.06563 by other authors

Subjects: Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS); Combinatorics (math.CO); Probability (math.PR); Machine Learning (stat.ML)

[6]  arXiv:2404.03844 [pdf, ps, other]

Title: $Π_{2}^{P}$ vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem

Authors: Dmitriy Zhuk

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

[7]  arXiv:2404.04395 [pdf, ps, other]

Title: A Critique of Du's "A Polynomial-Time Algorithm for 3-SAT

Authors: Yumeng He, Matan Kotler-Berkowitz, Harry Liuson, Zeyu Nie

Subjects: Computational Complexity (cs.CC)

[8]  arXiv:2404.06427 [pdf, other]

Title: A universal sequence of tensors for the asymptotic rank conjecture

Authors: Petteri Kaski, Mateusz Michałek

Subjects: Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS); Algebraic Geometry (math.AG)

[9]  arXiv:2404.06513 [pdf, ps, other]

Title: Superpolynomial Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs

Authors: Pravesh K. Kothari, Peter Manohar

Subjects: Computational Complexity (cs.CC)

[10]  arXiv:2404.07026 [pdf, ps, other]

Title: Optimal Communication Complexity of Chained Index

Authors: Janani Sundaresan

Comments: 24 pages, 3 figures

Subjects: Computational Complexity (cs.CC)

[11]  arXiv:2404.07441 [pdf, ps, other]

Title: Near Optimal Alphabet-Soundness Tradeoff PCPs

Authors: Dor Minzer, Kai Zhe Zheng

Comments: STOC 2024, 91 pages

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

[12]  arXiv:2404.07606 [pdf, ps, other]

Title: Lifting with Inner Functions of Polynomial Discrepancy

Authors: Yahel Manor, Or Meir

Subjects: Computational Complexity (cs.CC)

[13]  arXiv:2404.07881 [pdf, other]

Title: Diagram Analysis of Iterative Algorithms

Authors: Chris Jones, Lucas Pesenti

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

[14]  arXiv:2404.07986 [pdf, ps, other]

Title: Trading Determinism for Noncommutativity in Edmonds' Problem

Authors: V. Arvind, Abhranil Chatterjee, Partha Mukhopadhyay

Subjects: Computational Complexity (cs.CC); Formal Languages and Automata Theory (cs.FL)

[15]  arXiv:2404.08158 [pdf, ps, other]

Title: On the Power of Interactive Proofs for Learning

Authors: Tom Gur, Mohammad Mahdi Jahanara, Mohammad Mahdi Khodabandeh, Ninad Rajgopal, Bahar Salamatian, Igor Shinkar

Comments: 58 pages, To appear in STOC 2024

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

[16]  arXiv:2404.08370 [pdf, other]

Title: Resolution Over Linear Equations: Combinatorial Games for Tree-like Size and Space

Authors: Svyatoslav Gryaznov, Sergei Ovcharov, Artur Riazanov

Subjects: Computational Complexity (cs.CC)

[17]  arXiv:2404.08870 [pdf, other]

Title: Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH

Authors: Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu

Subjects: Computational Complexity (cs.CC)

[18]  arXiv:2404.09236 [pdf, ps, other]

Title: The complexity of convexity number and percolation time in the cycle convexity

Authors: Carlos V.G.C. Lima, Thiago Marcilon, Pedro Paulo de Medeiros

Subjects: Computational Complexity (cs.CC)

[19]  arXiv:2404.09798 [pdf, other]

Title: The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture

Authors: Ambroise Baril, Miguel Couceiro, Victor Lagerkvist

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

[20]  arXiv:2404.10380 [pdf, other]

Title: PSPACE-Hard 2D Super Mario Games: Thirteen Doors

Authors: MIT Hardness Group, Hayashi Ani, Erik D. Demaine, Holden Hall, Matias Korman

Subjects: Computational Complexity (cs.CC)

[21]  arXiv:2404.10712 [pdf, other]

Title: Tetris with Few Piece Types

Authors: MIT Hardness Group, Erik D. Demaine, Holden Hall, Jeffery Li

Subjects: Computational Complexity (cs.CC)

[22]  arXiv:2404.10839 [pdf, other]

Title: Constant-Depth Arithmetic Circuits for Linear Algebra Problems

Authors: Robert Andrews, Avi Wigderson

Subjects: Computational Complexity (cs.CC); Symbolic Computation (cs.SC)

[23]  arXiv:2404.10961 [pdf, ps, other]

Title: Chernoff Bounds and Reverse Hypercontractivity on HDX

Authors: Yotam Dikstein, Max Hopkins

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

[24]  arXiv:2404.11709 [pdf, ps, other]

Title: Satisfiability of commutative vs. non-commutative CSPs

Authors: Andrei A. Bulatov, Stanislav Živný

Subjects: Computational Complexity (cs.CC); Logic in Computer Science (cs.LO); Quantum Physics (quant-ph)

[25]  arXiv:2404.13254 [pdf, other]

Title: Unambiguous and Co-Nondeterministic Computations of Finite Automata and Pushdown Automata Families and the Effects of Multiple Counters

Authors: Tomoyuki Yamakami

Comments: (A4, 10pt, 12 pages) A conference version of this paper will appear in the Proceedings of TAMC 2024

Subjects: Computational Complexity (cs.CC); Formal Languages and Automata Theory (cs.FL)