Under the auspices of the Computational Complexity Foundation (CCF)

LATEST > REPORTS:
Next

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

TR20-175 | 24th November 2020
Emanuele Viola

#### Fourier conjectures, correlation bounds, and Majority

Recently several conjectures were made regarding the Fourier spectrum of low-degree polynomials. We show that these conjectures imply new correlation bounds for functions related to Majority. Then we prove several new results on correlation bounds which aim to, but don't, resolve the conjectures. In particular, we prove several new results ... more >>>

TR20-174 | 18th November 2020
We generalize the celebrated isoperimetric inequality of Khot, Minzer, and Safra (SICOMP 2018) for Boolean functions to the case of real-valued functions $f \colon \{0,1\}^d\to\mathbb{R}$. Our main tool in the proof of the generalized inequality is a new Boolean decomposition that represents every real-valued function $f$ over an arbitrary partially ... more >>>