CCC 2014: Program

Program Summary

Location   All events take place in room #1900 unless indicated otherwise. See the local arrangements for more details.

Online Proceedings   Click the titles of the papers below to view the paper. You will be prompted for a username and password. These have been sent by email to all those registered for the conference. Those registered may also download the entire proceedings here.

Slides from Presentations   Many of the presenters at the conference have agreed to have their slides posted here. For these, there will be a link "slides" next to the paper title below. Click the link to download the slides. You will be prompted for a username and password; use the same credentials as for the proceedings (which have been emailed to all registrants of the conference).

Tuesday June 10

2:00 - 5:00 PMOrganizational Meeting, room #2200
5:30 PMOpening Reception, room #1400-1410

Wednesday June 11

8:00 AM Coffee and Pastries
8:30 AM Goldreich's PRG: Evidence for near-optimal polynomial stretch (slides)

Ryan O'Donnell (Carnegie Mellon University), David Witmer (Carnegie Mellon University)

9:00 AM On the power of symmetric LP and SDP relaxations (slides)

James R. Lee (University of Washington), Prasad Raghavendra (University of California, Berkeley), David Steurer (Cornell University), Ning Tan (University of California, Berkeley)

Best Student Paper Award Winner
9:30 AM Quantum algorithms for learning symmetric juntas via the adversary bound (slides)

Alexander Belov (Massachusetts Institute of Technology)

10:00 AM Break
10:30 AM On physical problems that are slightly more difficult than QMA (slides)

Andris Ambainis (University of Latvia)

11:00 AM AM with multiple Merlins (slides)

Scott Aaronson (Massachusetts Institute of Technology), Russell Impagliazzo (University of California, San Diego), Dana Moshkovitz (Massachusetts Institute of Technology)

11:30 AM Lunch (on your own)
1:30 PM Counting list matrix partitions of graphs (slides)

Andreas Goebel (University of Oxford), Leslie Ann Goldberg (University of Oxford), Colin McQuillan (University of Liverpool), David Richerby (University of Oxford), Tomoyuki Yamakami (University of Fukui)

2:00 PM Counting the number of perfect matchings in K_5 free graphs (slides)

Simon Straub (Ulm University), Thomas Thierauf (Aalen University), Fabian Wagner (Ulm University)

2:30 PM Hardness of finding independent sets in 2-colorable hypergraphs and of satisfiable CSPs (slides)

Rishi Saket (IBM India Research Lab)

3:00 PM Break
3:30 PM Locally dense codes (slides)

Daniele Micciancio (University of California, San Diego)

4:00 PM On the closest vector problem with a distance guarantee (slides)

Daniel Dadush (New York University), Oded Regev (New York University), Noah Stephens-Davidowitz (New York University)

4:30 PM Algorithms for group isomorphism via group extensions and cohomology

Joshua A. Grochow (University of Toronto), Youming Qiao (University of Technology, Sydney; and National University of Singapore)

5:00 PM Break
5:20 PM Rump Session
6:30 PM End of Talks

Thursday June 12

8:00 AM Coffee and Pastries
8:30 AM Low Influence functions over slices of the boolean hypercube are juntas

Karl Wimmer (Duquesne University)

9:00 AM On the sum of L1 influences (slides)

Artūrs Bačkurs (Massachusetts Institute of Technology), Mohammad Bavarian (Massachusetts Institute of Technology)

9:30 AM A composition theorem for parity kill number (slides)

Ryan O'Donnell (Carnegie Mellon University), Xiaorui Sun (Columbia University), Li-Yang Tan (Columbia University), John Wright (Carnegie Mellon University), Yu Zhao (Carnegie Mellon University)

10:00 AM Break
10:30 AM Invited Survey Lecture: Recent progress in lower bounds for arithmetic circuits (slides)

Shubhangi Saraf (Rutgers University)

11:30 AM Lunch (On your own)
1:30 PM Hitting sets for low-degree polynomials with optimal density (slides)

Venkatesan Guruswami (Carnegie Mellon University), Chaoping Xing (Nanyang Technological University)

2:00 PM Equivalence of polynomial identity testing and deterministic multivariate polynomial factorization (slides)

Swastik Kopparty (Rutgers University), Shubhangi Saraf (Rutgers University), Amir Shpilka (Technion)

2:30 PM Noncommutative determininant is hard: a simple proof using an extension of Barrington's theorem

Craig Gentry (IBM T.J. Watson Research Center)

3:00 PM Break
3:30 PM Direct product testing

Irit Dinur (Weizmann Institute of Science), David Steurer (Cornell University)

4:00 PM A parallel repetition theorem for entangled projection games

Irit Dinur (Weizmann Institute), David Steurer (Cornell University), Thomas Vidick (California Institute of Technology, and Simons Institute for the Theory of Computing)

4:30 PM A parallel repetition theorem for entangled two-player one-round games under product distributions

Rahul Jain (National University of Singapore), Attila Pereszlényi (National University of Singapore), Penghui Yao (National University of Singapore)

5:00 PM End of Talks
8:00 PM Business Meeting, room #1400-1410

Friday June 13

8:00 AM Coffee and Pastries
8:30 AM A PRG for polynomial threshold functions of Gaussian with subpolynomial seed length (slides)

Daniel M. Kane (Stanford University)

9:00 AM Deterministic approximate counting for juntas of degree-2 polynomial threshold functions

Anindya De (Institute for Advanced Study, Princeton), Ilias Diakonikolas (Univerity of Edinburgh), Rocco Servedio (Columbia University)

9:30 AM Linear list-approximation for short programs (or the power of a few random bits) (slides)

Bruno Bauwens (Universite de Lorraine, Nancy), Marius Zimand (Towson University, Baltimore)

10:00 AM Break
10:30 AM Invited Survey Lecture: Algorithms for circuits and circuits for algorithms

Ryan Williams (Stanford University)

11:30 AM Lunch (on your own)
1:30 PM Mining circuit lower bound proofs for meta-algorithms

Ruiwen Chen (Simon Fraser University), Valentine Kabanets (Simon Fraser University), Antonina Kolokolova (Memorial University of Newfoundland), Ronen Shaltiel (University of Haifa), David Zuckerman(University of Texas)

2:00 PM Unifying known lower bounds via geometric complexity theory

Joshua A. Grochow (University of Toronto)

2:30 PM Narrow proofs may be maximally long (slides)

Albert Atserias (Universitat Politecnica de Catalunya, Barcelona), Massimo Lauria (KTH Royal Institute of Technology, Stockholm), Jakob Nordstrom (KTH Royal Institute of Technology, Stockholm)

3:00 PM Break
3:30 PM Overlays and limited memory communication mode(l)s (slides [zip/keynote])

Periklis Papakonstantinou (Tsinghua University), Dominik Scheder (Simons Institute for the Theory of Computing, UC Berkeley, and Tsinghua University), Hao Song (Tsinghua University)

4:00 PM Lower bounds for testing properties of functions of hypergrid domains (slides)

Eric Blais (Massachusetts Institute of Technology), Sofya Raskhodnikova (Pennsylvania State University and Boston University), Grigory Yaroslavtsev (ICERM, Brown University)

4:30 PM Fourier Concentration from shrinkage

Russell Impagliazzo (University of California, San Diego), Valentine Kabanets (Simon Fraser University)

5:00 PM End of Conference

Saturday June 14

9:00 AM - noonOrganizational Meeting, room #1315