| January 4 (Monday) |
January 5 (Tuesday) |
January 6 (Wednesday) |
January 7 (Thursday) |
|
| 08:20-08:30 | Opening Remarks | |||
| 08:30-08:45 | Session 5 Chair: Shafi Goldwasser |
|||
| 08:45-10:00 | Session 1 Chair:Sanjeev Arora |
|||
| 10:00-10:10 | Registration | Group Photo Coffee Break |
||
| 10:10-10:40 | Coffee Break | |||
| 10:40-11:55 | Session 2 Chair: Bernard Chazelle |
Session 6 Chair: Avrim Blum |
Session 10 Chair: Aravind Srinivasan |
|
| 12:00-13:45 | Lunch | |||
| 13:45-15:00 | Session 3 Chair: Cynthia Dwork |
Session 7 Chair: Rafael Pass |
||
| 15:00-15:25 | Session 12 Chair: Francis Lau |
|||
| 15:25-15:50 | Coffee Break | |||
| 15:50-15:55 | Coffee Break | |||
| 15:55-16:00 | Session 4 Chair: Sanjeev Khanna |
Session 8 Chair: Francis Y.L. Chin |
||
| 16:00-17:10 | Discussion Chair: Andrew Chi-Chih Yao Closing Ceremony |
|||
| 17:10-17:35 | Poster Session Chair: Henry Lin |
|||
| 17:35-18:00 | ||||
| 18:00-20:00 | Dinner | Reception | Dinner | Banquet |
| Monday January 4, 2010 | |||
| TIME | ACTIVITIES | VENUE | |
| 10:00-20:00 | Registration | Lobby of |
|
| 18:00-20:00 | Dinner | 2nd Floor, Wenjin Hotel |
|
| Tuesday January 5, 2010 | |||
| TIME | ACTIVITIES | VENUE | |
| 08:20-08:45 | Opening Remarks |
Lecture Hall (2nd Floor), FIT Building |
|
| 08:45-09:10 |
Title: Cryptography by Cellular Automata or How
Fast Can Complexity Emerge in Nature?[slide] Benny Applebaum, Yuval Ishai and Eyal Kushilevitz |
||
| 09:10-09:35 |
Title: Breaking and Making Quantum Money: Toward
a New Quantum Cryptographic Protocol[slide] Andrew Lutomirski, Scott Aaronson, Edward Farhi, David Gosset, Jonathan Kelner, Avinatan Hassidim and Peter Shor |
||
| 09:35-10:00 |
Title: Analytical Tools for Natural Algorithms[slide] Bernard Chazelle |
||
| 10:00-10:40 | Group Photo & Coffee Break | ||
| 10:40-11:05 |
Session 2 Chair: Bernard Chazelle |
Title: A New Approach to Strongly Polynomial
Linear Programming[slide] Mihály Bárász and Santosh Vempala |
|
| 11:05-11:30 | Title:
Computational Complexity and Information Asymmetry in Financial
Products (Extended Abstract)[slide] Sanjeev Arora, Boaz Barak, Markus Brunnermeier and Rong Ge |
||
| 11:30-11:55 |
Title: Pan-Private Streaming Algorithms[slide] Cynthia Dwork, Moni Naor, Toniann Pitassi, Guy N. Rothblum and Sergey Yekhanin |
||
| 12:00-13:45 | Lunch | 2nd Floor, Wenjin Hotel |
|
| 13:45-14:10 | Title: Robustly
Leveraging Collusion in Combinatorial Auctions Jing Chen, Silvio Micali and Paul Valiant |
Lecture Hall (2nd Floor), FIT Building |
|
| 14:10-14:35 |
Title: Robust Perfect Revenue From Perfectly
Informed Players Jing Chen, Avinatan Hassidim and Silvio Micali |
||
| 14:35-15:00 |
Title: Playing Games without Observing Payoffs[slide] Michal Feldman, Adam Kalai and Moshe Tennenholtz |
||
| 15:00-15:25 |
Title: Adversarial Leakage in Games[slide] Noga Alon, Yuval Emek, Michal Feldman and Moshe Tennenholtz |
||
| 15:25-15:55 | Coffee Break | ||
| 15:55-16:20 |
Session 4 Chair: Sanjeev Khanna |
Title: Game Theory with Costly Computation:
Formulation and Application to Protocol Security[slide] Joseph Y. Halpern and Rafael Pass |
|
| 16:20-16:45 |
Title: Bounding Rationality by Discounting Time[slide] Lance Fortnow and Rahul Santhanam |
||
| 16:45-17:10 |
Title: Market Equilibrium under Separable,
Piecewise-Linear, Concave Utilities[slide] Vijay V. Vazirani and Mihalis Yannakakis |
||
| 17:10-17:35 |
Title: Beyond Equilibria: Mechanisms for
Repeated Combinatorial Auctions[slide] Brendan Lucier |
||
| 18:00-20:00 | Reception | Grand Ball Room Wenjin Hotel |
|
| Wednesday January 6, 2010 | |||
| TIME | ACTIVITIES | VENUE | |
| 08:30-08:55 |
Session 5 Chair: Shafi Goldwasser |
Title: A New
Look at Selfish Routing [slide] Christos Papadimitriou and Gregory Valiant |
Lecture Hall (2nd Floor), FIT Building |
| 08:55-09:20 |
Title: Local Algorithms for Finding Interesting
Individuals in Large Networks[slide] Mickey Brautbar and Michael Kearns |
||
| 09:20-09:45 |
Title: Circumventing the Price of Anarchy:
Leading Dynamics to Good Behavior[slide] Maria-Florina Balcan and Avrim Blum and Yishay Mansour |
||
| 09:45-10:10 |
Title: Reaching Consensus on Social Networks[slide] Elchanan Mossel and Grant Schoenebeck |
||
| 10:10-10:40 | Coffee Break | ||
| 10:40-11:05 |
Session 6 Chair: Avrim Blum |
Title: Robustness of the Learning with Errors
Assumption[slide] Shafi Goldwasser, Yael Kalai, Chris Peikert and Vinod Vaikuntanathan |
|
| 11:05-11:30 |
Title: Distribution-Specific Agnostic Boosting[slide] Vitaly Feldman |
||
| 11:30-11:55 |
Title: Space-Efficient Estimation of Robust
Statistics and Distribution Testing[slide] Steve Chien, Katrina Ligett and Andrew McGregor |
||
| 12:00-13:45 | Lunch | 2nd Floor, Wenjin Hotel |
|
| 13:45-14:10 |
Session 7 Chair: Rafael Pass |
Title: Cryptographic Complexity Classes and
Computational Intractability Assumptions[slide] Hemanta K. Maji, Manoj Prabhakaran and Mike Rosulek |
Lecture Hall (2nd Floor), FIT Building |
| 14:10-14:35 |
Title: Hard Instances for Satisfiability and
Quasi-one-way Functions[slide] Andrej Bogdanov, Kunal Talwar and Andrew Wan |
||
| 14:35-15:00 |
Title: On the Construction of One-Way Functions
from Average Case Hardness[slide] Noam Livne |
||
| 15:00-15:25 |
Title: Proof-Carrying Data and Hearsay
Arguments from Signature Cards[slide] Alessandro Chiesa and Eran Tromer |
||
| 15:25-15:55 | Coffee Break | ||
| 15:55-16:20 |
Session 8 Chair: Francis Y.L. Chin |
Title: Are Stable Instances Easy?[slide] Yonatan Bilu and Nathan Linial |
|
| 16:20-16:45 |
Title: A New Approximation Technique for
Resource-Allocation Problems[slide] Barna Saha and Aravind Srinivasan |
||
| 16:45-17:10 |
Title: Global Alignment of Molecular Sequences
via Ancestral State Reconstruction[slide] Alexandr Andoni, Constantinos Daskalakis, Avinatan Hassidim and Sebastien Roch |
||
| 17:10-17:25 | Poster Session Chair: Henry Lin |
Title: Sufficient Conditions for Agnostic Active Learnable[slide] Liwei Wang |
|
| 17:25-17:40 | Title: An Analysis of the Chaudhuri and Monteleoni Algorithm[slide] |
||
| 17:40-17:55 | Title: A Structured Wikipedia for Mathematics[slide] Henry Lin |
||
| 18:00-20:00 | Dinner | 2nd Floor, Wenjin Hotel |
|
| Thursday January 7, 2010 | |||
| TIME | ACTIVITIES | VENUE | |
| 08:30-09:00 | Session 9 Chair: Michael Saks |
Title:
Effectively Polynomial Simulations[slide] Toniann Pitassi and Rahul Santhanam |
Lecture Hall (2nd Floor), FIT Building |
| 09:00-09:30 |
Title: Circuit Lower Bounds, Help Functions,
and the Remote Point Problem[slide] V. Arvind and Srikanth Srinivasan |
||
| 09:30-10:00 |
Title: Derandomizing Algorithms on Product
Distributions and Other Applications of Order-Based Extraction[slide] Ariel Gabizon and Avinatan Hassidim |
||
| 10:00-10:40 | Coffee Break | ||
| 10:40-11:05 | Session 10 Chair: Aravind Srinivasan |
Title: Symmetric LDPC Codes and Local Testing Tali Kaufman and Avi Wigderson |
|
| 11:05-11:30 |
Title: Weight Distribution and List-Decoding
Size of Reed-Muller Codes Tali Kaufman, Shachar Lovett and Ely Porat |
||
| 11:30-11:55 |
Title: Non-Malleable Codes Stefan Dziembowski, Krzysztof Pietrzak and Daniel Wichs |
||
| 12:00-13:45 | Lunch | 2nd Floor, Wenjin Hotel |
|
| 13:45-14:10 | Session 11 Chair: Michael Ben-Or |
Title: Interactive Proofs For Quantum
Computations[slide] Dorit Aharonov, Michael Ben-Or and Elad Eban |
Lecture Hall (2nd Floor), FIT Building |
| 14:10-14:35 |
Title: On the Power of a Unique Quantum Witness[slide] Rahul Jain, Iordanis Kerenidis,Greg Kuperberg, Miklos Santha, Or Sattath and Shengyu Zhang |
||
| 14:35-15:00 |
Title: Bounds on the Quantum Satisfiability
Threshold[slide] Sergey Bravyi, Cristopher Moore and Alexander Russell |
||
| 15:00-15:25 | Session 12 Chair: Francis Lau |
Title: Memory Consistency Conditions for
Self-Assembly Programming[slide] Aaron Sterling |
|
| 15:25-15:50 | Title: Cache Replacement Policies for Multicore
Processors[slide] Avinatan Hassidim |
||
| 15:50-16:00 | Coffee Break | ||
| 16:00-18:00 | Discussion Chair: Andrew Chi-Chih Yao Closing Ceremony |
||
| 18:00-20:00 | Banquet | Grand Ball Room Wenjin Hotel |
|