Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > DOUBLY-EFFICIENT:
Reports tagged with doubly-efficient:
TR19-135 | 2nd October 2019
Michel Goemans, Shafi Goldwasser, Dhiraj Holden

Doubly-Efficient Pseudo-Deterministic Proofs

In [20] Goldwasser, Grossman and Holden introduced pseudo-deterministic interactive proofs for search problems where a powerful prover can convince a probabilistic polynomial time verifier that a solution to a search problem is canonical. They studied search problems for which polynomial time algorithms are not known and for which many solutions ... more >>>


TR23-097 | 2nd July 2023
Joshua Cook, Ron D. Rothblum

Efficient Interactive Proofs for Non-Deterministic Bounded Space

Revisions: 1

The celebrated $\mathbf{IP}=\mathbf{PSPACE}$ Theorem gives an efficient interactive proof for any bounded-space algorithm. In this work we study interactive proofs for non-deterministic bounded space computations. While Savitch's Theorem shows that nondeterministic bounded-space algorithms can be simulated by deterministic bounded-space algorithms, this simulation has a quadratic overhead. We give interactive protocols ... more >>>


TR25-105 | 29th July 2025
Oded Goldreich, Guy Rothblum

Location-Invariant Properties of Functions versus Properties of Distributions: United in Testing but Separated in Verification

A property of functions is called location-invariant (or symmetric) if it can be characterized in terms of the frequencies in which each value occurs in the function, regardless of the locations in which each value occurs.
It is known that the (query) complexity of testing location-invariant properties of functions ... more >>>




ISSN 1433-8092 | Imprint