Connor Paddock

dblp:211/7729 · DBLP profile ↗
← Back
2ranked-venue papers
0as first author
2since 2021 · last 2026
0000-0002-5742-2795ORCID · verified

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2 · 2 since 2021
YearPublicationVenuePosition
2026 The Quantum Smooth Label Cover Problem Is Undecidable
abstract
We show that the quantum smooth label cover problem is undecidable and RE-hard. This sharply contrasts the quantum unique label cover problem, which can be decided efficiently by a result of Kempe, Regev, and Toner (FOCS'08). On the other hand, our result aligns with the RE-hardness of the quantum label cover problem, which follows from the celebrated MIP* = RE result of Ji, Natarajan, Vidick, Wright, and Yuen (ACM'21). Additionally, we show that the quantum oracularized smooth label cover problem is RE-hard. Our second result fits with the alternative quantum unique games conjecture recently proposed by Mousavi and Spirig (ITCS'25) on the RE-hardness of the quantum oracularized unique label cover problem. Our proof techniques include a quantum version of Feige's reduction from 3SAT to 3SAT5 (STOC'96) for BCSMIP*-protocols, which may be of independent interest.
Eric Culf, Kieran Mastel, Connor Paddock, Taro Spirig
ICALP3
2025 A Bound on the Quantum Value of All Compiled Nonlocal Games
Alexander Kulpe, Giulio Malavolta, Connor Paddock, Simon Schmidt 0001, Michael Walter 0005
STOC3