Tentative Program for ITCS 2014

5th Innovations in Theoretical Computer Science Conference, Princeton New Jersey

All Events Held at the Fields Center of Princeton University (Map)

Saturday, January 11th 2014

19:00-21:00 Reception (Room 101)

Sunday, January 12th 2014, 19:00-21:00

Breakfast 08:00-08:30 (Rooms 105-106)
Session 1: 8:30 - 10:00
08:30-08:40  Session Chair - Kobbi Nissim
08:40-09:00  Zvika Brakerski and Vinod Vaikuntanathan, Lattice-Based FHE as Secure as PKE
09:00-09:20  Joshua Brody, Sune Jakobsen, Dominik Scheder and Peter Winkler, Cryptogenography
09:20-09:40   Mohammad Mahmoody, Hemanta Maji and Manoj Prabhakaran, Limits of Random Oracles in Secure Computation
09:40-10:00   Umesh Vazirani and Thomas Vidick, Fully device independent quantum key distribution

10:00-10:30 Coffee Break (Lobby)

Session 2: 10:30 - 12:00
10:30-10:40  Session Chair - Shubhangi Saraf
10:40-11:00  Amir Shpilka, Avishay Tal and Ben Lee Volk, On the Structure of Boolean Functions with Small Spectral Norm
11:00-11:20  Pavel Hrubes and Avi Wigderson, Non-commutative arithmetic circuits with division
11:20-11:40  Andrew Wan, John Wright and Chenggang Wu. Decision Trees, Protocols, and the Fourier Entropy-Influence Conjecture
11:40-12:00 Parikshit Gopalan, Salil Vadhan and Yuan Zhou, Locally Testable Codes and Cayley Graphs

12:00-14:00 Lunch Break (Lobby)

Session 3: 14:00 - 15:30
14:00-14:10  Session Chair - Michael Kearns
14:10-14:30  Uriel Feige and Moshe Tennenholtz, Invitation games and the price of stability
14:30-14:50  Mark Braverman and Kanika Pasricha. The computational hardness of pricing compound options
14:50-15:10  Deeparnab Chakrabarty and Chaitanya Swamy, Welfare Maximization and Truthfulness in Mechanism Design with Ordinal Preferences
15:10-15:30  Sayan Bhattacharya, Sungjin Im, Janardhan Kulkarni and Kamesh Munagala, Coordination Mechanisms from (almost) all Scheduling Policies

15:30-16:00 Coffee Break (Lobby)

Session 4: 16:00 - 17:30
16:00-16:10  Session Chair - David Xiao
16:10-16:30  Ran Gelles, Amit Sahai and Akshay Wadia, Private Interactive Communication Across an Adversarial Channel
16:30-16:50  Cristopher Moore and Leonard Schulman, Tree Codes and a Conjecture on Exponential Sums
16:50-17:10  Mahdi Cheraghchi and Venkatesan Guruswami, Capacity of Non-Malleable Codes
17:10-17:30  Erez Druk and Yuval Ishai, Linear-Time Encodable Codes Meeting the Gilbert-Varshamov Bound and Their Cryptographic Applications

Evening program: Graduating Bits 17:30-20:00

Monday, January 13th 2014

Breakfast 08:00-08:30 (Rooms 105-106)
Session 5: 8:30 - 10:00
08:30-08:40  Session Chair - Costis Daskalakis
08:40-09:00  Fernando Brandao, Aram Harrow, James Lee and Yuval Peres, Adversarial hypothesis testing and a quantum Stein's Lemma for restricted measurements
09:00-09:20  Yossi Azar, Uriel Feige, Michal Feldman and Moshe Tennenholtz, Sequential Decision Making with Vector Outcomes
09:20-09:40  Yuval Rabani, Leonard Schulman and Chaitanya Swamy, Learning Mixtures of Arbitrary Distributions over Large Discrete Domains
09:40-10:00  Jonathan Berry, Luke Fostvedt, Daniel Nordman, Cynthia Phillips, C. Seshadhri and Alyson Wilson, Why do simple algorithms for triangle enumeration work in the real world?

10:00-10:30 Coffee Break (Lobby)

Session 6: 10:30 - 12:00
10:30-10:40  Session Chair - Vinod Vaikuntanathan
10:40-11:00   Zvika Brakerski and Guy Rothblum, Black-Box Obfuscation for d-CNFs
11:00-11:20   Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath and Alon Rosen, Candidate weak pseudorandom functions in AC0 o MOD2
11:20-11:40   Eric Miles, Iterated group products and leakage resilience against NC^1
11:40-12:00  Yi-Kai Liu, Building one-time memories from isolated qubits

12:00-14:00 Lunch Break (Lobby)

Session 7: 14:00 - 15:30
14:00-14:10  Session Chair - Bernard Chazelle
14:10-14:30  Elaine Angelino and Varun Kanade, Attribute-Efficient Evolvability of Sparse Linear Functions
14:30-14:50  Zeph Landau, Umesh Vazirani and Thomas Vidick, A polynomial-time algorithm for the ground state of 1D gapped local Hamiltonians
14:50-15:10  Antonios Antoniadis, Neal Barcelo, Michael Nugent, Kirk Pruhs and Michele Scquizzato, Energy-Efficient Circuit Design
15:10-15:30  Ho-Lin Chen, David Doty and David Soloveichik, Rate-independent computation in mass-action chemical reaction networks

15:30-16:00 Coffee Break (Lobby)

Session 8: 16:00 - 17:30
16:00-16:10  Session Chair - Yuval Filmus
16:10-16:30   Nader Bshouty, Testers and their Applications
16:30-16:50   Manor Mendel and Assaf Naor, Expanders with respect to Hadamard spaces and random graphs
16:50-17:10   Laszlo Babai, On the Automorphism Groups of Strongly Regular Graphs I
7:10-17:30   David Gamarnik and Madhu Sudan, Limits of local algorithms over sparse random graphs

Evening program: Conference dinner and after dinner talk by Peter Winkler on Computability and Phase Transition (18:00i, Lobby)

Tuesday, January 14th 2014

Breakfast 08:00-08:30 (Rooms 105-106)
Session 9: 8:30 - 10:00
08:30-08:40  Session Chair - Daniel Wichs
08:40-09:00  Elad Haramaty and Madhu Sudan, Deterministic Compression with Uncertain Priors
09:00-09:20  Karthekeyan Chandrasekaran, Justin Thaler, Jonathan Ullman and Andrew Wan, Faster Private Release of Marginals on Small Databases
09:20-09:40  Michael Kearns, Mallesh Pai, Aaron Roth and Jonathan Ullman, Mechanism Design in Large Games: Incentives and Privacy
09:40-10:00  Kobbi Nissim, Salil Vadhan and David Xiao, Redrawing the Boundaries on Purchasing Data from Privacy-Sensitive Individuals

10:00-10:30 Coffee Break (Lobby)

Session 10: 10:30 - 12:00
10:30-10:40  Session Chair - Sanjeev Arora
10:40-11:00  Yuichi Yoshida and Yuan Zhou, Approximation Schemes via Sherali-Adams Hierarchy for Dense Constraint Satisfaction Problems and Assignment Problems
11:00-11:20  Venkatesan Guruswami and Euiwoong Lee, Complexity of approximating CSP with Balance / Hard Constraints
11:20-11:40  Karthekeyan Chandrasekaran and Santosh Vempala, Integer Feasibility of Random Polytopes
11:40-12:00  Afonso S. Bandeira, Moses Charikar, Amit Singer and Andy Zhu, Multireference Alignment using Semidefinite Programming

12:00-14:00 Lunch Break (Lobby)

Session 11: 14:00 - 15:30
14:00-14:10  Session Chair - Ran Raz
14:10-14:30  Rishi Gupta, Tim Roughgarden and C. Seshadhri, Decompositions of Triangle-Dense Graphs
14:30-14:50  Eldar Fischer, Oded Lachish and Yonatan Goldhirsh, Partial tests, universal tests and decomposability
14:50-15:10  Tali Kaufman and Alexander Lubotzky, High Dimensional Expanders and Property Testing
15:10-15:30  Kazuo Iwama and Yuichi Yoshida, Parameterized Testability

15:30-16:00 Coffee Break (Lobby)

Session 12: 16:00 - 17:30
16:00-16:10  Session Chair - Uri Feige
16:10-16:30  Gillat Kol, Shay Moran, Amir Shpilka and Amir Yehudayoff. Direct Sum Fails for Zero Error Average Communication
16:30-16:50  Siyao Guo, Pavel Hubacek, Alon Rosen and Margarita Vald. Rational Arguments: Single Round Delegation with Sublinear Verification
16:50-17:10  Mark Braverman, Jing Chen and Sampath Kannan, Optimal Provision-After-Wait in Healthcare
17:10-17:30  Joseph Y. Halpern, Rafael Pass and Lior Seeman. The Truth Behind the Myth of the Folk Theorem