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
Adjourn