Playlist: 25 videos

Real Analysis in Testing, Learning and Inapproximability

Aug. 26 – Aug. 30, 2013

The goal of the first workshop of the program is to identify challenges from learning, computational complexity, hardness of approximation and communication complexity that can be explicitly expressed in discrete analytic...

0:50:23

Approximation Resistance from Pairwise Independent Subgroups

Siu On Chan, UC Berkeley
Real Analysis in Testing, Learning and Inapproximability
http://simons.berkeley.edu/talks/siu-on-chan-2013-08-26
Visit talk page
0:54:50

An Analytic Approach to Parallel Repetition

David Steurer, Cornell University
Real Analysis in Testing, Learning and Inapproximability
http://simons.berkeley.edu/talks/david-steurer-2013-08-26
Visit talk page
0:33:14

Hardness of Maximum Independent Set in Structured Hypergraphs

Rishi Saket, IBM T.J. Watson Research Center
Real Analysis in Testing, Learning and Inapproximability
http://simons.berkeley.edu/talks/rishi-saket-2013-08-26
Visit talk page
0:42:4

Approximation Algorithms For Projection Games

Dana Moshkovitz, Massachusetts Institute of Technology
Real Analysis in Testing, Learning and Inapproximability
http://simons.berkeley.edu/talks/dana-moshkovitz-2013-08-26
Visit talk page
0:25:9

The Complexity of Somewhat Approximation Resistant Predicates

Pratik Worah, Courant Institute, NYU
Real Analysis in Testing, Learning and Inapproximability
http://simons.berkeley.edu/talks/pratik-worah-2013-08-26
Visit talk page
0:32:25

A Characterization of Strong Approximation Resistance

Madhur Tulsiani, Toyota Technological Institute, Chicago
Real Analysis in Testing, Learning and Inapproximability
http://simons.berkeley.edu/talks/madhur-tulsiani-2013-08-26
Visit talk page
0:28:20

Beyond Locality-Sensitive Hashing

Alexandr Andoni, Microsoft Research
Real Analysis in Testing, Learning and Inapproximability
http://simons.berkeley.edu/talks/alexandr-andoni-2013-08-26
Visit talk page
0:37:50

Robust Gaussian Noise Stability

Joe Neeman, University of Texas, Austin
Real Analysis in Testing, Learning and Inapproximability
http://simons.berkeley.edu/talks/joe-neeman-2013-08-27
Visit talk page
0:39:49

Majority is Stablest: Discrete and SOS

Elchanan Mossel, UC Berkeley
Real Analysis in Testing, Learning and Inapproximability
http://simons.berkeley.edu/talks/elchanan-mossel-2013-08-27
Visit talk page
0:34:6

Generalizations of the KKL Theorem and Friedgut's Junta Theorem

Sushant Sachdeva, Princeton University
Real Analysis in Testing, Learning and Inapproximability
http://simons.berkeley.edu/talks/sushant-sachdeva-2013-08-27
Visit talk page