CCC 2014 Accepted papers

(In order of submission)

Note: The affiliation with IEEE is currently under discussion. Please check out the discussion forum.
  • A Pseudorandom Generator for Polynomial Threshold Functions of Gaussian with Subpolynomial Seed Length
    Daniel M. Kane (Stanford University)

  • Locally Dense Codes
    Daniele Micciancio (University of California, San Diego)

  • Counting List Matrix Partitions of Graphs
    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)

  • Low influence functions over slices of the Boolean hypercube are juntas
    Karl Wimmer (Duquesne University)

  • 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)

  • Quantum Algorithms for Learning Symmetric Juntas via Adversary Bound
    Aleksandrs Belovs (Massachusetts Institute of Technology)

  • 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)

  • 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)

  • Unifying known lower bounds via geometric complexity theory
    Joshua A. Grochow (University of Toronto)

  • 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)

  • Hardness of Finding Independent Sets in 2-Colorable Hypergraphs and of Satisfiable CSPs
    Rishi Saket (IBM India Research Lab)

  • Direct Product Testing
    Irit Dinur (Weizmann Institute of Science), David Steurer (Cornell University)

  • Overlays and Limited Memory Communication Mode(l)s
    Periklis Papakonstantinou (Tsinghua University), Dominik Scheder (Simons Institute for the Theory of Computing, UC Berkeley, and Tsinghua University), Hao Song (Tsinghua University)

  • Linear list-approximation for short programs (or the power of a few random bits)
    Bruno Bauwens (Universite de Lorraine, Nancy), Marius Zimand (Towson University, Baltimore)

  • Hitting Sets for Low-Degree Polynomials with Optimal Density
    Venkatesan Guruswami (Carnegie Mellon University), Chaoping Xing (Nanyang Technological University)

  • 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)

  • On physical problems that are slightly more difficult than QMA
    Andris Ambainis (University of Latvia)

  • Goldreich's PRG: Evidence for near-optimal polynomial stretch
    Ryan O'Donnell (Carnegie Mellon University), David Witmer (Carnegie Mellon University)

  • Fourier Concentration from Shrinkage
    Russell Impagliazzo (University of California, San Diego), Valentine Kabanets (Simon Fraser University)

  • AM with Multiple Merlins
    Scott Aaronson (Massachusetts Institute of Technology), Russell Impagliazzo (University of California, San Diego), Dana Moshkovitz (Massachusetts Institute of Technology)

  • Counting the Number of Perfect Matchings in $K_5$-free Graphs
    Simon Straub (Ulm University), Thomas Thierauf (Aalen University), Fabian Wagner (Ulm University)

  • Noncommutative Determinant is Hard: A Simple Proof Using an Extension of Barrington's Theorem
    Craig Gentry (IBM T.J. Watson Research Center)

  • On the power of symmetric LP and SDP relaxations
    James R. Lee (University of Washington), Prasad Raghavendra (University of California, Berkeley), David Steurer (Cornell University), Ning Tan (University of California, Berkeley)

  • Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization
    Swastik Kopparty (Rutgers University), Shubhangi Saraf (Rutgers University), Amir Shpilka (Technion)

  • A composition theorem for parity kill number
    Ryan O'Donnell (Carnegie Mellon University), Xiaorui Sun (Columbia University), Li-Yang Tan (Columbia University), John Wright (Carnegie Mellon University), Yu Zhao (Carnegia Mellon University)

  • On the Closest Vector Problem with a Distance Guarantee
    Daniel Dadush (New York University), Oded Regev (New York University), Noah Stephens-Davidowitz (New York University)

  • Lower Bounds for Testing Properties of Functions over Hypergrid Domains
    Eric Blais (Massachusetts Institute of Technology), Sofya Raskhodnikova (Pennsylvania State University), Grigory Yaroslavtsev (ICERM, Brown University)

  • Narrow Proofs May Be Maximally Long
    Albert Atserias (Universitat Politecnica de Catalunya, Barcelona), Massimo Lauria (KTH Royal Institute of Technology, Stockholm), Jakob Nordstrom (KTH Royal Institute of Technology, Stockholm)

  • On the sum of L1 influences
    Artūrs Bačkurs (Massachusetts Institute of Technology), Mohammad Bavarian (Massachusetts Institute of Technology)