Program

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?

10:00-10:30 Coffee Break (Rooms 105, 106)

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 (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

15:30-16:00 Coffee Break (Rooms 105, 106)

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