enter search term and/or author name
The Weakness of CTC Qubits and the Power of Approximate Counting
Ryan O'Donnell, A. C. Cem Say
Article No.: 5
We present results in structural complexity theory concerned with the following interrelated topics: computation with postselection/restarting, closed timelike curves (CTCs), and approximate counting. The first result is a new characterization of...
Tight Running Time Lower Bounds for Vertex Deletion Problems
Article No.: 6
For a graph class Π, the Π-V
Algorithmic Information, Plane Kakeya Sets, and Conditional Dimension
Jack H. Lutz, Neil Lutz
Article No.: 7
We formulate the conditional Kolmogorov complexity of x given y at precision r, where x and y are points in Euclidean spaces and r is a natural number. We demonstrate the utility of...
The study of ground state energies of local Hamiltonians has played a fundamental role in quantum complexity theory. In this article, we take a new direction by introducing the physically motivated notion of “ground state...
Hardness of Approximation for H-free Edge Modification Problems
Ivan Bliznets, Marek Cygan, Paweł Komosa, Michał Pilipczuk
Article No.: 9