Conference Program

Saturday, January 7th Reception at Microsoft Research, 7-10pm

The ITCS 2012 reception is being hosted at Microsoft New England Research and Development Center in Cambridge MA at One Memorial Drive, Cambridge MA. For direction and maps click here.

The conference itself is being hosted by CSAIL, at the Stata Center, MIT, at 32 Vassar St, Cambridge MA . For direction and maps click here.

Sunday, January 8th, at the ground floor of the Stata Center, room 32-141

                    Sunday, January 8, 2012
8:30-9:10 Registration and Continental Breakfast
  Session 1
Chair: 9:10-9:20
9:20-9:40 High-Confidence Predictions under Adversarial Uncertainty
Andrew Drucker --- best student paper award!
9:40-10:00 Learning Hurdles for Sleeping Experts
Varun Kanade and Thomas Steinke
10:00-10:20 Restriction Access
Zeev Dvir, Anup Rao, Avi Wigderson, and Amir Yehudayoff
10:20-10:50 Coffee break
  Session 2
Chair: 10:50-11:00
11:00-11:20 Mechanism Design with Approximate Valuations
Alessandro Chiesa, Silvio Micali, and Zeyuan Allen Zhu
11:20-11:40 Quantum Strategic Game Theory
Shengyu Zhang
11:40-12:00 The Curse of Simultaneity
Renato Paes Leme, Vasilis Syrgkanis, and Eva Tardos
12:00-12:20 No Justified Complaints: On Fair Sharing of Multiple Resources
Danny Dolev, Dror G. Feitelson, Joseph Y. Halpern, Raz Kupferman, and Nathan Linial
12:20-2:00 Lunch
  Session 3
Chair: 2:00-2:10
2:10-2:30 From Randomizing Polynomials to Parallel Algorithms
Yuval Ishai, Eyal Kushilevitz, and Anat Paskin  
2:30-2:50 Practical Verified Computation with Streaming Interactive Proofs
Graham Cormode, Michael Mitzenmacher, and Justin Thaler
2:50-3:10 Paging for Multicore Shared Caches
Alejandro Lopez-Ortiz and Alejandro Salinger
3:10-3:40 Coffee Break
  Session 4
Chair: 3:40-3:50
3:50-4:10 Noise vs computational intractability in dynamics
Mark Braverman, Alexander Grigo, and Cristobal Rojas
4:10-4:30 Distribution Free Evolvability of Polynomial Functions over all Convex Loss Functions
Paul Valiant
4:30-4:50 Algorithms on Evolving Graphs
Aris Anagnostopoulos, Ravi Kumar, Mohammad Mahdian, Eli Upfal ,and Fabio Vandin

Monday, January 9th, at the ground floor of the Stata Center, room 32-141

                    Monday, January 9, 2012
8:30-9:00 Registration and Continental Breakfast
  Session 5
Chair: 9:00-9:10
9:10-9:30 Towards deterministic tree code constructions
Mark Braverman
9:30-9:50 Linear time decoding of regular expander codes
Michael Viderman
9:50-10:10 List decoding subspace codes from insertions and deletions
Venkatesan Guruswami, Srivatsan Narayanan, and Carol Wang
10:10-10:30 Bounds on Locally Testable Codes with Unique Tests
Gillat Kol and Ran Raz
10:30-10:50 Coffee break
  Session 6
Chair: 10:50-11:00
11:00-11:20 Approximately Optimal Mechanism Design via Differential Privacy
Kobbi Nissim, Rann Smorodinsky, and Moshe Tennenholtz
11:20-11:40 Fairness Through Awareness
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel
11:40-12:00 Prisoner's Dilemma on Graphs with Large Girth
Vahideh H. Manshadi and Amin Saberi
12:00-12:20 Crowdsourced Bayesian Auctions
Pablo Azar, Jing Chen, and Silvio Micali
12:20-1:50 Lunch
  Session 7
Chair: 1:50-2:00
2:00-2:20 Super-Polynomial Quantum Speed-ups for Boolean Evaluation Trees with Hidden Structure
Bohua Zhan, Shelby Kimmel, and Avinatan Hassidim
2:20-2:40 Quantum interactive proofs with weak error bounds
Tsuyoshi Ito, Hirotada Kobayashi, and John Watrous
2:40-3:00 Quantum money from knots
Eddie Farhi, David Gosset, Avinatan Hassidim, Andrew Lutomirski, and Peter Shor
3:00-3:20 Quantum rejection sampling
Maris Ozols, Martin Roetteler, and Jeremie Roland
3:20-3:40 Coffee Break
  Graduating bits
Finishing Ph.D.'s and Postdoc Short Presentations
Room 32-123
  Evening Program
Light Dinner and Community Building Playback
at the 4th floor of the Stata Center, the R&D space

Tuesday, January 10th, at the ground floor of the Stata Center, room 32-141

                    Tuesday, January 10, 2012
8:30-9:00 Registration and Continental Breakfast
  Session 8
9:10-9:30 Fully Homomorphic Encryption without Bootstrapping
Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan
9:30-9:50 From Extractable Collision Resistance to Succinct Non-Interactive Arguments of Knowledge, and Back Again
Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer
9:50-10:10 Targeted Malleability: Homomorphic Encryption for Restricted Computations
Dan Boneh, Gil Segev, and Brent Waters
10:10-10:30 Coffee break
  Session 9
Chair: 10:30-10:40
10:40-11:00 Sherali-Adams Relaxations and Indistinguishability in Counting Logics
Albert Atserias and Elitza Maneva
11:00-11:20 Graph Densification
Moritz Hardt, Nikhil Srivastava, and Madhur Tulsiani
11:20-11:40 Spectral sparsification via random spanners
Michael Kapralov and Rina Panigrahy
11:40-12:00 Multicommodity Flows and Cuts in Polymatroidal Networks
Chandra Chekuri, Sreeram Kannan, Adnan Raja, and Pramod Viswanath
12:00-1:30 Lunch
  Session 10
Chair: 1:30-1:40
1:40-2:00 On the Degree of Univariate Polynomials Over the Integers
Gil Cohen, Amir Shpilka, and Avishay Tal
2:00-2:20 On Persistent Homotopy, Knotted Complexes and the Alexander Module
David Letscher
2:20-2:40 Compressed Matrix Multiplication
Rasmus Pagh
2:40-3:00 Coffee break
  Session 11
Chair: 3:00-3:10
3:10-3:30 Gadgets and Anti-gadgets Leading to a Complexity Dichotomy
Jin-Yi Cai, Michael Kowalczyk, and Tyson Williams
3:30-3:50 On beating the hybrid argument
Bill Fefferman, Ronen Shaltiel, Christopher Umans, and Emanuele Viola
3:50-4:10 Linear programming, width-1 CSPs, and robust satisfaction
Gabor Kun, Ryan O'Donnell, Suguru Tamaki, Yuichi Yoshida, and Yuan Zhou
4:10-4:30 Marginal Hitting Sets Imply Super-Polynomial Lower Bounds for Permanent
Maurice Jansen and Rahul Santhanam
4:30-5:00 ITCS 0pen discussion
5:00 PM End of Conference