20072008 seminars
Tuesday, June 10, 2008  Computability and Complexity of Julia sets Mark Braverman (University of Toronto) 
Tuesday, May 27, 2008  Approximating Functions in Logarithmic Space and Time: A "Plug & Play" Approach Nir Halman (MIT and Member, School of Mathematics) 
Monday, May 26, 2008  COMPUTER SCIENCE/DISCRETE MATH I
Institute Closed in Observance of Memorial Day 
Friday, May 23, 2008  The finite field Kakeya conjecture. Zeev Dvir (Weizmann Institute) 
Tuesday, May 20, 2008  COMPUTER SCIENCE/DISCRETE MATH II
No Seminar Due to STOC Conference 
Friday, May 16, 2008  Reconstruction of Depth3 Arithmetic Circuits Amir Shpilka (Technion) 
Tuesday, May 13, 2008  A DiracType Theorem for 3Uniform Hypergraphs Endre Szemeredi (Rutgers University and Member, School of Mathematics) 
Monday, May 12, 2008  Artin Map, Cyclotomic Function Fields, and Folded ListDecodable Codes Venkatesan Guruswami (University of Washington and Member, School of Mathematics) 
Tuesday, May 6, 2008  COMPUTER SCIENCE/DISCRETE MATH II
NO SEMINAR 
Monday, May 5, 2008  COMPUTER SCIENCE/DISCRETE MATH I
NO SEMINAR 
Tuesday, April 29, 2008  Optimal Monotone Encodings Rani Hod (Tel Aviv University) 
Monday, April 28, 2008  Security Under KeyDependent Inputs Shai Halevi (IBM T. J. Watson Research Center) 
Tuesday, April 22, 2008  COMPUTER SCIENCE/DISCRETE MATH II
NO SEMINAR DUE TO PASSOVER 
Monday, April 21, 2008  COMPUTER SCIENCE/DISCRETE MATH I
NO SEMINAR DUE TO PASSOVER 
Tuesday, April 15, 2008  Nearly Diagonally Dominant Matrices and Their Applications Noga Alon (Tel Aviv University and Visiting Professor, School of Mathematics) 
Monday, April 14, 2008  Embeddings of Discrete Groups and the Speed of Random Walks Assaf Naor (Courant Institute) 
Tuesday, April 8, 2008  Spherical Cubes, or Coordinated Random Choices in High Dimensions Anup Rao (University of Texas at Austin and Member, School of Mathematics) 
Monday, April 7, 2008  Merkle Puzzles are Optimal Mohammad Mohmoody Ghidary (Princeton University) 
Tuesday, April 1, 2008  The Distribution of Polynomials Over Finite Fields Tali Kaufman (Member, School of Mathematics) 
Monday, March 31, 2008  On Proving Hardness of Improper Learning from WorstCase Assumptions Benny Applebaum (Princeton University) 
Tuesday, March 25, 2008  Expander Cryptography  Cryptography With Constant Computational Overhead Amit Sahai (UCLA) 
Monday, March 24, 2008  Testing Symmetric Properties of Distributions Paul Valiant (Massachusetts Institute of Technology) 
Tuesday, March 18, 2008  COMPUTER SCIENCE/DISCRETE MATH II

Monday, March 17, 2008  COMPUTER SCIENCE/DISCRETE MATH I

