| Sep. 12 (Sun.) |
Sep. 13 (Mon.) |
Sep. 14 (Tue.) |
Sep. 15 (Wed.) |
Sep. 16 (Thu.) |
Sep. 17 (Fri.) |
Sep. 18 (Sat.) |
|
| 8:50-9:00 | Opening Remarks | Tour | Informal Tour & Possibly Open Problems | ||||
| 9:00-10:00 | Keynote Talk 1 | Keynote Talk 3 | Keynote Talk 4 | Keynote Talk 5 | |||
| 10:00-10:30 | Group Photo Coffee Break | Coffee Break | |||||
| 10:30-12:00 | Keynote Talk 2 | Session 3 Cryptography |
Session 6 |
Session 9 Game Theory |
|||
| 12:00-14:00 | Lunch | ||||||
| 14:00-15:00 | Registration |
Session 1 Complexity |
Session 4 Property Testing |
Session 7 Complexity |
Session 10 Embeddings and Random Matrices |
||
| 15:00-15:30 | Coffee Break | ||||||
| 15:30-16:30 | Session 2 Complexity |
Session 5 Learning |
Session 8 Complexity |
Session 11 Algs/Data Structures/ Applications |
|||
| 16:30-17:00 | ITCS Showcase | Discussion | Discussion | ||||
| 17:00-17:30 | Closing Ceremony | ||||||
| 18:00-20:00 | Reception | Banquet | |||||
| Sunday September 12, 2010 | |||
| TIME | ACTIVITIES | VENUE | |
| 14:00-18:00 | Registration | Lobby of FIT Building |
|
| Monday September 13, 2010 | |||
| TIME | ACTIVITIES | VENUE | |
| 8:50-9:00 | Opening Remarks | Lecture Hall (2nd Floor), FIT Building | |
| 9:00-10:00 | Keynote Talk 1 |
Title: Some Results in Circuit Complexity[slides] Johan Håstad (Kungliga Tekniska högskolan) |
|
| 10:00-10:30 | Group Photo + Coffee Break | Photo at Main Gate of FIT Building | |
| 10:30-11:30 | Keynote Talk 2 Chair: Ryan O'Donnell |
Title: Open problems in unconditional derandomization[slides] |
Lecture Hall (2nd Floor), FIT Building |
| 12:00-14:00 | Lunch | Wenjin Hotel | |
| 14:00-15:00 | Session 1 Chair: Andrew Wan |
Title: The Lovász Local Lemma and Satisfiability[slides] |
Room 1-315, FIT Building |
| 15:00-15:30 | Coffee Break | Lobby of Room 1-315, FIT Building | |
| 15:30-17:00 | Session 2 Chair: Periklis Papakonstantinou |
Title: Locally Testable Codes Analogues to the Unique Games Conjecture Do Not Exist[slides] Gillat Kol (Weizmann Institute of Science) Title: The Gaussian Surface Area and Noise Sensitivity of Degree-d Polynomial Threshold Functions Daniel Kane (Harvard University) Title: Improved Direct Product Theorems for Randomized Query Complexity[slides] Andrew Drucker (MIT) |
Room 1-315, FIT Building |
| 18:00-20:00 | Reception | Ball Room (6th Floor), Wenjin Hotel | |
| Tuesday September 14, 2010 | |||
| TIME | ACTIVITIES | VENUE | |
| 9:00-10:00 | Keynote Talk 3 Chair: Luca Trevisan |
Title: Invariance Principles in Theoretical Computer Science[slides] Ryan O'Donnell (Carnegie Mellon University) |
Room 1-315, FIT Building |
| 10:00-10:30 | Coffee Break | Lobby of Room 1-315, FIT Building | |
| 10:30-12:00 | Session 3 Chair: John Steinberger |
Title: Overcoming the Hole in the Bucket: Public-Key Cryptography Resilient to Continual Memory Leakage Zvika Brakerski (Weizmann Institute of Science) Title: On the Computational Complexity of Coin Flipping[slides] Hemanta Maji (University of Illinois, Urbana-Champaign) Title: Recent Progress in Leakage-Resilient Cryptography[slides] Daniel Wichs (New York University) |
Room 1-315, FIT Building |
| 12:00-14:00 | Lunch | Wenjin Hotel | |
| 14:00-15:00 | Session 4 Chair: Kevin Matulef |
Title: Testing Function Isomorphism Eric Blais (Carnegie Mellon University) Title: Toward A Canonical Form for Boolean Function Property Testing Algorithms Dana Dachman-Soled (Columbia University) |
Room 1-315, FIT Building |
| 15:00-15:30 | Coffee Break | Lobby of Room 1-315, FIT Building | |
| 15:30-16:30 | Session 5 Chair: Christophe Tartary |
Title: Learning Parities with Structured Noise[slides] Rong Ge (Princeton University) Title: Potential-Based Agnostic Boosting[slides] Varun Kanade (Harvard University) |
Room 1-315, FIT Building |
| 16:30-17:30 | ITCS Showcase | ||
| Wednesday September 15, 2010 | |||
| TIME | ACTIVITIES | VENUE | |
| 9:00-10:00 | Keynote Talk 4 Chair: Johan Håstad |
Title: Constructive Proofs of Concentration Bounds[slides] Russell Impagliazzo (Institute for Advanced Study, Princeton and University of California, San Diego) |
Room 1-315, FIT Building |
| 10:00-10:30 | Coffee Break | Lobby of Room 1-315, FIT Building | |
| 10:30-12:00 | Session 6 Chair: Joshua Brody |
Title: New Balanced Search Trees[slides] Siddhartha Sen (Princeton University) Title: External Memory Data Structures with o(1)-I/O Updates Qin Zhang (University of Aarhus) Title: Vertex Sparsifiers and Oblivious Reductions[slides] Ankur Moitra (MIT) |
Room 1-315, FIT Building |
| 12:00-14:00 | Lunch | Wenjin Hotel | |
| 14:00-15:00 | Session 7 Chair: Iddo Tzameret |
Title: Non-uniform Attacks Against One-way Functions and PRGs[slides] Anindya De (UC Berkeley) Title: An Invariance Principle for Polytopes[slides] Raghu Meka (UT Austin) |
Room 1-315, FIT Building |
| 15:00-15:30 | Coffee Break | Lobby of Room 1-315, FIT Building | |
| 15:30-16:30 | Session 8 Chair: Kevin Matulef |
Title: A New Approach to Affine Extractors and Dispersers[slides] Xin Li (UT Austin) Title: Trevisan's Extractor in the Presence of Quantum Side Information[slides] Thomas Vidick (UC Berkeley) |
Room 1-315, FIT Building |
| 16:30-17:30 | Discussion (open problems) | ||
| Thursday September 16, 2010 | |||
| TIME | ACTIVITIES | VENUE | |
| 9:00-10:00 | Keynote Talk 5
Chair: Maurice Herlihy |
Title: Sparse Recovery Using Sparse Matrices (a tutorial)[slides] Piotr Indyk (MIT) |
Room 1-315, FIT Building |
| 10:00-10:30 | Coffee Break | Lobby of Room 1-315, FIT Building | |
| 10:30-12:00 | Session 9 Chair: Xiaoming Sun |
Title: Towards Optimal Bayesian Algorithmic Mechanism Design Zhiyi Huang (University of Pennsylvania) Title: Single Parameter Combinatorial Auctions with Partially Public Valuations[slides] Lei Wang (Georgia Tech) Title: Rumor Spreading and Conductance[slides] Silvio Lattanzi (Sapienza University of Rome) |
Room 1-315, FIT Building |
| 12:00-14:00 | Lunch | Wenjin Hotel | |
| 14:00-15:00 | Session 10 Chair: Andrew Wan |
Title: Matrix-valued Chernoff Bounds and Applications[slides] Anastasios Zouzias (University of Toronto) Title: Explicit Dimension Reduction and its Applications Zohar Karnin (Technion - Israel Institute of Technology) |
Room 1-315, FIT Building |
| 15:00-15:30 | Coffee Break | Lobby of Room 1-315, FIT Building | |
| 15:30-16:30 | Session 11 Chair: John Steinberger |
Title: Fast Approximation Algorithms for Flow and Cut-based Problems in Undirected Graphs[slides] Aleksander Madry (MIT) Title: Achieving the Scaling Law of SNR-Monitoring in Dynamic Wireless Networks[slides] Hongyi Yao (Tsinghua University) |
Room 1-315, FIT Building |
| 16:30-17:00 | Discussion | ||
| 17:00-17:30 | Closing Ceremony | ||
| 18:00-20:00 | Banquet | Quanjude Roast Duck Restaurant | |