All scheduled events are held at the Fields Center of Princeton University. The Fields Center (aka Carl A. Fields Center) can be located on Google Maps and on the campus map.
Saturday January 11th
19:00-21:00 Reception (Room 101)
Sunday January 12th
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, Dominik Scheder, Sune Jakobsen 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 17:30-20:00 Graduating Bits (see list of speakers). With break, followed by reception, in Room 101.
Monday January 13th
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?
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
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 (Rooms 105, 106)
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
17:10-17:30 David Gamarnik and Madhu Sudan, Limits of local algorithms over sparse random graphs
Evening program: Conference dinner (18:00, lobby) and after-dinner talk by Peter Winkler
Tuesday January 14th
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 (Rooms 105, 106)
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
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
ITCS 2014 