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) |