Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

RSS-Feedprevious PreviousNext next

TR24-064 | 1st April 2024
Yuting Fang, Lianna Hambardzumyan, Nathaniel Harms, Pooya Hatami

No Complete Problem for Constant-Cost Randomized Communication

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

TR24-063 | 6th April 2024
Shuichi Hirahara, Mikito Nanashima

One-Way Functions and Zero Knowledge

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

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

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

previous PreviousNext next

ISSN 1433-8092 | Imprint