Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > ENTROPY APPROXIMATION:
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

Revisions: 1

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


TR24-094 | 19th May 2024
Tal Herman, Guy Rothblum

Interactive Proofs for General Distribution Properties

Suppose Alice has collected a small number of samples from an unknown distribution, and would like to learn about the distribution. Bob, an untrusted data analyst, claims that he ran a sophisticated data analysis on the distribution, and makes assertions about its properties. Can Alice efficiently verify Bob's claims using ... more >>>




ISSN 1433-8092 | Imprint