|
|
| 1 Einstein Drive • Princeton, New Jersey • 08540 US • Tel: 609-734-8100 • Fax: 609-951-4459 • math@math.ias.edu |
| Past Combinatorics and Complexity Theory 2006-2007 |
| Monday, September 25, 2006 | Michel Goemans , Massachusetts Institute of Technology
Minimum Bounded-Degree Spanning Trees Through Matroid Intersection |
| Tuesday, September 26, 2006 | Avi Wigderson , Faculty, School of Mathematics
Sum-Product Theorem in Finite Fields (Continued) |
| Monday, October 2, 2006 | NO SEMINAR - Yom Kippur ,
|
| Tuesday, October 3, 2006 | Jonathan Kelner , Massachusetts Institute of Technology; Member, School of Mathematics
A Randomized Polynomial-Time Simplex Algorithm for Linear Programming |
| Monday, October 9, 2006 | Mario Szegedy , Rutgers, The State University of New Jersey
Languages with Bounded Multiparty Communication Complexity |
| Tuesday, October 10, 2006 | Aaron Siegel , Mathematical Sciences Research Institute; Member, School of Mathematics
An Invitation to Combinatorial Games |
| Monday, October 16, 2006 | Alex Healy , Harvard University
Randomness-Efficient Sampling Within NC^1 |
| Tuesday, October 17, 2006 | Aaron Siegel , Mathematical Sciences Research Institute; Member, School of Mathematics
An Invitation to Combinatorial Games |
| Monday, October 23, 2006 | NO SEMINAR - FOCS Conference ,
|
| Tuesday, October 24, 2006 | NO SEMINAR - FOCS Conference ,
|
| Monday, October 30, 2006 | Anup Rao , University of Texas
2-Source Dispersers for n^{o(1)} Entropy, and Ramsey Graphs Beating theFrankl-Wilson Construction |
| Tuesday, October 31, 2006 | Anup Rao , University of Texas
2-Source Dispersers for Sub-Polynomial Min-Entropy and Ramsey Graphs Beating the Frankl Wilson Construction |
| Monday, November 6, 2006 | Gil Kalai , The Hebrew University of Jerusalem; Yale University
Towards Harmful Low-Rate Noise Models for Quantum Computers |
| Tuesday, November 7, 2006 | Neeraj Kayal , Indian Institute of Technology, India; Member, School of Mathematics
Solvability of Polynomial Equations over Finite Fields |
| Monday, November 13, 2006 | Elwyn Berlekamp , University of California, Berkeley
Coupon Go |
| Tuesday, November 14, 2006 | Julia Chuzhoy , Massachusetts Institute of Technology; Member, School of Mathematics
Cut Problems in Graphs: Algorithms and Complexity |
| Monday, November 20, 2006 | NO SEMINAR ,
|
| Tuesday, November 21, 2006 | NO SEMINAR ,
|
| Monday, November 27, 2006 | Sergey Yekhanin , Massachusetts Institute of Technology
New Locally Decodable Codes and Private Information Retrieval Schemes |
| Tuesday, November 28, 2006 | Emanuele Viola , Harvard University; Member, School of Mathematics
New Correlation Bounds for GF(2) Polynomials Using the Gowers Norm |
| Monday, December 4, 2006 | Silvio Micali , Massachusetts Institute of Technology
Transparent Achievement of Correlated Equilibrium |
| Tuesday, December 5, 2006 | Vladimir Trifonov , University of Texas at Austin; Member, School of Mathematics
On the Correlation Between Parity and Modular Polynomials |
| Monday, December 11, 2006 | Jan Vondrak , Princeton University
Approximation Algorithms for Combinatorial Allocation Problems |
| Tuesday, December 12, 2006 | Benny Sudakov , Princeton University
Cycles and Cliques Minors in Expanders |
| Wednesday, December 13, 2006 | Alistair Sinclair , Computer Science Division, University of California, Berkeley
Permanents, Determinants and Non-Commutativity |
| Monday, December 18, 2006 | Xi Chen , Tsinghua University, Beijing
On the Computation and Approximation of Two-Player Nash Equilibria |
| Tuesday, December 19, 2006 | Alex Gamburd , University of California at Santa Cruz
Sum-Product Estimates, Expanders, and Sieving |
| Monday, January 15, 2007 | Warren Schudy , Brown University
How to Rank with Few Errors: A PTAS for Weighted Feedback Arc Set on Tournaments |
| Tuesday, January 16, 2007 | Oded Schwartz , Tel-Aviv University
An Elementary Construction of Constant-Degree Expanders |
| Monday, January 22, 2007 | Van Vu , Rutgers, The State University of New Jersey
On the Condition Number of a Randomly Perturbed Matrix |
| Tuesday, January 23, 2007 | Neeraj Kayal , Member, School of Mathematics
The Polynomial Identity Testing Problem |
| Monday, January 29, 2007 | Michael Ben-Or , Hebrew University, Jerusalem
Secure Multipary Quantum Computation |
| Tuesday, January 30, 2007 | Emanuele Viola , Member, School of Mathematics
On Approximate Majority and Probabilistic Time |
| Monday, February 5, 2007 | John Conway , Princeton University
Integral Lexicographic Codes |
| Tuesday, February 6, 2007 | Tali Kaufman , Massachusetts Institute of Technology; Member, School of Mathematics
Algebraic Property Testing |
| Monday, February 12, 2007 | Michael Krivelevich , Tel-Aviv University
Biased Positional Games and Thin Hypergraphs with Large Covers |
| Tuesday, February 13, 2007 | Nir Ailon , Princeton University; Member, School of Mathematics
Fast Johnson-Lindenstrauss Transform(s) |
| Monday, February 19, 2007 | Salil Vadhan , Harvard University
Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes |
| Tuesday, February 20, 2007 | Tali Kaufman , Massachusetts Institute of Technology; Member, School of Mathematics
Algebraic Property Testing - Part II |
| Monday, February 26, 2007 | Andrej Bogdanov , DIMACS
Hardness Amplification for Errorless Heuristics |
| Tuesday, February 27, 2007 | Alexander Razborov , Steklov Mathematical Institute; Member, School of Mathematics
A Product Theorem in Free Groups |
| Monday, March 5, 2007 | Satyen Kale , Princeton University
Efficient Algorithms Using the Multiplicative Weights Update Method |
| Tuesday, March 6, 2007 | Alexander Razborov , Steklov Mathematical Institute; Member, School of Mathematics
A Product Theorem in Free Groups (Continued) |
| Monday, March 12, 2007 | Sanjeev Khanna , University of Pennsylvania
Disjoint Paths in Networks |
| Tuesday, March 13, 2007 | Allan Borodin , University of Toronto; Member, School of Mathematics
The Design and Analysis of Simple Algorithms (for Search and Optimization) |
| Monday, March 19, 2007 | David Xiao , Princeton University
A Cryptographic Study of Secure Internet Measurement |
| Tuesday, March 20, 2007 | Allan Borodin , University of Toronto; Member, School of Mathematics
The Design and Analysis of Simple Algorithms: Part II |
| Monday, March 26, 2007 | Konstantin Makarychev , Princeton University
Near-Optimal Algorithms for Maximum Constraint Satisfaction |
| Tuesday, March 27, 2007 | Andrew Klapper , University of Kentucky
Pseudo-Random Number Generation by Algebraic Means |
| Monday, April 2, 2007 | Bernard Chazelle , Princeton University
Data-Powered Computing |
| Tuesday, April 3, 2007 | Andrew Klapper , University of Kentucky
Pseudo-Random Number Generation by Algebraic Means (continued) |
| Monday, April 9, 2007 | Christos Papadimitriou , University of California at Berkeley
The Complexity of Nash Equilibria |
| Tuesday, April 10, 2007 | Nir Ailon , Princeton University; Member, School of Mathematics
Aggregating Inconsistent Information: Ranking and Clustering |
| Monday, April 16, 2007 | Nir Halman , Massachusetts Institute of Technology
Fully Polynomial Time Approximation Schemes for Stochastic Dynamic Programs |
| Tuesday, April 17, 2007 | Peter Sarnak , Princeton University; Member, School of Mathematics
Expanders in Number Theory |
| Monday, April 23, 2007 | Guy Rothblum , Massachusetts Institute of Technology
Disigning Efficient Program Checkers by Delegating Their Work |
| Tuesday, April 24, 2007 | Nir Ailon , Princeton University; Member, School of Mathematics
Consensus Clustering, Hieraracical Clustering and Phylogeny |
| Monday, April 30, 2007 | Elwyn Berlekamp , University of California at Berkeley
History of the Theory of Error-Correcting Codes |
| Tuesday, May 1, 2007 | Emanuele Viola , Harvard University; Member, School of Mathematics
One-Way Multi-Party Communication Lower Bound for Pointer Jumping with Applications |
| Monday, May 7, 2007 | Eric Allender , Rutgers, The State University of New Jersey
Reachability Problems: An Update |
| Tuesday, May 8, 2007 | Toniann Pitassi , University of Toronto
An Exponential Time/Space Speedup for Resolution |
| Monday, May 14, 2007 | Chandra Chekuri , University of Illinois at Urbana-Champaign
Approximation Algorithms for Buy-at-Bulk Nework Design |
| Thursday, May 17, 2007 | Boaz Barak , Princeton University
Proof of the Parallel Repetition Theorem |
| Tuesday, May 22, 2007 | Alexander Razborov , Member; School of Mathematics
Expander Codes and Somewhat Euclidean Expllicit Sections |
| Tuesday, June 5, 2007 | Nir Ailon , Princeton University
Fast Dimension Reduction Using Rademacher Series on Dual BCH Codes |
| Monday, September 17, 2007 | Scott Aaronson , Massachusetts Instittute of Technology
Algebrization: A New Barrier in Complexity Theory |
| Monday, September 24, 2007 | Madhu Sudan , Massachusetts Institute of Technology
Towards Universal Semantic Communiction |
| Monday, September 24, 2007 | Anup Rao , University of Texas at Austin; Member, School of Mathematics
Parallel Repetition in Multiplayer Interactive Proofs |
| Tuesday, September 25, 2007 | Venkatesan Guruswami , University of Washington; Member, School of Mathematics
Hardness of Solving Sparse Overdetermined Linear Systems |
| Tuesday, September 25, 2007 | Tim Gowers , Cambridge University
Applications of Quadratic Fourier Analysis |
| Monday, October 1, 2007 | Alexander Sherstov , University of Texas at Austin
The Pattern Matrix Method for Lower Bounds on Quantum Communication |
| Tuesday, October 2, 2007 | Alexander Sherstov , University of Texas at Austin
Unbounded-Error Communication Complexity of Symmetric Functions |
| Tuesday, October 2, 2007 | Tom Sanders , University of Cambridge, UK; Member, School of Mathematics
Difference Sets and the Primes |
| Monday, October 8, 2007 | Joel Spencer , New York University
Erdos-Renyi Phase Transition |
| Tuesday, October 9, 2007 | Russell Impagliazzo , University of California, San Diego; Member, School of Mathematics
New Proofs of (New) Direct Product Theorems |
| Tuesday, October 9, 2007 | Endre Szemeredi , Rutgers, The State University of New Jersey; Member, School of Mathematics
On Square Sum-Free Sets |
| Monday, October 15, 2007 | Zeev Dvir , Weizmann Institute of Science
Extractors and Rank Extractors for Polynomial Sources |
| Tuesday, October 16, 2007 | Tali Kaufman , Member; School of Mathematics
Sparse Random Linear Codes are Locally Decodable and Testable |
| Tuesday, October 16, 2007 | Melvyn Nathanson , City University of New York; Member, School of Mathematics
Problems in Additive Number Theory |
| Monday, October 22, 2007 | |
| Tuesday, October 23, 2007 | |
| Tuesday, October 23, 2007 | Tamar Ziegler , University of Michigan
Polynomial Progressions in Primes |
| Monday, October 29, 2007 | Luca Trevisan , University of California, Berkeley; Member, School of Mathematics
Dense Subsets of Pseudorandom Objects |
| Tuesday, October 30, 2007 | Kevin Costello , Rutgers, The State University of New Jersey
Balancing Gaussian Vectors |
| Tuesday, October 30, 2007 | Terrence Tao , University of California, Los Angeles
On the Property Testing of Hereditary Graph and Hypergraph Properties |
| Monday, November 5, 2007 | Vijay Vazirani , Georgia Institute of Technology
Markets and the Primal-Dual Paradigm |
| Tuesday, November 6, 2007 | Sergey Yekhanin , Massachusetts Institute of Technology; Member, School of Mathematics
Locally Decodable Codes from Nice Subsets of Finite Fields and Prime Factors of Mersenne Numbers |
| Tuesday, November 6, 2007 | Kevin Costello , Rutgers, The State University of New Jersey
The Rank of Symmetric Matrices |
| Monday, November 12, 2007 | Jin-Yi Cai , University of Wisconsin, Madison
Developments in Holographic Algorithms |
| Tuesday, November 13, 2007 | Jozsef Solymosi , University of British Columbia; Member, School of Mathematics
Applications of the Removal Lemma |
| Tuesday, November 13, 2007 | Laszlo Babai , University of Chicago
Product Growth and Mixing in Finite Groups: Variations on a Theme of Gowers |
| Wednesday, November 14, 2007 | Julia Wolf , University of Cambridge, UK; Member, School of Mathematics
Decompositions into Quadratic Phase Functions |
| Thursday, November 15, 2007 | Alexander Gamburd , University of California at Santa Cruz
Sum-Product Estimates and Expanders |
| Monday, November 19, 2007 | Yishay Mansour , Tel Aviv University & Google
On a Network Creation Game |
| Tuesday, November 20, 2007 | Benny Sudakov , University of California, Los Angeles; Member, School of Mathematics
Density Theorems for Bipartite Graphs and Related Ramsey-Type Results |
| Monday, November 26, 2007 | Subhash Khot , Courant Institute, New York University
On Hardness of Learning Intersection of Two Halfspaces |
| Tuesday, November 27, 2007 | Xi Chen , Tsinghua University, China; Member, School of Mathematics
The Approximation Complexity of Win-Lose Games |
| Tuesday, November 27, 2007 | Ilya Shkredov , Moscow State University, Russia; Member, School of Mathematics
Inverse Theorems for Large Subsets of sums of Dissociated Sets |
| Monday, December 3, 2007 | Umesh Vazirani , University of California, Berkeley
Expander Flows, Graph Spectra and Graph Separators |
| Tuesday, December 4, 2007 | Konstantinos Daskalakis , University of California, Berkeley
Optimal Phylogenetic Reconstruction |
| Wednesday, December 5, 2007 | Alexey Glibichuk , Moscow State University, Russia; Member, School of Mathematics
Some Properties of Sum and Product Sets in Finite Fields |
| Monday, January 21, 2008 | Avinatan Hassidim , Hebrew University
Noisy Binary Search and Applications |
| Tuesday, January 22, 2008 | Adi Akavia , Massachusetts Institute of Technology; Member, School of Mathematics
A Study of Multiplication Codes |
| Monday, January 28, 2008 | Emanuele Viola , Columbia University
Hardness Amplification Proofs Require Majority |
| Tuesday, January 29, 2008 | Avi Wigderson, IAS ,
Arithmetic Complexity -- The Power of Partial Derivatives |
| Monday, February 4, 2008 | Michael Krivelevich , Tel Aviv University
The Rules of the Game |
| Tuesday, February 5, 2008 | Avi Wigderson , IAS
Arithmetic Complexity -- The Power of Partial Derivatives |
| Monday, February 11, 2008 | Valentine Kabanets , Simon Fraser University
Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized |
| Tuesday, February 12, 2008 | Neeraj Kayal , DIMACS
Efficient Algorithms for Some Algebraic Problems |
| Monday, February 18, 2008 | Yury Makarychev , Microsoft Research
Integrality Gaps for Sherali-Adams Relaxations |
| Tuesday, February 19, 2008 | Christos Papadimitriou , University of California at Berkeley
New Results and Open Problems in Computing Nash Equilibria |
| Monday, February 25, 2008 | Shai Halevi , IBM T.J. Watson Research Center
Security Under Key-Dependent Inputs |
| Tuesday, February 26, 2008 | Arie Matsliah , Technion
Sound 3-Query PCPPs Are Long |
| Monday, March 3, 2008 | Troy Lee , Rutgers University
Disjointness is Hard in the Multi-Party Number-On-The-Forehead Model |
| Tuesday, March 4, 2008 | Alexander Razborov , IAS
The Sign-Rank of AC^0 |
| Monday, March 10, 2008 | Philip Matchett Wood , Rutgers University
A Frieman Isomorphism-type Lemma for Polynomials |
| Tuesday, March 11, 2008 | Alexander Razborov , IAS
The Sign-Rank of AC^0 (continued) |
| Monday, March 17, 2008 | |
| Tuesday, March 18, 2008 | |
| Monday, March 24, 2008 | Paul Valiant , Massachusetts Institute of Technology
Testing Symmetric Properties of Distributions |
| Tuesday, March 25, 2008 | Amit Sahai , UCLA
Expander Cryptography -- Cryptography With Constant Computational Overhead |
| Monday, March 31, 2008 | Benny Applebaum , Princeton University
On Proving Hardness of Improper Learning from Worst-Case Assumptions |
| Tuesday, April 1, 2008 | Tali Kaufman , Member, School of Mathematics
The Distribution of Polynomials Over Finite Fields |
| Monday, April 7, 2008 | Mohammad Mohmoody Ghidary , Princeton University
Merkle Puzzles are Optimal |
| Tuesday, April 8, 2008 | Anup Rao , University of Texas at Austin; Member, School of Mathematics
Spherical Cubes, or Coordinated Random Choices in High Dimensions |
| Monday, April 14, 2008 | Assaf Naor , Courant Institute
Embeddings of Discrete Groups and the Speed of Random Walks |
| Tuesday, April 15, 2008 | Noga Alon , Tel Aviv University; Visiting Professor, School of Mathematics
Nearly Diagonally Dominant Matrices and Their Applications |
| Monday, April 21, 2008 | NO SEMINAR DUE TO PASSOVER ,
|
| Tuesday, April 22, 2008 | NO SEMINAR DUE TO PASSOVER ,
|
| Monday, April 28, 2008 | Shai Halevi , IBM T. J. Watson Research Center
Security Under Key-Dependent Inputs |
| Tuesday, April 29, 2008 | Rani Hod , Tel Aviv University
Optimal Monotone Encodings |
| Monday, May 5, 2008 | NO SEMINAR ,
|
| Tuesday, May 6, 2008 | NO SEMINAR ,
|
| Monday, May 12, 2008 | Venkatesan Guruswami , University of Washington; Member, School of Mathematics
Artin Map, Cyclotomic Function Fields, and Folded List-Decodable Codes |
| Tuesday, May 13, 2008 | Endre Szemeredi , Rutgers University; Member, School of Mathematics
A Dirac-Type Theorem for 3-Uniform Hypergraphs |
| Friday, May 16, 2008 | Amir Shpilka , Technion
Reconstruction of Depth-3 Arithmetic Circuits |
| Tuesday, May 20, 2008 | No Seminar Due to STOC Conference ,
|
| Friday, May 23, 2008 | Zeev Dvir , Weizmann Institute
The finite field Kakeya conjecture. |
| Monday, May 26, 2008 | Institute Closed in Observance of Memorial Day ,
|
| Tuesday, May 27, 2008 | Nir Halman , MIT; Member, School of Mathematics
Approximating Functions in Logarithmic Space and Time: A "Plug & Play" Approach |
| Tuesday, June 10, 2008 | Mark Braverman , University of Toronto
Computability and Complexity of Julia sets |
| to the Seminars page |
| to the CSDM page |