|
Sep 20th (Sun.) |
Sep 21st (Mon.) |
Sep 22nd (Tue.) |
Sep 23rd (Wed.) |
Sep 24th (Thu.) |
Sep 25th (Fri.) |
8:00-8:50 |
Registration |
Registration |
Registration |
Registration |
Tour |
|
8:50-9:00 |
Opening Remarks |
|||||
9:00-10:30 |
||||||
10:30-11:00 |
Group Photo Coffee Break |
Coffee Break |
||||
11:00-12:00 |
||||||
12:00-14:00 |
Lunch |
|||||
14:00-15:30 |
Registration |
|||||
15:30-16:00 |
Coffee Break |
|||||
16:00-17:00 |
Discussion |
|||||
17:00-17:30 |
Closing Ceremony |
|||||
18:00-20:00 |
Reception |
Dinner |
Dinner |
Banquet |
||
|
Monday September 21, 2009 |
|||
|
TIME |
ACTIVITIES |
VENUE |
|
|
8:00-8:50 |
Registration |
Lecture Hall (2nd Floor), FIT Building |
|
|
8:50-9:00 |
Opening Remarks |
||
|
9:00-10:30 |
Chair: Andrew Yao |
Title: Succinct Data Structures Ian Munro (University of Waterloo) Title: Policy Iteration Algorithms Uri Zwick (Tel Aviv University) |
|
|
10:30-11:00 |
Group Photo + Coffee Break |
|
|
|
11:00-12:00 |
Chair: Jayalal Sarma M. N. |
Title: QIP = PSPACE Sarvagya Upadhyay (University of Waterloo) Title: Planar Graph Isomorphism is in Logspace Nutan P. Limaye (IMSc) |
Room 1-315, FIT Building, Tsinghua University |
|
12:00-14:00 |
Lunch |
2nd
Floor, |
|
|
14:00-15:30 |
Chair: Anke van Zuylen |
Title: Breaking the Multicommodity Flow Barrier for Approximating Sparsest Cut Jonah Sherman (UC Berkeley) Title: Integrality Gaps for Strong SDP Relaxations of Unique Games David Steurer (Princeton University) Title: Hardness of Approximation Max. Quadratic Assignment Problem Rajsekar Manokaran (Princeton University) |
Room 1-315, FIT Building, Tsinghua University |
|
15:30-16:00 |
|
Coffee Break |
|
|
16:00-17:00 |
Chair: Frans Schalekamp |
Title: On the Equilibria of Asynchronous Games Aaron Roth (CMU) Title: Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities Decheng Dai (Tsinghua University) |
Room 1-315, FIT Building, Tsinghua University |
|
18:00-20:00 |
Reception |
Wenjin Hotel |
|
|
Tuesday September 22, 2009 |
|||
|
TIME |
ACTIVITIES |
VENUE |
|
|
8:00-8:50 |
Registration |
Lecture Hall (2nd Floor), FIT Building |
|
|
9:00-10:30 |
Uri Zwick |
Title: Concurrent Reachability Games Peter Bro Miltersen (Aarhus University) Title: Proof Complexity in the Last Decade: A Brief Tour of the Highlights, Obstacles, and Future Directions Toniann Pitassi (University of Toronto) |
|
|
10:30-11:00 |
Coffee Break |
||
|
11:00-12:00 |
Chair: Elad Verbin |
Title: The Polynomial-time Learnability of Mixtures of Two Gaussians Gregory Valiant (UC Berkeley) Title: Agnostic Learning of Monomials by Halfspaces is Hard Yi Wu (CMU) |
Room 1-315, FIT Building, Tsinghua University |
|
12:00-14:00 |
Lunch |
2nd
Floor, |
|
|
14:00-15:30 |
Chair: Henry Lin |
Title: Randomization in Algorithmic Mechanism Design Shaddin Dughmi (Stanford University) Title: A New Approach to Auctions and Resilient Mechanism Design Jing Chen (MIT) Title: Resource Allocation Problems for Selfish Agents Thanh Nguyen (Cornell University) |
Room 1-315, FIT Building, Tsinghua University |
|
15:30-16:00 |
Coffee Break |
|
|
|
16:00-17:00 |
Chair: Elad Verbin |
Discussion |
Room 1-315, FIT Building, Tsinghua University |
|
18:00-20:00 |
Dinner |
2nd
Floor, |
|
|
Wednesday September 23, 2009 |
|||
|
TIME |
ACTIVITIES |
VENUE |
|
|
8:00-8:50 |
Registration |
Room 1-315, FIT Building, Tsinghua University |
|
|
9:00-10:30 |
Maurice Jansen |
Title: k-Clique on Random Graphs Ben Rossman (MIT) Title: Blackbox Polynomial Identity Testing for Depth 3 Circuits Shubhangi Saraf (MIT) Title: Extensions to the Method of Multiplicities, with Applications to Kakeya sets, Mergers and Extractors Swastik Kopparty (MIT) |
|
|
10:30-11:00 |
Coffee Break |
||
|
11:00-12:00 |
Henry Lin |
Title: Robustness and Optimization of Scrip Systems Ian Kash (Cornell University) Title: Bounded Budget Betweenness Centrality Game for Strategic Network Formations Xiaohui Bei (Tsinghua University) |
Room 1-315, FIT Building, Tsinghua University |
|
12:00-14:00 |
Lunch |
2nd Floor, Wenjin Hotel |
|
|
14:00-15:30 |
Xiaoming Sun |
Title: Space Lower Bounds on Succinct Representations of Graphs Arash Farzan (University of Waterloo) Title: Lower Bounds on the Randomized Communication Complexity of Read-once Functions, Via Information Theory Nikos Leonardos (Rutgers University) Title: Lower Bound for Distance Oracles Wei Yu (Tsinghua University) |
Room 1-315, FIT Building, Tsinghua University |
|
15:30-16:00 |
Coffee Break |
|
|
|
16:00-17:00 |
Chair: Christophe Tartary |
Title: On the Security of Goldreich's One-way Function Youming Qiao (Tsinghua University) Title: Non-Malleability Amplification Huijia Rachel Lin (Cornell University) |
Room 1-315, FIT Building, Tsinghua University |
|
18:00-20:00 |
Dinner |
2nd Floor, Wenjin Hotel |
|
|
Thursday September 24, 2009 |
|||
|
8:00-8:50 |
Registration |
Room 1-315, FIT Building, Tsinghua University |
|
|
9:00-10:30 |
John Steinberger |
Title: Product Rules in Semidefinite Programming Rajat Mittal (Rutgers University) Title: The Serializability of Network Codes Anna Blasiak (Cornell University) Title: On the Geometry of Differential Privacy Moritz Hardt (Princeton University) |
|
|
10:30-11:00 |
Coffee Break |
||
|
11:00-12:00 |
Victor Chen |
Title: Computational Complexity of Differential Equations Akitoshi Kawamura (University of Toronto) Title: Lower Bounds via Sampling Algorithms Chinmoy Dutta (TIFR) |
Room 1-315, FIT Building, Tsinghua University |
|
12:00-14:00 |
Lunch |
2nd Floor, Wenjin Hotel |
|
|
14:00-15:30 |
Kevin Matulef |
Title: Maximizing Non-monotone Submodular Functions over Matroid and Knapsack Constraints Viswanath Nagarajan (CMU) Title: Linear-Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems Warren Schudy (Brown University) Title: An Optimal Streaming Algorithm for Sketching Small Moments Jelani Nelson (MIT)
|
Room 1-315, FIT Building, Tsinghua University |
|
15:30-16:00 |
Coffee Break |
|
|
|
16:00-17:00 |
Chair: Elad Verbin |
Discussion |
Room 1-315, FIT Building, Tsinghua University |
|
17:00-17:30 |
Closing Ceremony |
|
|
|
18:00-20:00 |
Banquet |
Wenjin Hotel |
|