Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions

Submitted by dloring on Mon, 2015-08-17 00:00
Author: 
P. Gopalan
N. Nisan
R. Servedio
K. Talwar
A. Wigderson
Publication: 
Proceedings of the Innovations in Theoretical Computer Science (ITCS) 2016, pp. 59-70, 2016.
Electronic Colloquium on Computational Complexity (ECCC) Report TR15-131, 2015.
Year: 
2015
Files
File: 
Proceedings version (pdf)
Draft of final version (pdf)