PreviousNext

__
TR24-064
| 1st April 2024
__

Yuting Fang, Lianna Hambardzumyan, Nathaniel Harms, Pooya Hatami#### No Complete Problem for Constant-Cost Randomized Communication

__
TR24-063
| 6th April 2024
__

Shuichi Hirahara, Mikito Nanashima#### One-Way Functions and Zero Knowledge

__
TR24-062
| 5th April 2024
__

Omar Alrabiah, Venkatesan Guruswami#### Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles

Revisions: 1

PreviousNext

Yuting Fang, Lianna Hambardzumyan, Nathaniel Harms, Pooya Hatami

We prove that the class of communication problems with public-coin randomized constant-cost protocols, called $BPP^0$, does not contain a complete problem. In other words, there is no randomized constant-cost problem $Q \in BPP^0$, such that all other problems $P \in BPP^0$ can be computed by a constant-cost deterministic protocol with ... more >>>

Shuichi Hirahara, Mikito Nanashima

The fundamental theorem of Goldreich, Micali, and Wigderson (J. ACM 1991) shows that the existence of a one-way function is sufficient for constructing computational zero knowledge ($\mathrm{CZK}$) proofs for all languages in $\mathrm{NP}$. We prove its converse, thereby establishing characterizations of one-way functions based on the worst-case complexities of ... more >>>

Omar Alrabiah, Venkatesan Guruswami

We prove that a binary linear code of block length $n$ that is locally correctable with $3$ queries against a fraction $\delta > 0$ of adversarial errors must have dimension at most $O_{\delta}(\log^2 n \cdot \log \log n)$. This is almost tight in view of quadratic Reed-Muller codes being a ... more >>>

PreviousNext