Videos

Start date cannot be after end date.
General Hardness Amplification of Predicates and Puzzles Thumbnail

General Hardness Amplification of Predicates and Puzzles

Presenter
  • Grant Schoenbeck
March 29, 2011
IAS
Non-negatively Weighted #CSPs: An Effective Complexity Dichotomy Thumbnail

Non-negatively Weighted #CSPs: An Effective Complexity Dichotomy

Presenter
  • Xi Chen
March 28, 2011
IAS
On the Fourier Spectrum of Symmetric Boolean Functions Thumbnail

On the Fourier Spectrum of Symmetric Boolean Functions

Presenter
  • Amir Shpilka
March 14, 2011
IAS
Relativized Separations of Worst-Case and Average-Case Complexities for NP Thumbnail

Relativized Separations of Worst-Case and Average-Case Complexities for NP

Presenter
  • Russell Impagliazzo
March 8, 2011
IAS
A Randomized Rounding Approach for Symmetric TSP Thumbnail

A Randomized Rounding Approach for Symmetric TSP

Presenter
  • Mohit Singh
March 7, 2011
IAS
Local Testing and Decoding of Sparse Linear Codes Thumbnail

Local Testing and Decoding of Sparse Linear Codes

Presenter
  • Shubhangi Saraf
February 22, 2011
IAS
Automatizability and Simple Stochastic Games Thumbnail

Automatizability and Simple Stochastic Games

Presenter
  • Toniann Pitassi
February 15, 2011
IAS
An Elementary Proof of Anti-Concentration of Polynomials in Gaussian Variables Thumbnail

An Elementary Proof of Anti-Concentration of Polynomials in Gaussian Variables

Presenter
  • Shachar Lovett
February 14, 2011
IAS
Bypassing UGC From Some Optimal Geometric Inapproximability Results Thumbnail

Bypassing UGC From Some Optimal Geometric Inapproximability Results

Presenter
  • Rishi Saket
February 8, 2011
IAS
Fast Random Projections Thumbnail

Fast Random Projections

Presenter
  • Edo Liberty
February 7, 2011
IAS
On The Complexity of Computing Roots and Residuosity Over Finite Fields Thumbnail

On The Complexity of Computing Roots and Residuosity Over Finite Fields

Presenter
  • Swastik Kopparty
February 1, 2011
IAS
Sparsifying and Derandomizing the Johnson-Lindenstrauss Transform Thumbnail

Sparsifying and Derandomizing the Johnson-Lindenstrauss Transform

Presenter
  • Jelani Nelson
January 31, 2011
IAS