| Thursday January 6, 2011 |
| TIME |
ACTIVITIES |
VENUE |
| 13:00-19:30 |
Registration |
Lobby of Wenjin Hotel |
| |
| Friday January 7, 2011 |
| TIME |
ACTIVITIES |
VENUE |
| 08:15-08:30 |
Opening Remarks |
Lecture Hall
(2nd Floor),
FIT Building,
Tsinghua University |
| 08:30-09:30 |
Invited Talk 1
Chair: Andrew Yao |
Title: Conservative Rationalizability and the Second Knowledge Mechanism
Silvio Micali |
| 09:30-09:55 |
Session 1
Chair: Bernard Chazelle |
Title: Abstract Cryptography
Ueli Maurer and Renato Renner |
| 09:55-10:20 |
Title: Efficient Semantic Communication via Compatible Beliefs
Brendan Juba and Madhu Sudan |
| 10:20-10:40 |
Group Photo & Coffee Break |
| 10:40-11:05 |
Session 2
Chair:Bernard Chazelle |
Title: Secret Sharing Krohn-Rhodes: Private and Perennial Distributed Computation
Shlomi Dolev, Juan Garay, Niv Gilboa and Vladimir Kolesnikov |
| 11:05-11:30 |
Title: Semantic Security under Related-Key Attacks and Applications
Benny Applebaum, Danny Harnik and Yuval Ishai |
| 11:30-11:55 |
Title: Renegotiation-Safe Protocols
Rafael Pass and Abhi Shelat |
| 12:00-13:45 |
Lunch |
2nd Floor,
Wenjin Hotel |
| 13:45-14:10 |
Session 3
Chair: Silvio Micali |
Title: Compression without a Common Prior: An Information-Theoretic Justification for Ambiguity in Language
Brendan Juba, Adam Tauman Kalai, Sanjeev Khanna and Madhu Sudan |
Lecture Hall
(2nd Floor),
FIT Building,
Tsinghua University |
| 14:10-14:35 |
Title: Extracting Roots of Arithmetic Circuits by Adapting Numerical Methods
Maurice Jansen |
| 14:35-15:00 |
Title: Finding Almost-Perfect Graph Bisections
Venkatesan Guruswami, Yury Makarychev, Prasad Raghavendra, David Steurer and Yuan Zhou
|
|
15:00-15:25 |
Title: Revenue Maximization via Nash Implementation
Thanh Nguyen |
| 15:25-15:45 |
Coffee Break |
|
15:45-16:10 |
Session 4
Chair: Benny Applebaum |
Title: Beyond the Nash Equilibrium Barrier
Robert Kleinberg, Katrina Ligett, Georgios Piliouras, and Eva Tardos |
| 16:10-16:35 |
Title: A Complexity View of Markets with Social Influence
Xi Chen and Shang-Hua Teng |
| 16:35-17:00 |
Title: Best-Response Mechanisms
Noam Nisan, Michael Schapira, Greg Valiant and Aviv Zohar |
| 17:00-17:25 |
Title: Posting Prices with Unknown Distributions
Moshe Babaioff, Liad Blumrosen, Shaddin Dughmi and Yaron Singer |
| 18:00-20:00 |
Reception |
Grand Ball Room
Wenjin Hotel |
|
| Saturday January 8, 2011 |
| TIME |
ACTIVITIES |
VENUE |
| 08:30-09:30 |
Invited Talk 2
Chair: Bernard Chazelle |
Title: Influence and Noise
Gil Kalai
|
Lecture Hall
(2nd Floor),
FIT Building,
Tsinghua University |
| 09:30-09:55 |
Session 5
Chair: Uri Zwick |
Title: Testing Properties of Collections of Distributions
Reut Levi, Dana Ron and Ronitt Rubinfeld |
| 09:55-10:20 |
Title: Is Submodularity Testable?
C. Seshadhri and Jan Vondrak |
| 10:20-10:40 |
Coffee Break |
| 10:40-11:05 |
Session 6
Chair: Sanjeev Khanna |
Title: Property Testing via Set-Theoretic Operations
Victor Chen, Madhu Sudan and Ning Xie |
| 11:05-11:30 |
Title: Fast Local Computation Algorithms
Ronitt Rubinfeld, Gil Tamir, Shai Vardi and Ning Xie |
| 11:30-11:55 |
Title: Testing Monotonicity of Distributions over General Partial Orders
Arnab Bhattacharya, Eldar Fischer, Ronitt Rubinfeld and Paul Valiant |
| 12:00-13:45 |
Lunch |
2nd Floor,
Wenjin Hotel |
| 13:45-14:10 |
Session 7
Chair: Noam Nisan |
Title: Strategy Iteration Is Strongly Polynomial for 2-Player Turn-Based Stochastic Games with a Constant Discount Factor
Thomas Dueholm Hansen, Peter Bro Miltersen and Uri Zwick |
Lecture Hall
(2nd Floor),
FIT Building,
Tsinghua University |
| 14:10-14:35 |
Title: Query Complexity Lower Bounds for Reconstruction of Codes
Sourav Chakraborty, Eldar Fischer and Arie Matsliah |
| 14:35-15:00 |
Title: Optimal Lower Bounds for Locality Sensitive Hashing (Except When q Is Tiny)
Ryan O'Donnell, Yi Wu and Yuan Zhou |
| 15:00-15:25 |
Title: Cycle Detection, Order Finding and Discrete Log with Jumps
Sourav Chakraborty, David Garcia-Soriano and Arie Matsliah |
|
15:25-15:45 |
Coffee Break |
|
15:45-16:10 |
Session 8
Chair: Uri Zwick |
Title: Ideal Forms of Coppersmith's Theorem and Guruswami-Sudan List Decoding
Henry Cohn and Nadia Heninger |
| 16:10-16:35 |
Title: Shallow Circuits with High-Powered Inputs
Pascal Koiran |
| 16:35-17:00 |
Title: Pricing Loss Leaders Can Be Hard
Yi Wu
|
| 17:00-17:25 |
Title: The Need for Structure in Quantum Speedups
Scott Aaronson and Andris Ambainis |
| 17:25-17:50 |
Title: Leaky Pseudo-Entropy Functions
Mark Braverman, Avinatan Hassidim and Yael Tauman Kalai |
|
| Sunday January 9, 2011 |
| TIME |
ACTIVITIES |
VENUE |
| 08:30-08:55 |
Session 9
Chair:Benny Applebaum |
Title: Combinatorial Approximation Algorithms for MaxCut using Random Walks
Satyen Kale and C. Seshadhri |
Lecture Hall
(2nd Floor),
FIT Building,
Tsinghua University |
| 08:55-09:20 |
Title: The Hitchhiker's Guide to Affiliation Networks: A Game-Theoretic Approach
Christian Borgs, Jennifer Chayes, Jian Ding and Brendan Lucier |
| 09:20-09:45 |
Title: Understanding Space in Proof Complexity: Separations and Trade-offs via Substitutions
Eli Ben-Sasson and Jakob Nordstrom |
| 09:45-10:10 |
Title: Distributed Computing with Adaptive Heuristics
Aaron D. Jaggard, Michael Schapira and Rebecca N. Wright |
| 10:20-10:40 |
Coffee Break |
| 10:40-11:05 |
Session 10
Chair:Sanjeev Khanna |
Title: Complex Semidefinite Programming Revisited and the Assembly of Circular Genomes
Konstantin Makarychev and Alantha Newman |
| 11:05-11:30 |
Title: On Approximating the Entropy of Polynomial Mappings
Zeev Dvir, Dan Gutfreund, Guy Rothblum and Salil Vadhan |
| 11:30-11:55 |
Title: Economical Graph Discovery
Noga Alon, Yuval Emek, Michal Feldman and Moshe Tennenholtz |
| 12:00-13:45 |
Lunch |
2nd Floor,
Wenjin Hotel |
| 13:45-14:10 |
Session 11
Chair:Noam Nisan |
Title: Cross-Validation and Mean-Square Stability
Satyen Kale, Ravi Kumar and Sergei Vassilvitskii |
Lecture Hall
(2nd Floor),
FIT Building,
Tsinghua University |
| 14:10-14:35 |
Title: The Complexity of Linear Dependence Problems in Vector Spaces
Arnab Bhattacharyya, Piotr Indyk, David P. Woodruff and Ning Xie |
| 14:35-15:00 |
Title: The Effects of Diversity in Aggregation Games
Petros Mol, Andrea Vattani and Panagiotis Voulgaris |
|
15:00-15:25 |
Title: Computationally Limited Randomness
Matei David, Phuong Nguyen, Periklis Papakonstantinou and Anastasios Sidiropoulos |
|
15:25-15:45 |
Coffee Break |
|
15:45-18:00 |
Panel Discussion: Algorithmic Game Theory and Economics: Area, Technique, or Fad?
Noam Nisan (chair), Peter Bro-Miltersen, Silvio
Micali, Shang-Hua Teng
Closing Ceremony
|
| 18:00-20:00 |
Banquet |
Grand Ball Room
Wenjin Hotel |