CCC 2014: Program
Program Summary
- Organizational meetings will be held on June 10 and June 14.
- An opening reception is on June 10.
- Regular talks are on June 11, June 12, and June 13.
- The talk for the best student award paper is at 9:30 AM on June 11.
- The rump session starts at 5:20pm on June 11.
- An invited talk by Shubhangi Saraf is at 10:30 AM on June 12.
- The business meeting is at 8:00pm on June 12.
- An invited talk by Ryan Williams is at 10:30 AM on June 13.
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
| Time | Talk/Event |
|---|---|
| 2:00 - 5:00 PM | Organizational Meeting, room #2200 |
| 5:30 PM | Opening Reception, room #1400-1410 |
Wednesday June 11
| Time | Talk/Event |
|---|---|
| 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
| Time | Talk/Event |
|---|---|
| 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
| Time | Talk/Event |
|---|---|
| 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
| Time | Talk/Event |
|---|---|
| 9:00 AM - noon | Organizational Meeting, room #1315 |