ITCS 2013
|
|
Conference Program
Wednesday, January 9th Reception at Hotel Shattuck, 7-10pm
Thursday, January 10th Graduating Bits. 5:30-7:30. Dinner Provided. Local Favorite. Organic. Bechtel , 5:45-9:45pm
Friday, January 11th Banquet/Jazz Performance by Saxaphonist George Brook in Hearst Mining, 5:45-9:45pm
Conference Location: Sibley Auditorium in Bechtel Engineering Center.
For a map of these locations, click here.
| Wednesday, January 9, 2013 | ||
|---|---|---|
| 7:00-10:00 | Reception at Hotel Shattuck, 2086 Allston Way | |
| Thursday, January 10, 2013 | ||
| 8:00-8:40 | Registration and Continental Breakfast | |
|
Session 1 Chair: 8:40-8:50 |
||
| 8:50-9:10 |
Massive Online Teaching to Bounded Learners
Brendan Juba and Ryan Williams |
|
| 9:10-9:30 |
Learning Mixtures of Spherical Gaussians: Moment Methods and Spectral Decompositions
Daniel Hsu and Sham M. Kakade |
|
| 9:30-9:50 |
Low-Weight Halfspaces for Sparse Boolean Vectors
Philip M. Long and Rocco A. Servedio |
|
| 9:50-10:10 |
Learnability of DNF with Representation-Specific Queries
Liu Yang, Avrim Blum, and Jaime Carbonell |
|
| 10:10-10:35 | Coffee break | |
|
Session 2 Chair: 10:35-10:45 |
||
| 10:45-11:05 |
Can Theories Be Tested? A Cryptographic Treatment of Forecast Testing Kai-Min Chung, Edward Lui, and Rafael Pass |
|
| 11:05-11:25 |
Multiplicative Updates in Coordination Games and the Theory of Evolution Erick Chastain, Adi Livnat, Christos Papadimitriou, and Umesh Vazirani |
|
| 11:25-11:45 |
Making Evolution Rigorous — The Error Threshold Nisheeth K. Vishnoi |
|
| 11:45-12:05 |
On the Convergence of the Hegselmann-Krause System Arnab Bhattacharyya, Mark Braverman, Bernard Chazelle, and Huy L. Nguyen |
|
| 12:05-2:00 |
Lunch
|
|
|
Session 3 Chair: 2:00-2:10 |
||
| 2:10-2:30 |
Is Privacy Compatible with Truthfulness? David Xiao |
|
| 2:30-2:50 |
Differentially Private Analysis of Social Networks via Restricted Sensitivity
Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet |
|
| 2:50-3:10 |
Characterizing the Sample Complexity of Private Learners Amos Beimel, Kobbi Nissim, and Uri Stemmer |
|
| 3:10-3:30 |
Barriers in Cryptography with Weak, Correlated and Leaky Sources Daniel Wichs |
|
| 3:30-3:55 |
Coffee Break
|
|
|
Session 4 Chair: 3:55-4:05 |
||
| 4:05-4:25 |
On the Possibilities and Limitations of Pseudodeterministic Algorithms Oded Goldreich, Shafi Goldwasser, and Dana Ron |
|
| 4:25-4:45 |
Evasiveness Through Circuit Lens
Raghav Kulkarni |
|
| 4:45-5:05 |
The Garden-Hose Model
Harry Buhrman, Serge Fehr, Christian Schaffner, and Florian Speelman |
|
| 5:05-5:25 |
Space-Bounded Communication Complexity
Joshua Brody, Shiteng Chen, Periklis Papakonstantinou, Hao Song, and Xiaoming Sun |
|
| 5:35-7:35 |
Graduating Bits Short presentations by finishing Ph.D.'s and postdocs |
|
| 7:35-9:00 |
Graduating Bits Reception Dinner from Chaam provided. |
|
| | ||
| Friday, January 11, 2013 | ||
|---|---|---|
| 8:00-8:40 | Registration and Continental Breakfast | |
|
Session 5 Chair: 8:40-8:50 |
||
| 8:50-9:10 |
Towards An Optimal Query Efficient PCP?
Subhash Khot, Muli Safra, and Madhur Tulsiani |
|
| 9:10-9:30 |
A Characterization of Approximation Resistance for Even k-Partite CSPs
Per Austrin and Subhash Khot |
|
| 9:30-9:50 |
On the Optimality of Relaxations for Average-Case and Generalized Constraint Satisfaction Problems
Boaz Barak, Guy Kindler, and David Steurer |
|
| 9:50-10:10 |
On the Power of Many One-Bit Provers
Per Austrin, Johan Håstad, and Rafael Pass |
|
| 10:10-10:35 | Coffee break | |
|
Session 6 Chair: 10:35-10:45 |
||
| 10:45-11:05 |
Approaching Utopia: Strong Truthfulness and Externality-Resistant Mechanisms Amos Fiat, Anna Karlin, Elias Koutsoupias, and Angelina Vidali |
|
| 11:05-11:25 |
Parametric Digital Auctions Pablo Daniel Azar and Silvio Micali |
|
| 11:25-11:45 |
Learning and Incentives in User-Generated Content: Multi-Armed Bandits with Endogenous Arms Arpita Ghosh and Patrick Hummel |
|
| 11:45-12:05 |
Welfare Maximization and the Supermodular Degree Uriel Feige and Rani Izsak |
|
| 12:05-2:00 |
Lunch
|
|
|
Session 7 Chair: 2:00-2:10 |
||
| 2:10-2:30 |
Reachability in Graph Timelines
Jakub Łącki and Piotr Sankowski |
|
| 2:30-2:50 |
Runtime Guarantees for Regression Problems
Hui Han Chin, Aleksander Mądry, Gary Miller, and Richard Peng |
|
| 2:50-3:10 |
An Energy Complexity Model for Algorithms
Swapnoneel Roy, Atri Rudra, and Akshat Verma |
|
| 3:10-3:30 |
Streaming Computations With a Loquacious Prover
Hartmut Klauck and Ved Prakash |
|
| 3:30-3:55 |
Coffee Break
|
|
|
Session 8 Chair: 3:55-4:05 |
||
| 4:05-4:25 |
A Classical Leash for a Quantum System: Command of Quantum Systems Via Rigidity of CHSH Games
Ben Reichardt, Falk Unger, and Umesh Vazirani |
|
| 4:25-4:45 |
Adversary Lower Bound for the k-sum Problem Aleksandrs Belovs and Robert Špalek |
|
| 4:45-5:05 |
Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete Hirotada Kobayashi, Francois Le Gall, and Harumichi Nishimura |
|
| 5:05-5:25 |
Active Self-Assembly of Algorithmic Shapes and Patterns in Polylogarithmic Time Damien Woods, Ho-Lin Chen, Scott Goodfriend, Nadine Dabby, Erik Winfree, and Peng Yin |
|
| 5:45-9:00 |
Banquet/Jazz Performance in Hearst Mining Building
|
|
| | ||
| Saturday, January 12, 2013 | ||
|---|---|---|
| 8:00-8:30 | Registration and Continental Breakfast | |
|
Session 9 Chair: 8:30-8:40 |
||
| 8:40-9:00 |
An Equational Approach to Secure Multi-Party Computation
Daniele Micciancio and Stefano Tessaro |
|
| 9:00-9:20 |
Noninteractive Timestamping and Publicly Verifiable Proofs of Work
Mohammad Mahmoody, Tal Moran, and Salil Vadhan |
|
| 9:20-9:40 |
On the Power of Nonuniformity in Proofs of Security
Kai-Min Chung, Huijia Lin, Mohammad Mahmoody, and Rafael Pass | |
| 9:40-10:00 |
Fast Reductions from RAMs to Delegatable Succinct Constraint Satisfaction Problems
Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, and Eran Tromer |
|
| 10:00-10:20 |
Resource-based Corruptions and the Combinatorics of Hidden Diversity
Juan Garay, David Johnson, Aggelos Kiayias, and Moti Yung |
|
| 10:20-10:45 | Coffee break | |
|
Session 10 Chair: 10:45-10:55 |
||
| 10:55-11:15 |
Time Hierarchies for Sampling Distributions Thomas Watson Best Student Paper Award |
|
| 11:15-11:35 |
Properties and Applications of Boolean Function Composition Avishay Tal Best Student Paper Award |
|
| 11:35-11:55 |
Pseudo-partitions, Transversality and Locality: A Combinatorial Characterization for the Space Measure in Algebraic Proof Systems
Ilario Bonacina and Nicola Galesi |
|
| 11:55-12:15 |
Competing Provers Protocols for Circuit Evaluation Gillat Kol and Ran Raz |
|
| 12:15-2:00 |
Lunch
|
|
|
Session 11 Chair: 2:00-2:10 |
||
| 2:10-2:30 |
Catch Them If You Can: How to Serve Impatient Users
Marek Cygan, Matthias Englert, Anupam Gupta, Marcin Mucha, and Piotr Sankowski |
|
| 2:30-2:50 |
Instance-Sensitive Robustness Guarantees for Sequencing with Unknown Packing and Covering Constraints
Nicole Megow and Julián Mestre |
|
| 2:50-3:10 |
Robust Optimization in the Presence of Uncertainty
Joachim M. Buhmann, Matúš Mihalák, Rastislav Šrámek, and Peter Widmayer |
|
| 3:10-3:30 |
Sorting Noisy Data with Partial Information
Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan |
|
| 3:30-3:55 |
Tapas! (Coffee)
|
|
|
Session 12 Chair: 3:55-4:05 |
||
| 4:05-4:25 |
New Affine-Invariant Codes from Lifting
Alan Guo, Swastik Kopparty, and Madhu Sudan |
|
| 4:25-4:45 |
H-wise Independence Ishay Haviv and Michael Langberg |
|
| 4:45-5:05 |
Sparse Extractor Families for All the Entropy Andrej Bogdanov and Siyao Guo |
|
| 5:05-5:25 |
On the Power of Conditional Samples in Distribution Testing Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, and Arie Matsliah |
|
| 5:25 PM |
End of Conference |
|
