Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR23-206 | 9th December 2023
Yilei Chen, Jiatu Li

Hardness of Range Avoidance and Remote Point for Restricted Circuits via Cryptography

Revisions: 1

A recent line of research has introduced a systematic approach to explore the complexity of explicit construction problems through the use of meta problems, namely, the range avoidance problem (abbrev. Avoid) and the remote point problem (abbrev. RPP). The upper and lower bounds for these meta problems provide a unified ... more >>>


TR23-205 | 21st December 2023
Marshall Ball, Dana Dachman-Soled

(Inefficient Prover) ZAPs from Hard-to-Invert Functions

A ZAP is a witness-indistinguishable two-message public-coin interactive proof with the following simple structure: the verifier sends a uniformly random string, the prover responds, and the verifier decides in polynomial time whether to accept or reject.

We show that one-way functions imply the existence of ... more >>>


TR23-204 | 17th November 2023
John Bostanci, Luowen Qian, Nicholas Spooner, Henry Yuen

An efficient quantum parallel repetition theorem and applications

Revisions: 1

We prove a tight parallel repetition theorem for 3-message computationally-secure quantum interactive protocols between an efficient challenger and an efficient adversary. We also prove under plausible assumptions that the security of 4-message computationally secure protocols does not generally decrease under parallel repetition. These mirror the classical results of Bellare, Impagliazzo, ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint