Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR25-146 | 15th October 2025
Joshua Brakensiek, Yeyuan Chen, Manik Dhar, Zihan Zhang

From Random to Explicit via Subspace Designs With Applications to Local Properties and Matroids

In coding theory, a common question is to understand the threshold rates of various local properties of codes, such as their list decodability and list recoverability. A recent work Levi, Mosheiff, and Shagrithaya (FOCS 2025) gave a novel unified framework for calculating the threshold rates of local properties for random ... more >>>


TR25-145 | 2nd October 2025
Sabee Grewal, William Kretschmer

Unentanglement and Post-Measurement Branching in Quantum Interactive Proofs

We investigate two resources whose effects on quantum interactive proofs remain poorly understood: the promise of unentanglement, and the verifier’s ability to condition on an intermediate measurement, which we call post-measurement branching. We first show that unentanglement can dramatically increase computational power: three-round unentangled quantum interactive proofs equal NEXP, even ... more >>>


TR25-144 | 7th October 2025
Siddhartha Jain, Vishnu Iyer, Rolando Somma, Ning Bao, Stephen Jordan

Efficient Quantum Hermite Transform

We present a new primitive for quantum algorithms that implements a discrete Hermite transform efficiently, in time that depends logarithmically in both the dimension and the inverse of the allowable error. This transform, which maps basis states to states whose amplitudes are proportional to the Hermite functions, can be interpreted ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint