Theory of Computation Colloquium - 2014
Nikhil Devanur, MSR Redmond
Draft Auctions
Speaker(s): Nikhil Devanur
Date: Friday, March 14, 2014
Time: 11:00 AM to 12:00 PM
Location: G449 (Patil/Kiva)
Contact: Constantinos Daskalakis, costis@csail.mit.edu
Rafael Pass, Cornell University
Indistinguishability Obfuscation from Semantically-Secure Multilinear Encodings
Speaker(s): Rafael Pass
Date: Tuesday, March 18, 2014
Time: 4:15 PM to 5:15 PM
Location: 32-G449
Contact: Holly A Jones, hjones01@csail.mit.edu
Maria Florina Balcan, Georgia Tech
FOUNDATIONS FOR LEARNING IN THE AGE OF BIG DATA
Speaker(s): Maria Florina Balcan
Date: Tuesday, April 08, 2014
Time: 4:15 PM to 5:15 PM
Location: 32-G449
Contact: Holly A Jones, hjones01@csail.mit.edu
Anup Rao, University of Washington
Circuits with Medium Fan-In
Speaker(s): Anup Rao
Date: Tuesday, April 15, 2014
Time: 4:15 PM to 5:15 PM
Location: 32-G449
Contact: Holly A Jones, hjones01@csail.mit.edu
Benjamin Recht, UC Berkeley
A CONVEX VIEW OF INVERSE PROBLEMS
Speaker(s): Benjamin Recht
Date: Tuesday, April 29, 2014
Time: 4:15 PM to 5:15 PM
Location: 32-G449
Contact: Holly A Jones, hjones01@csail.mit.edu
David Zuckerman, Department of Computer Science, The University of Texas at Austin
Pseudorandomness from Shrinkage
Speaker(s): David Zuckerman
Date: Tuesday, May 06, 2014
Time: 4:15 PM to 5:15 PM
Location: 32-G449
Contact: Holly A Jones, hjones01@csail.mit.edu
Toniann Pitassi, University of Toronto
CIRCUIT COMPLEXITY, PROOF COMPLEXITY, AND POLYNOMIAL IDENTITY TESTING
Speaker(s): Toniann Pitassi
Date: Monday, May 12, 2014
Time: 4:00 PM to 5:00 PM
Location: 32-G449
Contact: Holly A Jones, hjones01@csail.mit.edu
Dana Moshkovitz,
PARALLEL REPETITION FROM FORTIFICATION
Speaker(s): Dana Moshkovitz
Date: Tuesday, May 13, 2014
Time: 4:15 PM to 5:15 PM
Location: 32-G449
Contact: Holly A Jones, hjones01@csail.mit.edu
Umesh Vazirani, UC Berkeley
Algorithms, Games and Evolution
Speaker(s): Umesh Vazirani
Date: Wednesday, May 14, 2014
Time: 1:30 PM to 3:00 PM
Location: 32-G575
Contact: Holly A Jones, hjones01@csail.mit.edu
Shubhangi Saraf, Assistant Professor, Dept.of Mathematics and Dept. of Computer Science, Rutgers University,
Lower bounds for bounded depth arithmetic circuits
Speaker(s): Shubhangi Saraf, Assistant Professor, Dept.of Mathematics and Dept. of Computer Science, Rutgers University
Date: Tuesday, September 09, 2014
Time: 4:15 PM to 5:15 PM
Location: G449 (Patil/Kiva)
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu
Shachar Lovett, Assistant Professor, CSE department, UC San Diego,
New advances on the log rank conjecture
Speaker(s): Shachar Lovett, Assistant Professor, CSE department, UC San Diego
Date: Tuesday, September 16, 2014
Time: 4:15 PM to 5:15 PM
Location: G449 (Patil/Kiva)
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu
Ronald Fagin, IBM Research
Applying theory to practice (and practice to theory)
Speaker(s): Ronald Fagin
Date: Tuesday, September 23, 2014
Time: 4:15 PM to 5:15 PM
Location: G449 (Patil/Kiva)
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu
Eli Gafni, Professor, UCLA, Dept. of Computer Science,
Better Late (40 years late!) Than Never: Monday Morning Quarterbacking the Coordinated-Attack Problem
Speaker(s): Eli Gafni, Professor, UCLA, Dept. of Computer Science
Date: Tuesday, September 30, 2014
Time: 4:15 PM to 5:15 PM
Location: G449
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu
Zeev Dvir,
Private Information Retrieval with 2-Servers and sub-polynomial communication
Speaker(s): Zeev Dvir
Date: Tuesday, October 07, 2014
Time: 4:15 PM to 5:15 PM
Location: G882 (Hewlett Rm)
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu
Alexandr Andoni,
Alexandr Andoni: Sketching Complexity of Graph Cuts
Speaker(s): Alexandr Andoni
Date: Tuesday, October 14, 2014
Time: 4:15 PM to 5:15 PM
Location: G449 (Patil/Kiva)
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu
Paul Beame, Professor, Dept. of Computer Science & Engineering, University of Washington
Paul Beame: Computing Elementary Statistics: Time-Space Tradeoffs and Sliding Windows
Speaker(s): Paul Beame
Date: Tuesday, October 28, 2014
Time: 4:15 PM to 5:15 PM
Location: G449 - Patil/Kiva
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu
Seth Pettie,
3SUM is Subquadratic
Speaker(s): Seth Pettie
Date: Tuesday, November 04, 2014
Time: 4:15 PM to 5:15 PM
Location: G449 (Patil/Kiva)
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu
Nicole Immorlica,
Tilting at Windmills: The Economic Efficiency of Large Games
Speaker(s): Nicole Immorlica
Date: Tuesday, November 18, 2014
Time: 4:15 PM to 5:15 PM
Location: G449 (Patil/Kiva)
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu
Ran Raz, Professor, Mathematics and Computer Science, Weizmann Institute,
Exponential Separation of Information and Communication
Speaker(s): Ran Raz, Professor, Mathematics and Computer Science, Weizmann Institute
Date: Monday, November 24, 2014
Time: 4:15 PM to 5:15 PM
Location: Patil/Kiva G449
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu
Madhu Sudan, Principal Researcher, Microsoft; Adjunct Professor, EECS, MIT,
Two Decades of Property Testing
Speaker(s): Madhu Sudan, Principal Researcher, Microsoft; Adjunct Professor, EECS, MIT
Date: Tuesday, December 09, 2014
Time: 4:15 PM to 5:15 PM
Location: G449 (Patil/Kiva)
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu