|
|
| 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 2005-2006 |
| Monday, September 26, 2005 | Stephen D. Miller , Hebrew University and Rutgers University
Expanders, L-functions, and the Elliptic Curve Discrete Logarithm Problem |
| Tuesday, September 27, 2005 | Alex Lubotzky , IAS
Property Tau and the Product Replacement Algorithm |
| Monday, October 3, 2005 | Terry Tao , University of California, Los Angeles
Szemeredi's Regularity Lemma Revisited |
| Tuesday, October 4, 2005 | NO SEMINAR |
| Monday, October 10, 2005 | Anup Rao , University of Texas, Austin
Randomness Extractors for a Constant Number Independent Sources of Polynomial Min-Entropy |
| Tuesday, October 11, 2005 | Avi Wigderson , IAS
Why and Which Expanders? |
| Tuesday, October 11, 2005 | Alex Lubotzky , IAS
From Ramanujan Graphs to Ramanujan Complexes |
| Monday, October 17, 2005 | Assaf Naor , Microsoft Research
Embeddings of Earthmover Metrics |
| Tuesday, October 18, 2005 | NO SEMINAR |
| Friday, October 21, 2005 | Gil Kalai , Hebrew University and Yale University
Combinatorics of Simplicial Complexes |
| Monday, October 24, 2005 | No Seminar Due to FOCS |
| Tuesday, October 25, 2005 | NO SEMINAR |
| Friday, October 28, 2005 | Leonid Gurvits , Los Alamos National Laboratory
Hyperbolic Polynomials and Van der Waerden/Schrijver-Valiant like Conjectures |
| Monday, October 31, 2005 | Ran Raz , Weizmann Institute of Science, Israel
Quantum Information and the PCP Theorem |
| Tuesday, November 1, 2005 | Eyal Rozenman , IAS
Expander Graphs on the Symmetric Groups |
| Tuesday, November 1, 2005 | Tim Steger , IAS
Buildings and the Spectra of their Laplacians |
| Monday, November 7, 2005 | Yuri Makarychev , Princeton University
Near-Optimal Algorithms for Unique Games |
| Tuesday, November 8, 2005 | Eyal Rozenman , IAS
Expander Graphs on the Symmetric Groups, Part II |
| Tuesday, November 8, 2005 | Tim Steger , IAS
Spectra of Laplacians of Buildings |
| Monday, November 14, 2005 | Various Speakers ,
|
| Monday, November 14, 2005 | NO SEMINAR |
| Tuesday, November 15, 2005 | Various Speakers ,
|
| Tuesday, November 15, 2005 | NO SEMINAR |
| Wednesday, November 16, 2005 | Various Speakers ,
|
| Thursday, November 17, 2005 | Various Speakers ,
|
| Friday, November 18, 2005 | Various Speakers ,
|
| Monday, November 21, 2005 | NO SEMINAR |
| Tuesday, November 22, 2005 | James Lee , IAS
Euclidean Embeddings of Finite Metric Spaces: Distortion and Expansion |
| Tuesday, November 22, 2005 | Bertrand Remy , Lyon
The Comparison Between Kac-Moody and Arithmetic Groups |
| Monday, November 28, 2005 | Tali Kaufman , MIT
Almost Orthogonal Linear Codes are Locally Testable |
| Tuesday, November 29, 2005 | Balazs Szegedy , IAS
Szemeredi's Regularity Lemma in Analysis |
| Wednesday, November 30, 2005 | Denis Osin , City College, New York
Uniform Kazhdan Groups |
| Monday, December 5, 2005 | Silvio Micali , MIT
Rational Secure Computation and Ideal Mechanism Design |
| Tuesday, December 6, 2005 | Madhu Sudan , MIT
Coding Theory: Survey of Recent Progress and Open Questions |
| Tuesday, December 6, 2005 | Andrzej Zuk , IAS
Around Property (T) |
| Monday, December 12, 2005 | Elad Schneidman , Princeton University
From Combinatorial Patterns to Strongly Correlated Networks States in Population Neural Code |
| Tuesday, December 13, 2005 | Benny Sudakov , Princeton University and IAS
Dependent Random Choice and Extremal Problems |
| Tuesday, December 13, 2005 | Rostislav Grigorchuk , Texas A & M
Hanoi Tower Groups, their Spectra and Growth of Diameters of Schreier Graphs |
| Tuesday, December 20, 2005 | Donald Cartwright , University of Sydney
Ramanujan Complexes of any Affine Type |
| Tuesday, December 20, 2005 | Andrei S. Rapinchuk , IAS
Normal Subgroups of the Multiplicative Group of a Finite Dimensional Division Algebra, and Valuations |
| Monday, January 16, 2006 | Adi Livnat , Princeton University
Internal Conflict in a Computational System |
| Tuesday, January 17, 2006 | Balazs Szegedy , IAS
Szemeredi's Regularity Lemma and Compactness |
| Tuesday, January 17, 2006 | Shahar Mozes , IAS
Linear Representations and Arithmeticity of Lattices in Products of Trees |
| Monday, January 23, 2006 | Santosh Vempala , MIT
Dispersion of Mass and the Complexity of Randomized Algorithms |
| Tuesday, January 24, 2006 | Van Vu , IAS
Random Discrete Matrices: A Survey |
| Tuesday, January 24, 2006 | Inna Korchagina , University of Birmingham
The Classification of Finite Simple Groups: Aspects of the Second Generation Proof |
| Monday, January 30, 2006 | Dror Weitz , DIMACS
From Trees to General Graphs: Counting Independent Sets up to the Tree Threshold |
| Tuesday, January 31, 2006 | Andrej Bogdanov , IAS
Cryptography and the P vs NP Question |
| Tuesday, January 31, 2006 | Ron Livnč , IAS
Paley Graphs and the Combinatorial Topology of the Bruhat Decomposition |
| Monday, February 6, 2006 | Various ,
|
| Monday, February 6, 2006 | |
| Tuesday, February 7, 2006 | Various ,
|
| Wednesday, February 8, 2006 | Various ,
|
| Thursday, February 9, 2006 | Various ,
|
| Friday, February 10, 2006 | Various ,
|
| Monday, February 13, 2006 | Joel Friedman , University of British Columbia
Cohomology in Grothendieck Topologies and Lower Bounds in Boolean Complexity |
| Tuesday, February 14, 2006 | Aner Shalev , Hebrew University
Quantum Computing and Finite Permutation Groups |
| Tuesday, February 14, 2006 | Tsachik Gelander , Yale University
Generalized Harmonic Maps Superridity and Uniformly Convex Metric Spaces |
| Monday, February 20, 2006 | Ron Blei , University of Connecticut
The Grothendieck Inequality Revisited |
| Tuesday, February 21, 2006 | Gregory Margulis , IAS and Yale University
Irrational Quadratic Forms II |
| Tuesday, February 21, 2006 | Alireza Salehi-Golsefidy , Yale University
Lattices of Minimum Covolume in Classical Chevalley Groups over $\mathbb F_q((t))$ |
| Thursday, February 23, 2006 | Dorit Aharonov , Hebrew University
The Jones Polynomial and Quantum Computation |
| Monday, February 27, 2006 | Michael Krivelevich , Tel Aviv University
Hamilton Cycles in Expanding and Highly Connected Graphs |
| Tuesday, February 28, 2006 | Po-Shen Loh , Princeton University
Independent Transversals in Locally Sparse Graphs |
| Tuesday, February 28, 2006 | George Willis , University of Newcastle, NSW
A Canonical Form for Automorphisms of Totally Disconnected Locally Compact Groups |
| Monday, March 6, 2006 | No seminar, due to talk of Christos Papadimitriou at Princeton University ,
|
| Tuesday, March 7, 2006 | Yair Glasner , IAS
Strong Approximation in Random Towers of Graphs |
| Tuesday, March 7, 2006 | Zoran Sunik , Texas A & M
Asymptotics and Spectra of Cayley and Schreier Graphs of Branch Groups |
| Monday, March 13, 2006 | Adi Akavia , MIT
On the (Im)possibility of Basing One-Way Functions on NP-Hardness |
| Tuesday, March 14, 2006 | Balazs Szedgedy , IAS
Group Theoretic Algorithms For Fast matrix Multiplication |
| Thursday, March 16, 2006 | Mikkel Thorup , AT & T
Time-Space Trade-Offs for Predecessor Search |
| Monday, March 20, 2006 | Tibor Szabo , ETH
Relaxed Two-Coloring of Cubic Graphs |
| Tuesday, March 21, 2006 | Mikhail Ershov , IAS
Golod-Shafarevich Groups with Property (T) and Kac-Moody Groups |
| Tuesday, March 21, 2006 | Yehuda Shalom , IAS
Kazhdan's Property (T) for Linear Groups Over General Rings |
| Tuesday, March 21, 2006 | Fritz Grunewald , IAS
Linear Representations of the Automorphism Group of a Free Group |
| Tuesday, March 21, 2006 | Martin Kassabov , Cornell University
Cartesian Products as Profinite Completions and Representation Growth of Groups |
| Monday, March 27, 2006 | Alan Frieze , Carnegie Mellon University
The Cover Time of Random Walks on Random Graphs |
| Tuesday, March 28, 2006 | Noga Alon , Tel Aviv University and IAS
The Grothendieck Constant of an Expander |
| Monday, April 3, 2006 | Vladlen Koltun , Stanford University
The Arrangement Method for Linear Programming |
| Tuesday, April 4, 2006 | Elon Lindenstrauss , Princeton University
Periodic Orbits and Extractors |
| Tuesday, April 4, 2006 | Alan Reid , University of Texas, Austin
Isospectrality and Commensurability |
| Monday, April 10, 2006 | Elchanan Mossel , University of California, Berkeley
Computational Hardness From Gaussian Isoperimetry: On Hardness of Graph Coloring, the Shape of Double Bubbles and Related Problems |
| Tuesday, April 11, 2006 | Elad Hazan , Princeton University
New Techniques in Online Game Playing |
| Monday, April 17, 2006 | Ashish Goel , Stanford University
Simultaneous Optimization and Fairness |
| Tuesday, April 18, 2006 | Avi Wigderson , IAS
Black Boxes, Inc. |
| Tuesday, April 18, 2006 | Alex Furman , University of Illinois at Chicago
Actions of Product Groups on Manifolds |
| Monday, April 24, 2006 | No Seminar Due to DIMACS Workshop ,
Click here for details about DIMACS Workshop |
| Tuesday, April 25, 2006 | No Seminar Due to DIMACS Workshop ,
Click here for details about DIMACS Workshop |
| Tuesday, April 25, 2006 | Yves de Cornulier , École Normale Supérieure
Relative Property T in Lie Groups and their Lattices |
| Monday, May 1, 2006 | Jeff Kahn , Rutgers University
Many Hamiltonian Cycles |
| Tuesday, May 2, 2006 | Alexander Razborov , IAS
On the Minimal Density of Triangles in Graphs |
| Tuesday, May 2, 2006 | George Willis , University of Newcastle
Almost Normal Subgroups of Lattices |
| Monday, May 8, 2006 | Michael Capalbo , DIMACS
Universal Graphs |
| Tuesday, May 9, 2006 | Alexander Razborov , IAS
On the Minimal Density of Triangles in Graphs (continued) |
| Monday, May 15, 2006 | Danny Gutfreund , Harvard University
New Connections Between Derandomization, Worst-Case Complexity and Average-Case Complexity |
| Tuesday, May 16, 2006 | Shiri Artstein , IAS
Randomness Reduction in Some Results of Asympotic Geometric Analysis |
| Tuesday, May 23, 2006 | Tim Steger , IAS
On Margulis' Normal Subgroup Theorem |
| Tuesday, July 11, 2006 | Scott Aaronson , University of Waterloo
The learnability of Quantum States |
| Tuesday, September 19, 2006 | Avi Wigderson , Faculty, School of Mathematics
The Sum-Product Theorem and Applications |
| 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 |