We gratefully acknowledge support from
the Simons Foundation and member institutions.

Computational Complexity

Authors and titles for recent submissions

[ total of 19 entries: 1-19 ]
[ showing up to 25 entries per page: fewer | more ]

Fri, 1 Mar 2024

[1]  arXiv:2402.19365 [pdf, other]
Title: On Efficient Computation of DiRe Committees
Authors: Kunal Relia
Comments: single-column format. 33 pages. 26 Figures. 6 Tables. 4 Algorithms. 4 Theorems. 9 Lemmas/Lemmata. 2 Observations. 14 Definitions. 2 Examples. Reducing inequality is easier than expected. P=NP
Subjects: Computational Complexity (cs.CC); Computers and Society (cs.CY); Computer Science and Game Theory (cs.GT)
[2]  arXiv:2402.18790 (cross-list from quant-ph) [pdf, ps, other]
Title: The Power of Unentangled Quantum Proofs with Non-negative Amplitudes
Comments: 64 pages
Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC)

Thu, 29 Feb 2024

[3]  arXiv:2402.18276 [pdf, ps, other]
Title: Fractional Linear Matroid Matching is in quasi-NC
Subjects: Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS)
[4]  arXiv:2402.18263 (cross-list from cs.DS) [pdf, ps, other]
Title: Max-Cut with $ε$-Accurate Predictions
Comments: 18 pages
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)
[5]  arXiv:2402.18193 (cross-list from math.AG) [pdf, other]
Title: Counting points with Riemann-Roch formulas
Comments: 35 pages
Journal-ref: Revista de la Real Academia de Ciencias de Zaragoza 2024
Subjects: Algebraic Geometry (math.AG); Computational Complexity (cs.CC)
[6]  arXiv:2402.17805 (cross-list from cs.LG) [pdf, ps, other]
Title: Graph Neural Networks and Arithmetic Circuits
Subjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Computational Complexity (cs.CC)

Wed, 28 Feb 2024

[7]  arXiv:2402.17290 [pdf, ps, other]
Title: Tight Lower Bounds for Block-Structured Integer Programs
Subjects: Computational Complexity (cs.CC)

Tue, 27 Feb 2024

[8]  arXiv:2402.15995 [pdf, ps, other]
Title: Improved Hardness Results for Learning Intersections of Halfspaces
Authors: Stefan Tiegel
Subjects: Computational Complexity (cs.CC); Machine Learning (cs.LG); Statistics Theory (math.ST); Machine Learning (stat.ML)
[9]  arXiv:2402.16847 (cross-list from cs.DS) [src]
Title: The Art of Staying Ahead of Deadlines: Improved Algorithms for the Minimum Tardy Processing Time
Authors: Mihail Stoian
Comments: The runtime analysis is incorrect: the contribution of the processing times in [d_j - p_j, d_{j - 1}] is not taken into account. We thank N. Fischer for pointing this out
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)
[10]  arXiv:2402.16777 (cross-list from cs.CG) [pdf, other]
Title: Approximating Simplet Frequency Distribution for Simplicial Complexes
Comments: EuroCG2024
Subjects: Computational Geometry (cs.CG); Computational Complexity (cs.CC); Geometric Topology (math.GT)
[11]  arXiv:2402.16541 (cross-list from quant-ph) [pdf, other]
Title: Integer Programming Using A Single Atom
Comments: 12 pages, 7 figures
Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC); Optimization and Control (math.OC); Atomic Physics (physics.atom-ph)
[12]  arXiv:2402.16284 (cross-list from cs.ET) [pdf, other]
Title: Self-Assembly of Patterns in the abstract Tile Assembly Model
Subjects: Emerging Technologies (cs.ET); Computational Complexity (cs.CC); Computational Geometry (cs.CG)
[13]  arXiv:2402.16016 (cross-list from cs.GT) [pdf, ps, other]
Title: Complexity of Manipulation and Bribery in Premise-Based Judgment Aggregation with Simple Formulas
Subjects: Computer Science and Game Theory (cs.GT); Computational Complexity (cs.CC)
[14]  arXiv:2402.15871 (cross-list from cs.LO) [pdf, other]
Title: Regular resolution effectively simulates resolution
Authors: Sam Buss, Emre Yolcu
Subjects: Logic in Computer Science (cs.LO); Computational Complexity (cs.CC)
[15]  arXiv:2402.15814 (cross-list from cs.CL) [pdf, other]
Title: A Theoretical Result on the Inductive Bias of RNN Language Models
Subjects: Computation and Language (cs.CL); Computational Complexity (cs.CC); Machine Learning (cs.LG)
[16]  arXiv:2402.15686 (cross-list from quant-ph) [pdf, other]
Title: Lower bounds for quantum-inspired classical algorithms via communication complexity
Comments: 29 pages
Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC)

Mon, 26 Feb 2024

[17]  arXiv:2402.15409 (cross-list from stat.ML) [pdf, other]
Title: Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps
Subjects: Machine Learning (stat.ML); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG); Statistics Theory (math.ST)
[18]  arXiv:2402.15282 (cross-list from quant-ph) [pdf, ps, other]
Title: Dimension Independent Disentanglers from Unentanglement and Applications
Comments: 28 pages
Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC)
[19]  arXiv:2402.15076 (cross-list from cs.DS) [pdf, other]
Title: Tight Inapproximability of Target Set Reconfiguration
Authors: Naoto Ohsaka
Comments: 13 pages
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC); Discrete Mathematics (cs.DM)
[ total of 19 entries: 1-19 ]
[ showing up to 25 entries per page: fewer | more ]

Disable MathJax (What is MathJax?)

Links to: arXiv, form interface, find, cs, new, 2403, contact, help  (Access key information)