Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with indistinguishability:
TR15-182 | 13th November 2015
Andrej Bogdanov, Yuval Ishai, Emanuele Viola, Christopher Williamson

Bounded Indistinguishability and the Complexity of Recovering Secrets

Revisions: 1

We say that a function $f\colon \Sigma^n \to \{0, 1\}$ is $\epsilon$-fooled by $k$-wise indistinguishability if $f$ cannot distinguish with advantage $\epsilon$ between any two distributions $\mu$ and $\nu$ over $\Sigma^n$ whose projections to any $k$ symbols are identical. We study the class of functions $f$ that are fooled by ... more >>>

TR20-176 | 26th November 2020
Cynthia Dwork, Michael Kim, Omer Reingold, Guy Rothblum, Gal Yona

Outcome Indistinguishability

Prediction algorithms assign numbers to individuals that are popularly understood as individual ``probabilities''---what is the probability of 5-year survival after cancer diagnosis?---and which increasingly form the basis for life-altering decisions. Drawing on an understanding of computational indistinguishability developed in complexity theory and cryptography, we introduce Outcome Indistinguishability. Predictors that are ... more >>>

ISSN 1433-8092 | Imprint