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-139 | 3rd October 2025
Kel Zin Tan, Prashant Nalini Vasudevan

Improved Search-to-Decision Reduction for Random Local Functions

A random local function defined by a $d$-ary predicate $P$ is one where each output bit is computed by applying $P$ to $d$ randomly chosen bits of its input. These represent natural distributions of instances for constraint satisfaction problems. They were put forward by Goldreich as candidates for low-complexity one-way ... more >>>


TR25-138 | 8th September 2025
Antoine Vinciguerra

Linear Matroid Intersection is in Catalytic Logspace

Revisions: 1

Linear matroid intersection is an important problem in combinatorial optimization. Given two linear matroids over the same ground set, the linear matroid intersection problem asks you to find a common independent set of maximum size. The deep interest in linear matroid intersection is due to the fact that it generalises ... more >>>


TR25-137 | 27th September 2025
Scott Aaronson, Freek Witteveen

Limits to black-box amplification in QMA

We study the limitations of black-box amplification in the quantum complexity class QMA. Amplification is known to boost any inverse-polynomial gap between completeness and soundness to exponentially small error, and a recent result (Jeffery and Witteveen, 2025) shows that completeness can in fact be amplified to be doubly exponentially close ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint