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

Computational Complexity

Authors and titles for recent submissions

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

Mon, 6 May 2024

[1]  arXiv:2405.02232 [pdf, ps, other]
Title: From Proof Complexity to Circuit Complexity via Interactive Protocols
Authors: Noel Arteche, Erfan Khaniki, Ján Pich, Rahul Santhanam
Comments: A conference version of this work is accepted to the 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP 2024)
Subjects: Computational Complexity (cs.CC)
[2]  arXiv:2405.01704 (cross-list from cs.LG) [pdf, other]
Title: Privacy-aware Berrut Approximated Coded Computing for Federated Learning
Authors: Xavier Martínez Luaña, Rebeca P. Díaz Redondo, Manuel Fernández Veiga
Subjects: Machine Learning (cs.LG); Computational Complexity (cs.CC); Distributed, Parallel, and Cluster Computing (cs.DC); Information Theory (cs.IT)

Fri, 3 May 2024

[3]  arXiv:2405.01091 [pdf, other]
Title: Maximizing Network Phylogenetic Diversity
Authors: Leo van Iersel, Mark Jones, Jannik Schestag, Celine Scornavacca, Mathias Weller
Subjects: Computational Complexity (cs.CC)
[4]  arXiv:2405.01344 (cross-list from cs.DS) [pdf, other]
Title: Metric Dimension and Geodetic Set Parameterized by Vertex Cover
Authors: Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, Prafullkumar Tale
Comments: This is the second part following an accompanying paper arXiv:2307.08149. We split the original paper to keep paper length more manageable
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC); Discrete Mathematics (cs.DM)
[5]  arXiv:2405.01017 (cross-list from math.CO) [pdf, ps, other]
Title: NP-completeness of Tiling Finite Simply Connected Regions with a Fixed Set of Wang Tiles
Authors: Chao Yang, Zhujun Zhang
Subjects: Combinatorics (math.CO); Computational Complexity (cs.CC); Metric Geometry (math.MG)
[6]  arXiv:2405.00789 (cross-list from quant-ph) [pdf, other]
Title: Classically Spoofing System Linear Cross Entropy Score Benchmarking
Authors: Andrew Tanggara, Mile Gu, Kishor Bharti
Comments: 19 pages, 1 figure
Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC)
[7]  arXiv:2405.00770 (cross-list from quant-ph) [pdf, other]
Title: Quantum-Classical Separations in Shallow-Circuit-Based Learning with and without Noises
Authors: Zhihan Zhang, Weiyuan Gong, Weikang Li, Dong-Ling Deng
Comments: 14 pages, 3 figures
Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC); Machine Learning (cs.LG)

Thu, 2 May 2024 (showing first 3 of 6 entries)

[8]  arXiv:2405.00327 [pdf, other]
Title: A Smoothed Analysis of the Space Complexity of Computing a Chaotic Sequence
Authors: Naoaki Okada, Shuji Kijima
Comments: arXiv admin note: text overlap with arXiv:2310.14185
Subjects: Computational Complexity (cs.CC)
[9]  arXiv:2405.00165 [pdf, ps, other]
Title: Solvable Initial Value Problems Ruled by Discontinuous Ordinary Differential Equations
Authors: Olivier Bournez, Riccardo Gozzi
Comments: Preliminary version presented at STACS'2024
Subjects: Computational Complexity (cs.CC); Logic in Computer Science (cs.LO); Dynamical Systems (math.DS)
[10]  arXiv:2405.00162 (cross-list from math.OC) [pdf, other]
Title: Real Stability and Log Concavity are coNP-Complete
Authors: Tracy Chin
Comments: 21 pages, 1 figure
Subjects: Optimization and Control (math.OC); Computational Complexity (cs.CC); Combinatorics (math.CO)
[ total of 20 entries: 1-10 | 11-20 ]
[ showing 10 entries per page: fewer | more | all ]

Disable MathJax (What is MathJax?)

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