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

Testing Surface Area

Ryan O'Donnell, Carnegie Mellon University
Real Analysis in Testing, Learning and Inapproximability
http://simons.berkeley.edu/talks/ryan-odonnell-2013-08-27
Visit talk page
0:32:2

The Analysis of Partially Symmetric Functions

Eric Blais, Massachusetts Institute of Technology
Real Analysis in Testing, Learning and Inapproximability
http://simons.berkeley.edu/talks/eric-blais-2013-08-27
Visit talk page
0:47:22

Approximate Constraint Satisfaction Requires Large LP Relaxations

James R. Lee, University of Washington
Real Analysis in Testing, Learning and Inapproximability
http://simons.berkeley.edu/talks/james-lee-2013-08-28
Visit talk page
0:54:26

Moment-Matching Polynomials

Adam Klivans, University of Texas, Austin
Real Analysis in Testing, Learning and Inapproximability
http://simons.berkeley.edu/talks/adam-klivans-2013-08-28
Visit talk page
0:33:9

Deterministic Approximate Counting for Degree-2 Polynomial Threshold Functions

Rocco Servedio, Columbia University
Real Analysis in Testing, Learning and Inapproximability
http://simons.berkeley.edu/talks/rocco-servedio-2013-08-28
Visit talk page
0:46:8

Deterministic Counting of Satisfying Assignments for Juntas of Degree-2 PTFs

Anindya De, UC Berkeley
Real Analysis in Testing, Learning and Inapproximability
http://simons.berkeley.edu/talks/anindya-de-2013-08-28
Visit talk page
0:25:4

Approximating Boolean Functions With Small-Depth Circuits

Li-Yang Tan, Columbia University
Real Analysis in Testing, Learning and Inapproximability
http://simons.berkeley.edu/talks/li-yang-tan-2013-08-28
Visit talk page
0:47:36

Testing for Affine Invariant Properties of Algebraic Functions

Hamed Hatami, McGill University
Real Analysis in Testing, Learning and Inapproximability
http://simons.berkeley.edu/talks/hamed-hatami-2013-08-29
Visit talk page
0:44:35

On the Structure of Boolean Functions With Small Spectral Norm

Ben Lee Volk, Technion Israel Institute of Technology
Real Analysis in Testing, Learning and Inapproximability
http://simons.berkeley.edu/talks/ben-lee-volk-2013-08-29
Visit talk page
0:33:0

Locally Testable Codes and Cayley Graphs

Parikshit Gopalan, Microsoft Research
Real Analysis in Testing, Learning and Inapproximability
http://simons.berkeley.edu/talks/parikshit-gopalan-2013-08-29
Visit talk page