Next

__
TR20-176
| 26th November 2020
__

Cynthia Dwork, Michael Kim, Omer Reingold, Guy Rothblum, Gal Yona#### Outcome Indistinguishability

__
TR20-175
| 24th November 2020
__

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

__
TR20-174
| 18th November 2020
__

Hadley Black, Iden Kalemaj, Sofya Raskhodnikova#### Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing

Next

Cynthia Dwork, Michael Kim, Omer Reingold, Guy Rothblum, Gal Yona

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

Emanuele Viola

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

Hadley Black, Iden Kalemaj, Sofya Raskhodnikova

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

Next