Tuesday, March 11, 2008  The SignRank of AC^0 (continued) Alexander Razborov (IAS) 
Monday, March 10, 2008  A Frieman Isomorphismtype Lemma for Polynomials Philip Matchett Wood (Rutgers University) 
Tuesday, March 4, 2008  The SignRank of AC^0 Alexander Razborov (IAS) 
Monday, March 3, 2008  Disjointness is Hard in the MultiParty NumberOnTheForehead Model Troy Lee (Rutgers University) 
Tuesday, February 26, 2008  Sound 3Query PCPPs Are Long Arie Matsliah (Technion) 
Monday, February 25, 2008  Security Under KeyDependent Inputs Shai Halevi (IBM T.J. Watson Research Center) 
Tuesday, February 19, 2008  New Results and Open Problems in Computing Nash Equilibria Christos Papadimitriou (University of California at Berkeley) 
Monday, February 18, 2008  Integrality Gaps for SheraliAdams Relaxations Yury Makarychev (Microsoft Research) 
Tuesday, February 12, 2008  Efficient Algorithms for Some Algebraic Problems Neeraj Kayal (DIMACS) 
Monday, February 11, 2008  Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized Valentine Kabanets (Simon Fraser University) 
Tuesday, February 5, 2008  Arithmetic Complexity  The Power of Partial Derivatives Avi Wigderson (IAS) 
Monday, February 4, 2008  The Rules of the Game Michael Krivelevich (Tel Aviv University) 
Tuesday, January 29, 2008  Arithmetic Complexity  The Power of Partial Derivatives Avi Wigderson, IAS 
Monday, January 28, 2008  Hardness Amplification Proofs Require Majority Emanuele Viola (Columbia University) 
Tuesday, January 22, 2008  A Study of Multiplication Codes Adi Akavia (Massachusetts Institute of Technology and Member, School of Mathematics) 
Monday, January 21, 2008  Noisy Binary Search and Applications Avinatan Hassidim (Hebrew University) 
Wednesday, December 5, 2007  Some Properties of Sum and Product Sets in Finite Fields Alexey Glibichuk (Moscow State University, Russia and Member, School of Mathematics) 
Tuesday, December 4, 2007  Optimal Phylogenetic Reconstruction Konstantinos Daskalakis (University of California, Berkeley) 
Monday, December 3, 2007  Expander Flows, Graph Spectra and Graph Separators Umesh Vazirani (University of California, Berkeley) 
Tuesday, November 27, 2007  Inverse Theorems for Large Subsets of sums of Dissociated Sets Ilya Shkredov (Moscow State University, Russia and Member, School of Mathematics) 
Tuesday, November 27, 2007  The Approximation Complexity of WinLose Games Xi Chen (Tsinghua University, China and Member, School of Mathematics) 
Monday, November 26, 2007  On Hardness of Learning Intersection of Two Halfspaces Subhash Khot (Courant Institute, New York University) 
Tuesday, November 20, 2007  Density Theorems for Bipartite Graphs and Related RamseyType Results Benny Sudakov (University of California, Los Angeles and Member, School of Mathematics) 
Monday, November 19, 2007  On a Network Creation Game Yishay Mansour (Tel Aviv University & Google) 
Thursday, November 15, 2007  SumProduct Estimates and Expanders
Alexander Gamburd (University of California at Santa Cruz) 
Wednesday, November 14, 2007  Decompositions into Quadratic Phase Functions Julia Wolf (University of Cambridge, UK and Member, School of Mathematics) 
Tuesday, November 13, 2007  Product Growth and Mixing in Finite Groups: Variations on a Theme of Gowers Laszlo Babai (University of Chicago) 
Tuesday, November 13, 2007  Applications of the Removal Lemma Jozsef Solymosi (University of British Columbia and Member, School of Mathematics) 
Monday, November 12, 2007  Developments in Holographic Algorithms JinYi Cai (University of Wisconsin, Madison) 
Tuesday, November 6, 2007  The Rank of Symmetric Matrices Kevin Costello (Rutgers, The State University of New Jersey) 
Tuesday, November 6, 2007  Locally Decodable Codes from Nice Subsets of Finite Fields and Prime Factors of Mersenne Numbers Sergey Yekhanin (Massachusetts Institute of Technology and Member, School of Mathematics) 
Monday, November 5, 2007  Markets and the PrimalDual Paradigm Vijay Vazirani (Georgia Institute of Technology) 
Tuesday, October 30, 2007  On the Property Testing of Hereditary Graph and Hypergraph Properties Terrence Tao (University of California, Los Angeles) 
Tuesday, October 30, 2007  Balancing Gaussian Vectors Kevin Costello (Rutgers, The State University of New Jersey) 
Monday, October 29, 2007  Dense Subsets of Pseudorandom Objects Luca Trevisan (University of California, Berkeley and Member, School of Mathematics) 
Tuesday, October 23, 2007  Polynomial Progressions in Primes Tamar Ziegler (University of Michigan) 
Tuesday, October 23, 2007  COMPUTER SCIENCE DISCRETE MATH II

Monday, October 22, 2007  COMPUTER SCIENCE DISCRETE MATH I

Tuesday, October 16, 2007  Problems in Additive Number Theory Melvyn Nathanson (City University of New York and Member, School of Mathematics) 
Tuesday, October 16, 2007  Sparse Random Linear Codes are Locally Decodable and Testable Tali Kaufman (Member and School of Mathematics) 
Monday, October 15, 2007  Extractors and Rank Extractors for Polynomial Sources Zeev Dvir (Weizmann Institute of Science) 
Tuesday, October 9, 2007  On Square SumFree Sets Endre Szemeredi (Rutgers, The State University of New Jersey and Member, School of Mathematics) 
Tuesday, October 9, 2007  New Proofs of (New) Direct Product Theorems
Russell Impagliazzo (University of California, San Diego and Member, School of Mathematics) 
Monday, October 8, 2007  ErdosRenyi Phase Transition Joel Spencer (New York University) 
Tuesday, October 2, 2007  Difference Sets and the Primes Tom Sanders (University of Cambridge, UK and Member, School of Mathematics) 
Tuesday, October 2, 2007  UnboundedError Communication Complexity of Symmetric Functions Alexander Sherstov (University of Texas at Austin) 
Monday, October 1, 2007  The Pattern Matrix Method for Lower Bounds on Quantum Communication Alexander Sherstov (University of Texas at Austin) 
Tuesday, September 25, 2007  Applications of Quadratic Fourier Analysis Tim Gowers (Cambridge University) 
Tuesday, September 25, 2007  Hardness of Solving Sparse Overdetermined Linear Systems Venkatesan Guruswami (University of Washington and Member, School of Mathematics) 
Monday, September 24, 2007  Parallel Repetition in Multiplayer Interactive Proofs
Anup Rao (University of Texas at Austin and Member, School of Mathematics) 
Monday, September 24, 2007  Towards Universal Semantic Communiction Madhu Sudan (Massachusetts Institute of Technology) 
Monday, September 17, 2007  Algebrization: A New Barrier in Complexity Theory Scott Aaronson (Massachusetts Instittute of Technology) 