2006-2007 seminars

Tuesday, June 5, 2007
Fast Dimension Reduction Using Rademacher Series on Dual BCH Codes
Nir Ailon (Princeton University)
Tuesday, May 22, 2007
Expander Codes and Somewhat Euclidean Expllicit Sections
Alexander Razborov (Member and School of Mathematics)
Thursday, May 17, 2007
Proof of the Parallel Repetition Theorem
Boaz Barak (Princeton University)
Monday, May 14, 2007
Approximation Algorithms for Buy-at-Bulk Nework Design
Chandra Chekuri (University of Illinois at Urbana-Champaign)
Tuesday, May 8, 2007
An Exponential Time/Space Speedup for Resolution
Toniann Pitassi (University of Toronto)
Monday, May 7, 2007
Reachability Problems: An Update
Eric Allender (Rutgers, The State University of New Jersey)
Tuesday, May 1, 2007
One-Way Multi-Party Communication Lower Bound for Pointer Jumping with Applications
Emanuele Viola (Harvard University and Member, School of Mathematics)
Monday, April 30, 2007
History of the Theory of Error-Correcting Codes
Elwyn Berlekamp (University of California at Berkeley)
Tuesday, April 24, 2007
Consensus Clustering, Hieraracical Clustering and Phylogeny
Nir Ailon (Princeton University and Member, School of Mathematics)
Monday, April 23, 2007
Disigning Efficient Program Checkers by Delegating Their Work
Guy Rothblum (Massachusetts Institute of Technology)
Tuesday, April 17, 2007
Expanders in Number Theory
Peter Sarnak (Princeton University and Member, School of Mathematics)
Monday, April 16, 2007
Fully Polynomial Time Approximation Schemes for Stochastic Dynamic Programs
Nir Halman (Massachusetts Institute of Technology)
Tuesday, April 10, 2007
Aggregating Inconsistent Information: Ranking and Clustering
Nir Ailon (Princeton University and Member, School of Mathematics)
Monday, April 9, 2007
The Complexity of Nash Equilibria
Christos Papadimitriou (University of California at Berkeley)
Tuesday, April 3, 2007
Pseudo-Random Number Generation by Algebraic Means (continued)
Andrew Klapper (University of Kentucky)
Monday, April 2, 2007
Data-Powered Computing
Bernard Chazelle (Princeton University)
Tuesday, March 27, 2007
Pseudo-Random Number Generation by Algebraic Means
Andrew Klapper (University of Kentucky)
Monday, March 26, 2007
Near-Optimal Algorithms for Maximum Constraint Satisfaction
Konstantin Makarychev (Princeton University)
Tuesday, March 20, 2007
The Design and Analysis of Simple Algorithms: Part II
Allan Borodin (University of Toronto and Member, School of Mathematics)
Monday, March 19, 2007
A Cryptographic Study of Secure Internet Measurement
David Xiao (Princeton University)
Tuesday, March 13, 2007
The Design and Analysis of Simple Algorithms (for Search and Optimization)
Allan Borodin (University of Toronto and Member, School of Mathematics)
Monday, March 12, 2007
Disjoint Paths in Networks
Sanjeev Khanna (University of Pennsylvania)
Tuesday, March 6, 2007
A Product Theorem in Free Groups (Continued)
Alexander Razborov (Steklov Mathematical Institute and Member, School of Mathematics)
Monday, March 5, 2007
Efficient Algorithms Using the Multiplicative Weights Update Method
Satyen Kale (Princeton University)
Tuesday, February 27, 2007
A Product Theorem in Free Groups
Alexander Razborov (Steklov Mathematical Institute and Member, School of Mathematics)
Monday, February 26, 2007
Hardness Amplification for Errorless Heuristics
Andrej Bogdanov (DIMACS)
Tuesday, February 20, 2007
Algebraic Property Testing - Part II
Tali Kaufman (Massachusetts Institute of Technology and Member, School of Mathematics)
Monday, February 19, 2007
Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes
Salil Vadhan (Harvard University)
Tuesday, February 13, 2007
Fast Johnson-Lindenstrauss Transform(s)
Nir Ailon (Princeton University and Member, School of Mathematics)
Monday, February 12, 2007
Biased Positional Games and Thin Hypergraphs with Large Covers
Michael Krivelevich (Tel-Aviv University)
Tuesday, February 6, 2007
Algebraic Property Testing
Tali Kaufman (Massachusetts Institute of Technology and Member, School of Mathematics)
Monday, February 5, 2007 Integral Lexicographic Codes
John Conway (Princeton University)
Tuesday, January 30, 2007
On Approximate Majority and Probabilistic Time
Emanuele Viola (Member, School of Mathematics)
Monday, January 29, 2007
Secure Multipary Quantum Computation
Michael Ben-Or (Hebrew University, Jerusalem)
Tuesday, January 23, 2007
The Polynomial Identity Testing Problem
Neeraj Kayal (Member, School of Mathematics)
Monday, January 22, 2007
On the Condition Number of a Randomly Perturbed Matrix
Van Vu (Rutgers, The State University of New Jersey)
Tuesday, January 16, 2007
An Elementary Construction of Constant-Degree Expanders
Oded Schwartz (Tel-Aviv University)
Monday, January 15, 2007
How to Rank with Few Errors: A PTAS for Weighted Feedback Arc Set on Tournaments
Warren Schudy (Brown University)
Tuesday, December 19, 2006
Sum-Product Estimates, Expanders, and Sieving
Alex Gamburd (University of California at Santa Cruz)
Monday, December 18, 2006
On the Computation and Approximation of Two-Player Nash Equilibria
Xi Chen (Tsinghua University, Beijing)
Wednesday, December 13, 2006
Permanents, Determinants and Non-Commutativity
Alistair Sinclair (Computer Science Division, University of California, Berkeley)
Tuesday, December 12, 2006
Cycles and Cliques Minors in Expanders
Benny Sudakov (Princeton University)
Monday, December 11, 2006
Approximation Algorithms for Combinatorial Allocation Problems
Jan Vondrak (Princeton University)
Tuesday, December 5, 2006
On the Correlation Between Parity and Modular Polynomials
Vladimir Trifonov (University of Texas at Austin and Member, School of Mathematics)
Monday, December 4, 2006
Transparent Achievement of Correlated Equilibrium
Silvio Micali (Massachusetts Institute of Technology)
Tuesday, November 28, 2006
New Correlation Bounds for GF(2) Polynomials Using the Gowers Norm
Emanuele Viola (Harvard University and Member, School of Mathematics)
Monday, November 27, 2006
New Locally Decodable Codes and Private Information Retrieval Schemes
Sergey Yekhanin (Massachusetts Institute of Technology)
Tuesday, November 21, 2006 COMPUTER SCIENCE/DISCRETE MATH II
NO SEMINAR
Monday, November 20, 2006 COMPUTER SCIENCE/DISCRETE MATH I
NO SEMINAR
Tuesday, November 14, 2006
Cut Problems in Graphs: Algorithms and Complexity
Julia Chuzhoy (Massachusetts Institute of Technology and Member, School of Mathematics)
Monday, November 13, 2006
Coupon Go
Elwyn Berlekamp (University of California, Berkeley)
Tuesday, November 7, 2006
Solvability of Polynomial Equations over Finite Fields
Neeraj Kayal (Indian Institute of Technology, India and Member, School of Mathematics)
Monday, November 6, 2006
Towards Harmful Low-Rate Noise Models for Quantum Computers
Gil Kalai (The Hebrew University of Jerusalem and Yale University)
Tuesday, October 31, 2006
2-Source Dispersers for Sub-Polynomial Min-Entropy and Ramsey Graphs Beating the Frankl Wilson Construction
Anup Rao (University of Texas)
Monday, October 30, 2006
2-Source Dispersers for n^{o(1)} Entropy, and Ramsey Graphs Beating theFrankl-Wilson Construction
Anup Rao (University of Texas)
Tuesday, October 24, 2006 COMPUTER SCIENCE/DISCRETE MATH II
NO SEMINAR - FOCS Conference
Monday, October 23, 2006 COMPUTER SCIENCE/DISCRETE MATH I
NO SEMINAR - FOCS Conference
Tuesday, October 17, 2006
An Invitation to Combinatorial Games
Aaron Siegel (Mathematical Sciences Research Institute and Member, School of Mathematics)
Monday, October 16, 2006
Randomness-Efficient Sampling Within NC^1
Alex Healy (Harvard University)
Tuesday, October 10, 2006
An Invitation to Combinatorial Games
Aaron Siegel (Mathematical Sciences Research Institute and Member, School of Mathematics)
Monday, October 9, 2006
Languages with Bounded Multiparty Communication Complexity
Mario Szegedy (Rutgers, The State University of New Jersey)
Tuesday, October 3, 2006
A Randomized Polynomial-Time Simplex Algorithm for Linear Programming
Jonathan Kelner (Massachusetts Institute of Technology and Member, School of Mathematics)
Monday, October 2, 2006 COMPUTER SCIENCE/DISCRETE MATH I
NO SEMINAR - Yom Kippur
Tuesday, September 26, 2006
Sum-Product Theorem in Finite Fields (Continued)
Avi Wigderson (Faculty, School of Mathematics)
Monday, September 25, 2006
Minimum Bounded-Degree Spanning Trees Through Matroid Intersection
Michel Goemans (Massachusetts Institute of Technology)
Tuesday, September 19, 2006
The Sum-Product Theorem and Applications
Avi Wigderson (Faculty, School of Mathematics)