Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Justin Oh:

TR23-056 | 26th April 2023
Geoffrey Mon, Dana Moshkovitz, Justin Oh

Approximate Locally Decodable Codes with Constant Query Complexity and Nearly Optimal Rate

We present simple constructions of good approximate locally decodable codes (ALDCs) in the presence of a $\delta$-fraction of errors for $\delta<1/2$. In a standard locally decodable code $C \colon \Sigma_1^k \to \Sigma_2^n$, there is a decoder $M$ that on input $i \in [k]$ correctly outputs the $i$-th symbol of a ... more >>>

TR22-103 | 15th July 2022
Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman

Almost Chor--Goldreich Sources and Adversarial Random Walks

Revisions: 2

A Chor--Goldreich (CG) source [CG88] is a sequence of random variables $X = X_1 \circ \ldots \circ X_t$, each $X_i \sim \{0,1 \{^d$, such that each $X_i$ has $\delta d$ min-entropy for some constant $\delta > 0$, even conditioned on any fixing of $X_1 \circ \ldots \circ X_{i-1}$. We typically ... more >>>

TR19-099 | 29th July 2019
Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman

Nearly Optimal Pseudorandomness From Hardness

Revisions: 3

Existing proofs that deduce $\mathbf{BPP}=\mathbf{P}$ from circuit lower bounds convert randomized algorithms into deterministic algorithms with a large polynomial slowdown. We convert randomized algorithms into deterministic ones with little slowdown. Specifically, assuming exponential lower bounds against nondeterministic circuits, we convert any randomized algorithm over inputs of length $n$ running in ... more >>>

ISSN 1433-8092 | Imprint