Computational Complexity

Authors and titles for recent submissions

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

[1] arXiv:2405.15368 [pdf, other]: Title: Complexity of Robust Orbit Problems for Torus Actions and the abc-conjecture

Authors: Peter Bürgisser, Mahmut Levent Doğan, Visu Makam, Michael Walter, Avi Wigderson

Subjects: Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS); Algebraic Geometry (math.AG); Representation Theory (math.RT)
[2] arXiv:2405.15722 (cross-list from cs.LG) [pdf, other]: Title: Models That Prove Their Own Correctness

Authors: Noga Amit, Shafi Goldwasser, Orr Paradise, Guy Rothblum

Subjects: Machine Learning (cs.LG); Computational Complexity (cs.CC); Software Engineering (cs.SE)
[3] arXiv:2405.15480 (cross-list from cs.LG) [pdf, other]: Title: Fundamental limits of weak learnability in high-dimensional multi-index models

Authors: Emanuele Troiani, Yatin Dandi, Leonardo Defilippis, Lenka Zdeborová, Bruno Loureiro, Florent Krzakala

Subjects: Machine Learning (cs.LG); Disordered Systems and Neural Networks (cond-mat.dis-nn); Computational Complexity (cs.CC)
[4] arXiv:2405.15441 (cross-list from stat.ML) [pdf, other]: Title: Statistical and Computational Guarantees of Kernel Max-Sliced Wasserstein Distances

Authors: Jie Wang, March Boedihardjo, Yao Xie

Comments: 44 pages, 7 figures, 4 tables

Subjects: Machine Learning (stat.ML); Computational Complexity (cs.CC); Machine Learning (cs.LG)

[5] arXiv:2405.13875 [pdf, other]: Title: On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets

Authors: Davide Bilò, Giordano Colli, Luca Forlizzi, Stefano Leucci

Subjects: Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)
[6] arXiv:2405.13143 [pdf, ps, other]: Title: Pseudorandomness, symmetry, smoothing: I

Authors: Harm Derksen, Peter Ivanov, Chin Ho Lee, Emanuele Viola

Comments: CCC 2024

Subjects: Computational Complexity (cs.CC)
[7] arXiv:2405.14835 (cross-list from cs.DS) [pdf, other]: Title: Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy

Authors: Sepehr Assadi, Prantar Ghosh, Bruno Loff, Parth Mittal, Sagnik Mukhopadhyay

Comments: Accepted at CCC 2024

Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)
[8] arXiv:2405.13877 (cross-list from cs.CG) [pdf, ps, other]: Title: On connections between k-coloring and Euclidean k-means

Authors: Enver Aman, Karthik C. S., Sharath Punna

Subjects: Computational Geometry (cs.CG); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)
[9] arXiv:2405.13273 (cross-list from quant-ph) [pdf, other]: Title: Dequantizability from inputs

Authors: Tae-Won Kim, Byung-Soo Choi

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

[10] arXiv:2405.12583 (cross-list from math.OC) [pdf, ps, other]: Title: Ergodic Unobservable MDPs: Decidability of Approximation

Authors: Krishnendu Chatterjee, David Lurie, Raimundo Saona, Bruno Ziliotto

Subjects: Optimization and Control (math.OC); Computational Complexity (cs.CC)
[11] arXiv:2405.12555 (cross-list from math.CO) [pdf, other]: Title: A Subexponential Reduction from Product Partition to Subset Sum

Authors: Marius Costandin

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

[12] arXiv:2405.11699 [pdf, ps, other]: Title: Fixed-parameter tractability of canonical polyadic decomposition over finite fields

Authors: Jason Yang

Comments: 8 pages; some proofs copied from arXiv:2401.06857

Subjects: Computational Complexity (cs.CC)
[13] arXiv:2405.12085 (cross-list from quant-ph) [pdf, other]: Title: Noise-tolerant learnability of shallow quantum circuits from statistics and the cost of quantum pseudorandomness

Authors: Chirag Wadhwa, Mina Doosti

Comments: 23+7 pages, 2 figures

Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC); Cryptography and Security (cs.CR); Machine Learning (cs.LG)
[14] arXiv:2405.11155 (cross-list from eess.SY) [pdf, other]: Title: Inner-approximate Reachability Computation via Zonotopic Boundary Analysis

Authors: Dejin Ren, Zhen Liang, Chenyu Wu, Jianqiang Ding, Taoran Wu, Bai Xue

Comments: the extended version of the paper accepted by CAV 2024

Subjects: Systems and Control (eess.SY); Computational Complexity (cs.CC)

[15] arXiv:2405.10774 [pdf, ps, other]: Title: Injective hardness condition for PCSPs

Authors: Demian Banakh, Marcin Kozik

Comments: To be published in LICS'24

Subjects: Computational Complexity (cs.CC)
[16] arXiv:2405.10546 [pdf, other]: Title: You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games

Authors: MIT Hardness Group, Hayashi Ani, Erik D. Demaine, Holden Hall, Ricardo Ruiz, Naveen Venkat

Subjects: Computational Complexity (cs.CC)
[17] arXiv:2405.10933 (cross-list from quant-ph) [pdf, other]: Title: Learning low-degree quantum objects

Authors: Srinivasan Arunachalam, Arkopal Dutt, Francisco Escudero Gutiérrez, Carlos Palazuelos

Comments: 26+4 pages

Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG); Functional Analysis (math.FA)
[18] arXiv:2405.10930 (cross-list from stat.ML) [pdf, other]: Title: Submodular Information Selection for Hypothesis Testing with Misclassification Penalties

Authors: Jayanth Bhargav, Mahsa Ghasemi, Shreyas Sundaram

Comments: 23 pages, 4 figures

Subjects: Machine Learning (stat.ML); Computational Complexity (cs.CC); Information Theory (cs.IT); Machine Learning (cs.LG); Optimization and Control (math.OC)

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