Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > ADAPTIVITY:
Reports tagged with adaptivity:
TR03-019 | 3rd April 2003
Eli Ben-Sasson, Oded Goldreich, Madhu Sudan

Bounds on 2-Query Codeword Testing.

Revisions: 1


We present upper bounds on the size of codes that are locally
testable by querying only two input symbols. For linear codes, we
show that any $2$-locally testable code with minimal distance
$\delta n$ over a finite field $F$ cannot have more than
$|F|^{3/\delta}$ codewords. This result holds even ... more >>>


TR16-172 | 3rd November 2016
William Hoza, Adam Klivans

Preserving Randomness for Adaptive Algorithms

Revisions: 4

We introduce the concept of a randomness steward, a tool for saving random bits when executing a randomized estimation algorithm $\mathrm{Est}$ on many adaptively chosen inputs. For each execution, the chosen input to $\mathrm{Est}$ remains hidden from the steward, but the steward chooses the randomness of $\mathrm{Est}$ and, crucially, is ... more >>>




ISSN 1433-8092 | Imprint