|
|
| 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 2007-2008 |
| 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 |