2007-2008 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 Depth-3 Arithmetic Circuits
Amir Shpilka (Technion)
Tuesday, May 13, 2008
A Dirac-Type Theorem for 3-Uniform Hypergraphs
Endre Szemeredi (Rutgers University and Member, School of Mathematics)
Monday, May 12, 2008
Artin Map, Cyclotomic Function Fields, and Folded List-Decodable 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 Key-Dependent 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 Worst-Case 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 Sign-Rank of AC^0 (continued)
Alexander Razborov (IAS)
Monday, March 10, 2008
A Frieman Isomorphism-type Lemma for Polynomials
Philip Matchett Wood (Rutgers University)
Tuesday, March 4, 2008
The Sign-Rank of AC^0
Alexander Razborov (IAS)
Monday, March 3, 2008
Disjointness is Hard in the Multi-Party Number-On-The-Forehead Model
Troy Lee (Rutgers University)
Tuesday, February 26, 2008
Sound 3-Query PCPPs Are Long
Arie Matsliah (Technion)
Monday, February 25, 2008
Security Under Key-Dependent 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 Sherali-Adams 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 Win-Lose 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 Ramsey-Type 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 Sum-Product 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
Jin-Yi 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 Primal-Dual 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 Sum-Free 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
Erdos-Renyi 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
Unbounded-Error 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)