Under the auspices of the Computational Complexity Foundation (CCF)

LATEST > REPORTS:
Next

TR21-084 | 21st June 2021
Liron Bronfman, Ron Rothblum

#### PCPs and Instance Compression from a Cryptographic Lens

Modern cryptography fundamentally relies on the assumption that the adversary trying to break the scheme is computationally bounded. This assumption lets us construct cryptographic protocols and primitives that are known to be impossible otherwise. In this work we explore the effect of bounding the adversary's power in other information theoretic ... more >>>

TR21-083 | 21st June 2021
Mark Braverman, Sumegha Garg, Or Zamir

#### Tight Space Complexity of the Coin Problem

In the coin problem we are asked to distinguish, with probability at least $2/3$, between $n$ $i.i.d.$ coins which are heads with probability $\frac{1}{2}+\beta$ from ones which are heads with probability $\frac{1}{2}-\beta$. We are interested in the space complexity of the coin problem, corresponding to the width of a read-once ... more >>>

TR21-082 | 16th June 2021
Rahul Ilango, Hanlin Ren, Rahul Santhanam

#### Hardness on any Samplable Distribution Suffices: New Characterizations of One-Way Functions by Meta-Complexity

We show that one-way functions exist if and only if there is some samplable distribution D such that it is hard to approximate the Kolmogorov complexity of a string sampled from D. Thus we characterize the existence of one-way functions by the average-case hardness of a natural \emph{uncomputable} problem on ... more >>>

Next

ISSN 1433-8092 | Imprint