Seminars

Tuesday, December 12, 2017 Amir Shpilka , Tel Aviv University
A PSPACE construction of a hitting set for the closure of small algebraic circuits
Monday, December 11, 2017 Richard Zemel , University of Toronto; Visitor, School of Mathematics
Learning with little data
Monday, December 11, 2017 Daniel Kane , University of California, San Diego
Recent advances in high dimensional robust statistics
Tuesday, December 5, 2017 Ian Mertz , University of Toronto
Short proofs are hard to find (joint work w/ Toni Pitassi and Hao Wei)
Monday, December 4, 2017 Madhu Sudan , Harvard University
General strong polarization
Tuesday, November 28, 2017 Greta Panova , University of Pennsylvania; von Neumann Fellow, School of Mathematics
Geometric complexity theory from a combinatorial viewpoint
Monday, November 27, 2017 Sanjeev Arora , Princeton University; Visiting Professor, School of Mathematics
Everything you wanted to know about machine learning but didn't know whom to ask
Monday, November 27, 2017 Holden Lee , Princeton University
Beyond log-concavity: provable guarantees for sampling multi-modal distributions using simulated tempering Langevin Monte Carlo
Monday, November 27, 2017 Shubhangi Saraf , Rutgers University
Locally testable and locally correctable codes approaching the Gilbert-Varshamov bound
Tuesday, November 21, 2017 Richard Zemel , University of Toronto; Visitor, School of Mathematics
A practical guide to deep learning
Monday, November 20, 2017 No seminar today
No seminar today
Tuesday, November 14, 2017 Russell Impagliazzo , University of California, San Diego
Learning models: connections between boosting, hard-core distributions, dense models, GAN, and regularity II
Monday, November 13, 2017 Maithra Raghu , Cornell University
Towards a better understanding of neural networks: learning dynamics, interpretability and RL generalization
Monday, November 13, 2017 Russell Impagliazzo , University of California, San Diego
Learning models: connections between boosting, hard-core distributions, dense models, GAN, and regularity I
Tuesday, November 7, 2017 Eshan Chattopadhyay , Member, School of Mathematics
Pseudorandom generators for unordered branching programs
Monday, November 6, 2017 Sida Wang , Visitor, School of Mathematics
Naturalizing a programming language
Monday, November 6, 2017 Barna Saha , University of Massachusetts, Amherst
Language edit distance, $(\min,+)$-matrix multiplication & beyond
Tuesday, October 31, 2017 Zeev Dvir , Princeton University; von Neumann Fellow, School of Mathematics
Cap-sets in $(F_q)^n$ and related problems
Monday, October 30, 2017 Rocco Servedio , Columbia University
Fooling intersections of low-weight halfspaces
Tuesday, October 24, 2017 Shay Moran , University of California, San Diego; Member, School of Mathematics
On the strength of comparison queries
Monday, October 23, 2017 Mark Bun , Princeton University
A nearly optimal lower bound on the approximate degree of AC$^0$
Tuesday, October 17, 2017 No seminar: FOCS
No seminar: FOCS
Monday, October 16, 2017 Nevena Lazic , Google
Keeping IT cool: machine learning for data center cooling
Monday, October 16, 2017 No seminar: FOCS
No seminar: FOCS
Tuesday, October 10, 2017 Ankit Garg , Microsoft Research
Structural aspects of the null-cone problem in invariant theory
Monday, October 9, 2017 Rafael Oliveira , University of Toronto
Barriers for rank methods in arithmetic complexity
Tuesday, October 3, 2017 Avi Wigderson , Herbert H. Maass Professor, School of Mathematics
Elementary open problems in Algebra (with consequences in computational complexity)
Monday, October 2, 2017 Elad Hazan , Princeton University
Hyperparameter optimization: a spectral approach
Monday, October 2, 2017 Omri Weinstein , Columbia University
Crossing the logarithmic barrier for dynamic boolean data structure lower bounds
Tuesday, September 26, 2017 Toniann Pitassi , University of Toronto; Visiting Professor, School of Mathematics
Lifting theorems in communication complexity and applications
Monday, September 18, 2017 Umesh Vazirani , University of California, Berkeley
Rigorous RG: a provably efficient and possibly practical algorithm for simulating 1D quantum systems
Tuesday, April 18, 2017 Adam Marcus , Princeton University; von Neumann Fellow, School of Mathematics
Bounds on roots of polynomials (and applications)
Monday, April 17, 2017 Yannai Gonczarowski , Hebrew University of Jerusalem and Microsoft Research
Efficient empirical revenue maximization in single-parameter auction environments
Tuesday, April 11, 2017 Adam Marcus , Princeton University; von Neumann Fellow, School of Mathematics
Noncommutative probability for computer scientists
Monday, April 10, 2017 Allison Bishop , Columbia University
In pursuit of obfuscation
Tuesday, April 4, 2017 Mark Braverman , Princeton University; von Neumann Fellow, School of Mathematics
Computability and complexity in analysis and dynamics
Monday, April 3, 2017 Ran Raz , Princeton University
A time-space lower bound for a large class of learning problems
Tuesday, March 28, 2017 Robert Robere , University of Toronto
Applications of monotone constraint satisfaction
Monday, March 27, 2017 Orit Raz , Member, School of Mathematics
Extremal problems in combinatorial geometry
Monday, March 27, 2017 Robert Robere , University of Toronto
Applications of monotone constraint satisfaction
Monday, March 20, 2017 Ankur Moitra , Massachusetts Institute of Technology
Approximate counting and the Lovasz local lemma
Monday, March 13, 2017 Nir Bitansky , Massachusetts Institute of Technology
Indistinguishability obfuscation from 5-linear maps: a reduction from flying pigs to jumping pigs
Monday, March 13, 2017 Nir Bitansky , Massachusetts Institute of Technology
On the cryptographic hardness of finding a Nash equilibrium
Tuesday, March 7, 2017 Avi Wigderson , Herbert H. Maass Professor, School of Mathematics
Some basic problems and results from Invariant Theory
Monday, March 6, 2017 Yael Kalai , Microsoft Research
Interactive coding with nearly optimal round and communication blowup
Tuesday, February 28, 2017 Avi Wigderson , Herbert H. Maass Professor, School of Mathematics
Structural and computational aspects of Brascamp-Lieb inequalities
Monday, February 27, 2017 Eric Allender , Rutgers University
New insights on the (non)-hardness of circuit minimization and related problems
Tuesday, February 21, 2017 Omer Paneth , Massachusetts Institute of Technology
Program obfuscation: outside the black box
Tuesday, February 14, 2017 Matt Weinberg , Princeton University
A unified duality-based approach to Bayesian mechanism design
Monday, February 13, 2017 Ilya Razenshteyn , Massachusetts Institute of Technology
Nearest neighbor search for general symmetric norms via embeddings into product spaces
Tuesday, February 7, 2017 Amir Ali Ahmadi , Princeton University
Optimization in dynamical systems
Monday, February 6, 2017 Prasad Raghavendra , University of California, Berkeley
Strongly Refuting Random CSPs below the spectral threshold
Tuesday, January 31, 2017 Alex Andoni , Columbia University
Sketching and embedding are equivalent for norms
Monday, January 30, 2017 Aaron Roth , University of Pennsylvania
Quantifying tradeoffs between fairness and accuracy in online learning
Tuesday, January 24, 2017 Shachar Lovett , University of California, San Diego
Robust sensitivity
Monday, January 23, 2017 Shachar Lovett , University of California, San Diego
Active learning with "simple" membership queries
Tuesday, January 17, 2017 Jordan Ellenberg , University of Wisconsin
The polynomial method: more results and open questions
Tuesday, January 17, 2017 Jordan Ellenberg , University of Wisconsin
The polynomial method and the cap set problem
Tuesday, December 13, 2016 Pravesh Kothari , Member, School of Mathematics
Sum of squares lower bounds for refuting any CSP
Monday, December 12, 2016 Ronen Eldan , Weizmann Institute of Science
On gradient complexity of measures on the discrete cube
Tuesday, December 6, 2016 Pravesh Kothari , Member, School of Mathematics
Approximate constraint satisfaction requires sub-exponential size linear programs
Monday, December 5, 2016 Shubhangi Saraf , Rutgers University
On the number of ordinary lines determined by sets in complex space
Tuesday, November 29, 2016 Orit Raz , Member, School of Mathematics
Combinatorial rigidity of graphs embedded in $\mathbb{R}^2$
Monday, November 28, 2016 Emmanuel Abbe , Princeton University
Stochastic block models and probabilistic reductions
Tuesday, November 22, 2016 Zeyuan Allen-Zhu , Member, School of Mathematics
Theory of accelerated methods
Monday, November 21, 2016 Uri Feige , Weizmann Institute of Science
On the effect of randomness on planted 3-coloring models
Tuesday, November 15, 2016 Eshan Chattopadhyay , Member, School of Mathematics
Non-malleable extractors for constant depth circuits, and affine functions
Monday, November 14, 2016 Bernard Chazelle , Princeton University
The mathematics of natural algorithms
Tuesday, November 8, 2016 Aaron Potechin , Member, School of Mathematics
Exact tensor completion via sum of squares
Monday, November 7, 2016 Amit Singer , Princeton University
Non-unique games over compact groups and orientation estimation in cryo-EM
Tuesday, November 1, 2016 Aviad Rubinstein , University of California, Berkeley
Settling the complexity of computing approximate two-player Nash equilibria
Monday, October 31, 2016 Aviad Rubinstein , University of California, Berkeley
Communication complexity of approximate Nash equilibria
Tuesday, October 25, 2016 David Steurer , Cornell University; Member, School of Mathematics
Sum of squares, quantum entanglement, and log rank
Monday, October 24, 2016 Xi Chen , Columbia University
On the query complexity of Boolean monotonicity testing
Tuesday, October 18, 2016 Adam Marcus , Princeton University; von Neumann Fellow, School of Mathematics
Real rooted polynomials and multivariate extensions
Monday, October 17, 2016 Harm Derksen , University of Michigan
Matrix invariants and algebraic complexity theory
Tuesday, October 11, 2016 No seminar today: FOCS
No seminar today: FOCS
Monday, October 10, 2016 No seminar today: FOCS
No seminar today: FOCS
Tuesday, October 4, 2016 No seminar today
No seminar today
Monday, October 3, 2016 No seminar today
No seminar today
Tuesday, September 27, 2016 No seminar today: postdoctoral talks
No seminar today: postdoctoral talks
Monday, September 26, 2016 Allan Sly , Princeton University
Counting solutions to random constraint satisfaction problems
Tuesday, September 20, 2016 Gil Cohen , Princeton University
Algebraic geometric codes and their applications
Tuesday, May 3, 2016 Avishay Tal , Member, School of Mathematics
Fourier tails for Boolean functions and their applications
Tuesday, April 26, 2016 Amir Shpilka , Tel Aviv University
Reed-Muller codes for random erasures and errors
Tuesday, April 19, 2016 Pooya Hatami , Member, School of Mathematics
A characterization of functions with vanishing averages over products of disjoint sets
Tuesday, April 5, 2016 Li-Yang Tan , Toyota Technological Institute, Chicago
An average-case depth hierarchy theorem for Boolean circuits II
Monday, April 4, 2016 Li-Yang Tan , Toyota Technological Institute, Chicago
An average-case depth hierarchy theorem for Boolean circuits I
Monday, March 28, 2016 Swastik Kopparty , Rutgers University
A local central limit theorem for triangles in a random graph
Tuesday, March 22, 2016 Avi Wigderson , Herbert H. Maass Professor, School of Mathematics
The Resolution proof system
Monday, March 21, 2016 Tengyu Ma , Princeton University
Polynomial-time tensor decompositions via sum-of-squares
Tuesday, March 15, 2016 Avi Wigderson , Herbert H. Maass Professor, School of Mathematics
Proof complexity - an introduction
Monday, March 14, 2016 Mrinal Kumar , Rutgers University
Lower bounds for homogeneous depth-5 arithmetic circuits over finite fields
Tuesday, March 8, 2016 Ran Raz , Weizmann Institute of Science; Visiting Professor, School of Mathematics
Fast learning requires good memory: a time-space lower bound for parity learning
Monday, March 7, 2016 Pravesh Kothari , University of Texas, Austin
Almost optimal sum of squares lower bound for planted clique
Tuesday, March 1, 2016 László Babai , University of Chicago
Graph isomorphism in quasipolynomial time II
Monday, February 29, 2016 László Babai , University of Chicago
Graph isomorphism in quasipolynomial time I
Tuesday, February 23, 2016 Karim Adiprasito , Member, School of Mathematics
Minkowski sums, mixed faces and combinatorial isoperimetry
Monday, February 22, 2016 Omri Weinstein , New York University
The deterministic communication complexity of approximate fixed point
Tuesday, February 16, 2016 Avi Wigderson , Herbert H. Maass Professor, School of Mathematics
The singularity of symbolic matrices
Tuesday, February 9, 2016 Avi Wigderson , Herbert H. Maass Professor, School of Mathematics
The singularity of symbolic matrices
Monday, February 8, 2016 Stephen Fenner , University of South Carolina
Bipartite perfect matching is in quasi-NC
Tuesday, February 2, 2016 Ron Rothblum , Massachusetts Institute of Technology
Constant-round interactive-proofs for delegating computations (continued)
Monday, February 1, 2016 Ron Rothblum , Massachusetts Institute of Technology
Constant-round interactive-proofs for delegating computations
Tuesday, January 26, 2016 Seminar cancelled on account of snow.
Seminar cancelled on account of snow.
Monday, January 25, 2016 Seminar cancelled on account of snow.
Seminar cancelled on account of snow.
Tuesday, January 19, 2016 Michael Forbes , Visitor, School of Mathematics
Proof Complexity Lower Bounds from Algebraic Circuit Complexity
Tuesday, January 12, 2016 Hoi Nguyen , Ohio State University; von Neumann Fellow, School of Mathematics
Anti-concentration: results and applications
Monday, December 14, 2015 Or Meir , University of Haifa
Toward the KRW conjecture: cubic lower bounds via communication complexity
Tuesday, December 8, 2015 Doron Puder , Member, School of Mathematics
Ramanujan coverings of graphs
Monday, December 7, 2015 Abhishek Bhowmick , University of Texas at Austin
Bias vs low rank of polynomials with applications to list decoding and effective algebraic geometry
Thursday, December 3, 2015 Avi Wigderson , School of Mathematics, Institute for Advanced Study
Randomness Extractors
video
Thursday, December 3, 2015 Russell Impagliazzo , University of California at San Diego and Member, School of Mathematics
When Do Sparse Sets Have Dense Models?
video
Thursday, December 3, 2015 Jean Bourgain , School of Mathematics, Institute for Advanced Study
Exponential Sums, Equidistribution and Pseudo-Randomness
video
Tuesday, December 1, 2015 Avishay Tal , Member, School of Mathematics
Rigidity of random Toeplitz matrices with an application to depth three circuits
Monday, November 30, 2015 David Steurer , Cornell University
Lower bounds on the size of semidefinite programming relaxations
Tuesday, November 24, 2015 Pooya Hatami , Member, School of Mathematics
General systems of linear forms: equidistribution and true complexity
Monday, November 23, 2015 Jacob Fox , Stanford University
Advances on Ramsey numbers
Tuesday, November 17, 2015 Alex Lubotzky , Hebrew University of Jerusalem
Cohomology for computer science
Monday, November 16, 2015 Vadym Kliuchnikov , Microsoft Research
How quaternion algebras over number fields are useful for creating compiler for a quantum computer?
Tuesday, November 10, 2015 Gillat Kol , Member, School of Mathematics
Exponential separation of communication and external information
Monday, November 9, 2015 Yin Tat Lee , Massachusetts Institute of Technology
Cutting plane method: A faster algorithm for many (combinatorial) optimization problems
Tuesday, November 3, 2015 Gil Cohen , California Institute of Technology
Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs II
Monday, November 2, 2015 Gil Cohen , California Institute of Technology
Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs I
Tuesday, October 27, 2015 Jan Vondrák , IBM Almaden Research Center; Member, School of Mathematics
Algorithmic proof of the Lovasz Local Lemma via resampling oracles
Monday, October 26, 2015 John Wright , Carnegie Mellon University
Random words, longest increasing subsequences, and quantum PCA
Tuesday, October 20, 2015 No seminar today: FOCS
No seminar today: FOCS
Monday, October 19, 2015 No seminar today: FOCS
No seminar today: FOCS
Tuesday, October 13, 2015 Noga Alon , Tel Aviv University; Visiting Professor, School of Mathematics
Non-constructive combinatorics
Monday, October 12, 2015 Rafael Oliveira , Princeton University
Factors of polynomials of low individual degree
Tuesday, October 6, 2015 Chaim Even Zohar , Hebrew University of Jerusalem
Invariants of random knots
Monday, October 5, 2015 Elad Hazan , Princeton University
Is optimization computationally equivalent to online learning?
Tuesday, September 29, 2015 No talk today
No talk today
Monday, September 28, 2015 Choongbum Lee , Massachusetts Institute of Technology
Ramsey numbers of degenerate graphs
Tuesday, September 22, 2015 Eshan Chattopadhyay , University of Texas at Austin
Explicit two-source extractors and resilient functions II
Monday, September 21, 2015 Eshan Chattopadhyay , University of Texas at Austin
Explicit two-source extractors and resilient functions I
Wednesday, April 22, 2015 Swastik Kopparty , Member, School of Mathematics
The Correlation of Multiplicative Characters with Polynomials over Finite Fields
Wednesday, April 22, 2015 Peter Varju , Princeton University
Random Walks in Linear Groups
Monday, April 13, 2015 Michael Saks , Rutgers University
A new approach to the sensitivity conjecture
Tuesday, April 7, 2015 Emanuele Viola , Northeastern University
Interleaved products in special linear groups: mixing and communication complexity
Monday, April 6, 2015 Nisheeth Vishnoi , École polytechnique fédérale de Lausanne
Natural algorithms for flow problems
Tuesday, March 31, 2015 Sergey Yekhanin , Microsoft Research
Kolmogorov width of discrete linear spaces: an approach to matrix rigidity
Monday, March 30, 2015 Vladimir Vapnik , Columbia University
Intelligent learning: similarity control and knowledge transfer
Tuesday, March 24, 2015 Dimitris Achlioptas , University of California, Santa Cruz
Tractability as compressibility
Monday, March 23, 2015 Dimitris Achlioptas , University of California, Santa Cruz
Random walks that find perfect objects and the Lovász local lemma
Tuesday, March 17, 2015 Ran Raz , Weizmann Institute of Science; Visiting Professor, School of Mathematics
Average-case lower bounds for formula size
Monday, March 16, 2015 Oded Regev , New York University
Tight hardness of the non-commutative Grothendieck problem
Tuesday, March 10, 2015 Christopher Beck , Member, School of Mathematics
Chernoff bounds for expander walks
Monday, March 9, 2015 Elchanan Mossel , University of Pennsylvania
Strong contraction and influences in tail spaces
Tuesday, March 3, 2015 Karim Adiprasito , Member, School of Mathematics
Whitney numbers via measure concentration in representation varieties
Monday, March 2, 2015 Shayan Oveis Gharan , University of California, Berkeley
Effective-resistance-reducing flows, spectrally thin trees and asymmetric TSP
Tuesday, February 24, 2015 Louis Rowen , Bar Ilan University
Computing inverses
Monday, February 23, 2015 Mika Göös , University of Toronto
Lower bounds for clique vs. independent set
Tuesday, February 17, 2015 June Huh , Princeton University; Veblen Fellow, School of Mathematics
The log-concavity conjecture and the tropical Laplacian
Monday, February 16, 2015 Sivakanth Gopi , Princeton University
2-Server PIR with sub-polynomial communication
Tuesday, February 10, 2015 Ali Kemal Sinop , Simons Institute for the Theory of Computing, Berkeley
How to round subspaces: a new spectral clustering algorithm
Monday, February 9, 2015 Alex Arkhipov , Massachusetts Institute of Technology
Quantum computing with noninteracting particles
Tuesday, February 3, 2015 Michael Forbes , Member, School of Mathematics
Dimension expanders via rank condensers
Monday, February 2, 2015 Subhash Khot , New York University
On monotonicity testing and boolean isoperimetric type theorems
Tuesday, January 27, 2015 Storm - no seminar
Storm - no seminar
Monday, January 26, 2015 Guy Rothblum , Stanford University
Publicly-verifiable non-interactive arguments for delegating computation
Tuesday, January 20, 2015 Ankit Garg , Princeton University
Small value parallel repetition for general games
Tuesday, December 9, 2014 Avi Wigderson , Herbert H. Maass Professor, School of Mathematics
More on sum-of-squares proofs for planted clique
Monday, December 8, 2014 Umesh Vazirani , University of California, Berkeley
Area Laws and the complexity of quantum states
Tuesday, December 2, 2014 Timothy Riley , Cornell University; Member, School of Mathematics
Taming the hydra: the Word Problem, Dehn functions, and extreme integer compression
Monday, December 1, 2014 Dana Moshkovitz , Massachusetts Institute of Technology
Parallel Repetition From Fortification
Tuesday, November 25, 2014 Avi Wigderson , Herbert H. Maass Professor, School of Mathematics
Sum-of-squares lower bounds for the planted clique problem
Monday, November 24, 2014 Ariel Procaccia , Carnegie Mellon University
Computational fair division
Tuesday, November 18, 2014 Tara Holm , Cornell University; von Neumann Fellow, School of Mathematics
Toric origami manifolds and origami templates
Monday, November 17, 2014 Adi Livnat , Virginia Tech
Mutation as a computational event
Tuesday, November 11, 2014 Anindya De , Center for Discrete Mathematics and Theoretical Computer Science; Visitor, School of Mathematics
Asymptotic expansions of the central limit theorem and its applications
Monday, November 10, 2014 James Lee , University of Washington
Talagrand's convolution conjecture and geometry via coupling
Tuesday, November 4, 2014 Noga Alon , Tel Aviv University; Visiting Professor, School of Mathematics
Sign rank, spectral gap and VC dimension
Monday, November 3, 2014 Eyal Lubetzky , New York University
Information percolation for the Ising model
Tuesday, October 28, 2014 Gillat Kol , Member, School of Mathematics
Exponential separation of information and communication
Monday, October 27, 2014 Assaf Naor , Princeton University
Discretization and quantitative differentiation
Tuesday, October 21, 2014 FOCS - no seminar
FOCS - no seminar
Monday, October 20, 2014 FOCS - no seminar
FOCS - no seminar
Tuesday, October 14, 2014 Noga Ron-Zewi , Member, School of Mathematics
Sampling-based proof of the quasipolynomial Bogolyubov-Ruzsa theorem and algorithmic applications
Monday, October 13, 2014 Santosh Vempala , Georgia Institute of Technology
Cool with a Gaussian: an \(O^*(n^3)\) volume algorithm
Tuesday, October 7, 2014 Yuval Filmus , Member, School of Mathematics
Monotone submodular maximization over a matroid
Monday, October 6, 2014 Rotem Oshman , Tel Aviv University
The communication complexity of distributed subgraph detection
Tuesday, September 30, 2014 Doron Puder , Member, School of Mathematics
Uniform words are primitive (cont'd)
Monday, September 29, 2014 Leonid Gurvits , City University of New York
Breaking \(e^n\) barrier for deterministic poly-time approximation of the permanent and settling Friedland's conjecture on the Monomer-Dimer Entropy
Tuesday, September 23, 2014 Doron Puder , Member, School of Mathematics
Uniform words are primitive
Monday, September 22, 2014 Paul Seymour , Princeton University
Colouring graphs with no odd holes
Tuesday, May 13, 2014 Anindya De , Member, School of Mathematics
A central limit theorem for Gaussian polynomials and deterministic approximate counting for polynomial threshold functions
Tuesday, April 29, 2014 Anindya De , Member, School of Mathematics
A central limit theorem for Gaussian polynomials and deterministic approximate counting for polynomial threshold functions
Monday, April 28, 2014 Yuval Peres , Microsoft Research
Search games and Optimal Kakeya Sets
Tuesday, April 22, 2014 Andris Ambainis , University of Latvia; von Neumann Fellow, School of Mathematics
Results and open problems in theory of quantum complexity
Monday, April 21, 2014 Yaoyun Shi , University of Michigan
True Randomness: Its Origin and Expansion
Tuesday, April 15, 2014 Or Meir , Member, School of Mathematics
IP = PSPACE via error correcting codes
Monday, April 14, 2014 Brett Hemenway , University of Pennsylvania
Local Correctability of Expander Codes
Tuesday, April 8, 2014 Andrew Drucker , Member, School of Mathematics
Do NP-Hard Problems Require Exponential Time?
Monday, April 7, 2014 Aravind Srinivasan , University of Maryland, College Park
Progress on algorithmic versions of the Lovasz Local Lemma
Tuesday, April 1, 2014 Valerie King , University of Victoria; Member, School of Mathematics
Byzantine Agreement in Expected Polynomial Time
Monday, March 31, 2014 Rocco Servedio , Columbia University
A polynomial lower bound for monotonicity testing of Boolean functions over hypercube and hypergrid domains
Tuesday, March 25, 2014 Bruce Kapron , University of Victoria; Member, School of Mathematics
Circular Encryption in Formal and Computational Cryptography
Monday, March 24, 2014 Mary Wootters , University of Michigan
List decodability of randomly punctured codes
Tuesday, March 18, 2014 Olga Holtz , University of California, Berkeley; von Neumann Fellow, School of Mathematics
Graph expansion and communication complexity of algorithms
Monday, March 17, 2014 Thomas Rothvoss , University of Washington, Seattle
The matching polytope has exponential extension complexity
Tuesday, March 11, 2014 Ran Raz , Weizmann Institute of Science; Visiting Professor, School of Mathematics
How to Delegate Computations: The Power of No-Signaling
Monday, March 10, 2014 Avishay Tal , Weizmann Institute
Two Structural Results for Low Degree Polynomials and Applications
Tuesday, March 4, 2014 Yuval Filmus , Member, School of Mathematics
Fast matrix multiplication
Monday, March 3, 2014 Yufei Zhao , Massachusetts Institute of Technology
The Green-Tao theorem and a relative Szemeredi theorem
Tuesday, February 25, 2014 Yuval Filmus , Member, School of Mathematics
Fast matrix multiplication
Monday, February 24, 2014 Jonathan Kelner , Massachusetts Institute of Technology
An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
Tuesday, February 18, 2014 Avi Wigderson , Herbert H. Maass Professor, School of Mathematics
Non-commutative arithmetic computation
Monday, February 17, 2014 Joshua Grochow , University of Toronto
Unifying known lower bounds via geometric complexity theory
Tuesday, February 11, 2014 Avi Wigderson , Herbert H. Maass Professor, School of Mathematics
Non-commutative arithmetic computation
Monday, February 10, 2014 Julia Chuzhoy , Toyota Technological Institute at Chicago
Polynomial Bounds for the Grid-Minor Theorem
Tuesday, February 4, 2014 Ori Parzanchevski , Member, School of Mathematics
Simplicial complexes as expanders
Monday, February 3, 2014 Brett Hemenway , University of Pennsylvania
Local Correctability of Expander Codes
Tuesday, January 28, 2014 Ori Parzanchevski , Member, School of Mathematics
Simplicial complexes as expanders
Monday, January 27, 2014 Aram Harrow , Massachusetts Institute of Technology
Unique games, the Lasserre hierarchy and monogamy of entanglement
Tuesday, January 21, 2014 Siu Man Chan , Princeton University
Deeper Combinatorial Lower Bounds
Monday, December 16, 2013 Gil Cohen , Weizmann Institute
Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball
Tuesday, December 10, 2013 Ori Parzanchevski , Member, School of Mathematics
Simplicial complexes as expanders
Monday, December 9, 2013 Adi Shamir , Weizmann Institute
How Cryptosystems Are REALLY Broken
Tuesday, December 3, 2013 Allison Lewko , Columbia University; Member, School of Mathematics
Multi-party Interactive Coding
Monday, December 2, 2013 Adam Marcus , Yale University
A solution to Weaver's \(KS_2\)
Tuesday, November 26, 2013 Or Meir , Member, School of Mathematics
Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture
Monday, November 25, 2013 Joseph Landsberg , Texas A & M University
Geometry and matrix multiplication
Tuesday, November 19, 2013 Gillat Kol , Member, School of Mathematics
Interactive Channel Capacity
Monday, November 18, 2013 Brendan Juba , Harvard University
Efficient reasoning in PAC semantics
Tuesday, November 12, 2013 Edinah Gnang , Member, School of Mathematics
Hypermatrix Algebra, their spectral decomposition and applications
Monday, November 11, 2013 Toni Pitassi , University of Toronto
Communication Lower Bounds via Block Sensitivity
Tuesday, November 5, 2013 Anindya De , Member, School of Mathematics
Learning from positive examples
Monday, November 4, 2013 Vladimir Braverman , Johns Hopkins University
Approximating large frequency moments with pick-and-drop sampling
Tuesday, October 29, 2013
Monday, October 28, 2013
Tuesday, October 22, 2013 Van Vu , Yale University
Matrix perturbation with random noise and matrix recovery problems
Monday, October 21, 2013 Boaz Slomka , Tel Aviv University; Member, School of Mathematics
Fractional covering numbers, with an application to the Levi-Hadwiger conjecture for convex bodies
Tuesday, October 15, 2013 Noga Alon , Tel Aviv University; Visiting Professor, School of Mathematics
Minimal majority sequences
Monday, October 14, 2013 Yael Tauman-Kalai , Microsoft Research New England
Obfuscating Programs Against Algebraic Attacks
Tuesday, October 8, 2013 Ali Sinop , Member, School of Mathematics
Rounding Moment Based SDP Relaxations by Column Selection
Monday, October 7, 2013 Jacob Fox , Massachusetts Institute of Technology
Stanley-Wilf limits are typically exponential
Tuesday, October 1, 2013 Ali Kemal Sinop , Institute for Advanced Study; Member, School of Mathematics
Small set expander flows
Monday, September 30, 2013 Sanjeev Arora
Some provable bounds for deep learning
Tuesday, September 24, 2013 Mark Lewko , Member, School of Mathematics
Finite Field Restriction Estimates
Monday, September 23, 2013 Michael Krivelevich , Tel Aviv University
Using the DFS Algorithm for Finding Long Paths in Random and Pseudo-Random Graphs
Tuesday, May 14, 2013 No Seminar Talk
Monday, May 13, 2013 Raghu Meka , DIMACS (Rutgers); Member, School of Mathematics
Association Schemes, Non-Commutative Polynomials and Lasserre Lower Bounds for Planted Clique
Monday, May 13, 2013 Andrew Drucker , Member, School of Mathematics
Nondeterministic Direct Product Reductions and the Success Probability of SAT Solvers
Tuesday, May 7, 2013 No Seminar Talk
Monday, May 6, 2013 Rotem Oshman , University of Toronto
Tight Bounds for Set Disjointness in the Message-Passing Model
Tuesday, April 30, 2013 Michal Feldman , Hebrew University of Jerusalem
Combinatorial Walrasian Equilibrium
Monday, April 29, 2013 Michael Rabin , Harvard University and Columbia University
Cryptography and Preventing Collusion in Second Price (Vickery) Auctions
Tuesday, April 23, 2013 Klim Efremenko , Tel-Aviv University; Member, School of Mathematics
Uncertainty Principle
Monday, April 22, 2013 Daniel Kane , Stanford University
Diffuse Decompositions of Polynomials
Tuesday, April 16, 2013 No Seminar Talk
Monday, April 15, 2013 Irit Dinur , Weizmann Institute; Radcliffe institute
Analytical Approach to Parallel Repetition
Tuesday, April 9, 2013 Jozsef Beck , Rutgers, The State University of New Jersey
"What is Geometric Entropy, and Does it Really Increase?"
Monday, April 8, 2013 No Seminar Talk
Tuesday, April 2, 2013 Sushant Sachdeva , Princeton University
An Arithmetic Analogue of Fox's Improved Triangle Removal Lemma
Monday, April 1, 2013 Thomas Vidick , Massachusetts Institute of Technology
Device Independence: A New Paradigm for Randomness Manipulation?
Tuesday, March 26, 2013 No Seminar Talk
Monday, March 25, 2013 Madhu Sudan , Microsoft Research
New Locally Decodable Codes from Lifting
Tuesday, March 19, 2013 Hao Huang , University of California, Los Angeles; Member, School of Mathematics
Sensitivity Versus Block Sensitivity, II
Monday, March 18, 2013 Eli Ben-Sasson , Technion; Massachusetts Institute of Technology
Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity
Tuesday, March 12, 2013 Hao Huang , University of California, Los Angeles; Member, School of Mathematics
Sensitivity Versus Block Sensitivity, I
Monday, March 11, 2013 Tim Roughgarden , Stanford University
Intractability in Algorithmic Game Theory
Tuesday, March 5, 2013 Avi Wigderson , School of Mathematics, IAS
Derandomization of Probabilistic Logspace (The Nisan Variations)
Monday, March 4, 2013 Dhruv Mubayi , University of Illinois at Chicago
Quasirandom Hypergraphs
Tuesday, February 26, 2013 Avi Wigderson , School of Mathematics, IAS
Derandomizing BPL?
Monday, February 25, 2013 Emmanuel Abbe , Princeton University
Polar Codes and Randomness Extraction for Structured Sources
Tuesday, February 19, 2013 Shubhangi Saraf , Rutgers, The State University of New Jersey
The Chasm at Depth 3
Monday, February 18, 2013 Penny Haxell , University of Waterloo
Connectedness, Sperner's Lemma and Combinatorial Problems
Tuesday, February 12, 2013 Alex Lubotzky , Hebrew University
High Dimensional Expanders and Ramanujan Complexes
Monday, February 11, 2013 Liu Yang , School of Computer Science, Carnegie Mellon University
Mathematical Theories of Interaction with Oracles: Active Property Testing and New Models for Learning Boolean Functions
Tuesday, February 5, 2013 Manor Mendel , The Open University of Israel; Member, School of Mathematics
Ramsey Theory for Metric Spaces
Monday, February 4, 2013 Gil Kalai , Hebrew University; Yale University
Influences, Traces, Tribes, and Perhaps Also Thresholds
Tuesday, January 29, 2013 Manor Mendel , The Open University of Israel; Member, School of Mathematics
The Ribe Program
Monday, January 28, 2013 Xin Li , University of Washington
New Independent Source Extractors with Exponential Improvement
Tuesday, January 22, 2013 Jelani Nelson , Member, School of Mathematics
Sparsity Lower Bounds for Dimensionality Reducing Maps
Monday, January 21, 2013 Sebastien Bubeck , Princeton University
Clique Number of Random Geometric Graphs in High Dimension
Tuesday, January 15, 2013 Jelani Nelson , Member, School of Mathematics
OSNAP: Faster Numerical Linear Algebra Algorithms Via Sparser Subspace Embeddings
Monday, January 14, 2013 Pavel Hrubes , University of Washington
On Bilinear Complexity
Tuesday, December 18, 2012 (1) Raghu Meka and (2) Avi Wigderson , (1) DIMACS; (2) IAS
The SOS (aka Lassere/Positivestellensatz/Sum-of-Squares) System
Monday, December 17, 2012 No Seminar
Tuesday, December 11, 2012 Or Meir , Stanford University; Member, School of Mathematics
Combinatorial PCPs with Short Proofs
Monday, December 10, 2012 Vijay Vazirani , Georgia Institute of Technology
Matching: A New Proof for an Ancient Algorithm
Tuesday, December 4, 2012 Ran Raz , Weizmann Institute; Member, School of Mathematics
Delegation for Bounded Space
Monday, December 3, 2012 Mark Braverman , Princeton University
Information Complexity and Exact Communication Bounds
Tuesday, November 27, 2012 Jing Chen , Massachusetts Institute of Technology; Member, School of Mathematics
Computational Complexity in Mechanism Design
Monday, November 26, 2012 Michael Forbes , Massachusetts Institute of Technology
Polynomial Identity Testing of Read-Once Oblivious Algebraic Branching Progress
Tuesday, November 20, 2012 Joseph Landsberg , Texas A&M University
On the Complexity of Matrix Multiplication and Other Tensors
Monday, November 19, 2012 Jin-Yi Cai , University of Wisconsin
A Complete Dichotomy Rises from the Capture of Vanishing Signatures
Tuesday, November 13, 2012 No Seminar (Oberwolfach)
Monday, November 12, 2012 No Seminar (Oberwolfach)
Tuesday, November 6, 2012 Jing Chen , Massachusetts Institute of Technology; Member, School of Mathematics
Games, Solution Concepts, and Mechanism Design: A Very Short Introduction
Monday, November 5, 2012 Ben Rossman , Tokyo Institute of Technology
Query Complexity of Black-Box Search
Monday, October 29, 2012 Michal Feldman , Hebrew University and Harvard University
Combinatorial Walrasian Equilibrium
Tuesday, October 23, 2012 No Seminar (FOCS Meeting)
Monday, October 22, 2012 No Seminar (FOCS Meeting)
Tuesday, October 16, 2012 Andrew Drucker , Massachusetts Institute of Technology; Member, School of Mathematics
On the AND- and OR-Conjectures: Limits to Efficient Preprocessing
Monday, October 15, 2012 Tsuyoshi Ito , NEC Laboratories America, Inc.
A Multi-Prover Interactive proof for NEXP Sound Against Entangled Provers
Tuesday, October 9, 2012 Hao Huang , University of California, Los Angeles; Member, School of Mathematics
On the Conjectures of Nonnegative $k$-Sum and Hypergraph Matching
Monday, October 8, 2012 Amir Shpilka , Technion
Identity Testing of Tensors, Low Rank Recovery and Compressed Sensing
Tuesday, October 2, 2012 Alex Russell , University of Connecticut
Plug your ears! Graph isomorphism, siren of the algebraic seas, calls to your quantum helmsman.
Monday, October 1, 2012 Cris Moore , Santa Fe Institute
Random Vectors, Random Matrices, Permuted Products, Permanents, and Diagrammatic Fun
Tuesday, September 25, 2012 Greg Kuperberg , University of California, Davis
Koiran + Geometric Topology implies "Knottedness is in NP"
Monday, September 24, 2012 Greg Kuperberg , University of California, Davis
The Computational Complexity of Geometric Topology Problems
Tuesday, May 22, 2012 No seminar today (STOC Conference)
Monday, May 21, 2012 No seminar today (STOC Conference)
Tuesday, May 15, 2012 Klim Efremenko , Tel Aviv University
From Irreducible Representations to Locally Decodable Codes
Monday, May 14, 2012 Nisheeth Vishnoi , Microsoft Research, Bangalore
Are Lattice Based Cryptosystems Secure Enough?
Tuesday, May 8, 2012 Raghu Meka , Member, School of Mathematics
Pseudorandomness from Shrinkage
Monday, May 7, 2012 Pooya Hatami , University of Chicago
Topology of Norms Defined by Systems of Linear forms
Tuesday, May 1, 2012 Abhishek Bhowmick , University of Texas at Austin
Lower Bounds for Matching Vector Codes
Monday, April 30, 2012 Mario Szegedy , Rutgers, The State University of New Jersey
Randomized Greedy Algorithms for the Maximum Matching Problem with New Analysis
Tuesday, April 24, 2012 Srikanth Srinivasan , DIMACS
Pseudorandom Generators for Read-Once ACC^0
Monday, April 23, 2012 Salil Vadhan , Harvard University; Visiting Researcher Microsoft Research SVC; Visiting Scholar Stanford University
Computational Entropy
Tuesday, April 17, 2012 Laszlo Lovasz , Eotvos Lorand University, Budapest; Member, School of Mathematics
Nondeterministic Property Testing
Monday, April 16, 2012 Sushant Sachdeva , Princeton University
Near-Linear Time Approximation Algorithm for Balanced Separator
Tuesday, April 10, 2012 Swastik Kopparty , Rutgers University
List-Decoding Multiplicity Codes
Monday, April 9, 2012 Endre Csoka , Eotvos Lorand University, Budapest, Hungary
Random Local Algorithms
Tuesday, April 3, 2012 Parikshit Gopalan , Microsoft Research Silicon Valley, Mountain View, CA
Better Pseudorandom Generators from Milder Pseudorandom Restrictions
Monday, April 2, 2012 Pablo Azar , Massachusetts Institute of Technology
Rational Proofs
Tuesday, March 27, 2012 Luca Trevisan , Stanford University
Higher-Order Cheeger Inequalities
Monday, March 26, 2012 Jan Vondrak , IBM Almaden
Hardness of Randomized Truthful Mechanisms for Combinatorial Auctions
Tuesday, March 20, 2012 Miklos Abert , Alfred Renyi Institute of Mathematics, Budapest
Graph Convergence, Parameter Testing and Group Actions
Tuesday, March 20, 2012 Shachar Lovett , Member, School of Mathematics
The Quasi-Polynomial Freiman-Ruzsa Theorem of Sanders
Monday, March 19, 2012 Gregory Valiant , University of California, Berkeley
Optimal Estimators for Entropy, Support Size, and Related Properties
Tuesday, March 13, 2012 Jelani Nelson , Member, School of Mathematics
Applications of FT-Mollification II
Monday, March 12, 2012 Mina Teicher , Bar-Ilan University; Member, School of Mathematics
Computational Aspects in the Braid Group and Applications to Cryptography
Tuesday, March 6, 2012 Jelani Nelson , Member, School of Mathematics
Applications of FT-Mollification
Monday, March 5, 2012 Emanuele Viola , Northeastern University
The Complexity of Distributions
Tuesday, February 28, 2012 Christos Papadimitriou , University of California at Berkeley
Complexity, Approximability, and Mechanism Design
Monday, February 27, 2012 Noga Zewi , Technion
An Additive Combinatorics Approach to the Log-Rank Conjecture in Communication Complexity
Thursday, February 23, 2012 Amir Yehudayoff , Technion--Israel Institute of Technology
Building Expanders in Three Steps
Thursday, February 23, 2012 Boaz Barak , Microsoft Research New England
Zero Knowledge Proofs and Nuclear Disarmament
Tuesday, February 21, 2012 Joel Spencer , Courant Institute, NYU
Finding Needles in Exponential Haystacks
Monday, February 20, 2012 Venkat Guruswami , Carnegie Mellon University
Lasserre Hierarchy, Higher Eigenvalues, and Graph Partitioning
Tuesday, February 14, 2012 Benjamin Matschke , Member, School of Mathematics
On the Colored Tverberg Problem
Monday, February 13, 2012 Andrew Drucker , Massachusetts Institute of Technology
High-Confidence Predictions under Adversarial Uncertainty
Tuesday, February 7, 2012 David Zuckerman , University of Texas at Austin; Member, School of Mathematics
Randomness Extraction: A Survey
Monday, February 6, 2012 Fan Chung , University of California at San Diego
Graphlets: A Spectral Perspective for Graph Limits
Tuesday, January 31, 2012 Avi Wigderson , Herbert H. Maass Professor, School of Mathematics
A Survey of Lower Bounds for the Resolution Proof System
Monday, January 30, 2012 Santosh Vempala , Georgia Institute of Technology
Nearly Optimal Deterministic Algorithms Via M-Ellipsoids
Tuesday, January 24, 2012 Russell Impagliazzo , University of California, San Diego; Member, School of Mathematics
A Tutorial on the Likely Worst-Case Complexities of NP-Complete Problems
Monday, January 23, 2012 Michael Saks , Rutgers, The State University of New Jersey
An Optimal Lower Bound for File Maintenance
Tuesday, December 13, 2011 Christopher Beck , Princeton University
Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space
Monday, December 12, 2011 Pavel Hrubes , University of Calgary
Monotone Unification Problems
Tuesday, December 6, 2011 Menachem Magidor , Hebrew University
Can the Continuum Problem be Solved?
Monday, December 5, 2011 Mark Braverman , Princeton University
Towards Coding for Maximum Errors in Interactive Communication
Tuesday, November 29, 2011 Raghu Meka , Member, School of Mathematics
Shorter Long Code and Applications to Unique Games
Monday, November 28, 2011 Oded Regev , CNRS-ENS-Paris and Tel Aviv University
Entropy-Based Bounds on Dimension Reduction in L_1
Tuesday, November 22, 2011 Raghu Meka , Member, School of Mathematics
Shorter Long Code and Applications to Unique Games
Monday, November 21, 2011 Siavosh Benabbas , University of Toronto
An Isoperimetric Inequality for the Hamming Cube and Integrality Gaps in Bounded-Degree Graphs
Tuesday, November 15, 2011 Ankur Moitra , Massachusetts Institute of Technology; Member, School of Mathemtics
Vertex Sparsification: An Introduction, Connections and Applications
Monday, November 14, 2011 Mihalis Yannakakis , Columbia University
Polynomial Time Algorithms for Multi-Type Branching Processes and Stochastic Context-Free Grammars
Tuesday, November 8, 2011 Ankur Moitra , Massachusetts Institute of Technology; Member, School of Mathematics
Vertex Sparsification: An Introduction, Connections and Applications
Monday, November 7, 2011 Sigal Oren , Cornell University
How Bad is Forming Your Own Opinion
Tuesday, November 1, 2011 No Seminar (CCI Quantum Computation Workshop)
Monday, October 31, 2011 Jeff Kahn , Rutgers, The State University of New Jersey
Mantel's Theorem for Random Graphs
Tuesday, October 25, 2011 No Seminar (FOCS 2011 Meeting)
Monday, October 24, 2011 No Seminar (FOCS 2011 Meeting)
Tuesday, October 18, 2011 Ohad Feldheim , Tel Aviv University
Rigidity of 3-Colorings of the d-Dimensional Discrete Torus
Monday, October 17, 2011 Michael Krivelevich , Tel Aviv University
On the Number of Hamilton Cycles in Psdueo-Random Graphs
Tuesday, October 11, 2011 Balazs Szegedy , University of Toronto; Member, School of Mathematics
Limit Theories and Higher Order Fourier Analysis
Monday, October 10, 2011 Arkadev Chattopadhyay , University of Toronto
A Little Advice Can Be Very Helpful
Tuesday, October 4, 2011 Balazs Szegedy , University of Toronto; Member, School of Mathematics
Limit Theories and Higher Order Fourier Analysis
Monday, October 3, 2011 Jing Chen , Massachusetts Institute of Technology
Mechanism Design With Set-Theoretic Beliefs
Tuesday, September 27, 2011 Shubhangi Saraf , Microsoft Research; Member, School of Mathematics
Tight Lower Bounds for 2-query LCCs Over Finite fields
Monday, September 26, 2011 Benny Sudakov , University of California, Los Angeles
Nonnegative k-Sums, Fractional Covers, and Probability of Small Deviations
Tuesday, September 20, 2011 Shachar Lovett , Member, School of Mathematics
Existence of Small Families of t-wise Independent Permutations and t-Designs Via Local Limit Theorems