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

__
TR22-103
| 15th July 2022
__

Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman#### Almost Chor--Goldreich Sources and Adversarial Random Walks

Revisions: 2

__
TR19-099
| 29th July 2019
__

Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman#### Nearly Optimal Pseudorandomness From Hardness

Revisions: 3

Geoffrey Mon, Dana Moshkovitz, Justin Oh

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 >>>

Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman

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 >>>

Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman

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 >>>