ITCS 2013
Innovations in Theoretical Computer Science


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