Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Entropy Approximation:
TR22-127 | 12th September 2022
Eric Allender, Shuichi Hirahara, Harsha Tirumala

Kolmogorov Complexity Characterizes Statistical Zero Knowledge

Revisions: 2

We show that a decidable promise problem has a non-interactive statistical zero-knowledge proof system if and only if it is randomly reducible to a promise problem for Kolmogorov-random strings, with a superlogarithmic additive approximation term. This extends recent work by Saks and Santhanam (CCC 2022). We build on this to ... more >>>

TR23-161 | 1st November 2023
Tal Herman, Guy Rothblum

Doubly-Efficient Interactive Proofs for Distribution Properties

Suppose we have access to a small number of samples from an unknown distribution, and would like learn facts about the distribution.
An untrusted data server claims to have studied the distribution and makes assertions about its properties. Can the untrusted data server prove that its assertions are approximately correct? ... more >>>

ISSN 1433-8092 | Imprint