Computational Complexity

Authors and titles for recent submissions, skipping first 10

[ total of 18 entries: 1-10 | 11-18 ]
[ showing 10 entries per page: fewer | more | all ]

[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-10 | 11-18 ]
[ showing 10 entries per page: fewer | more | all ]