Computational Complexity Conference

CCC'18 - Accepted Papers

  • New Hardness Results for the Permanent Using Linear Optics
    Daniel Grier and Luke Schaeffer
  • Dimension Reduction for Polynomials over Gaussian Space and Applications
    Badih Ghazi, Pritish Kamath and Prasad Raghavendra
  • Communication Complexity with Small Advantage
    Thomas Watson
  • Unbalancing Sets and an Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits
    Noga Alon, Mrinal Kumar and Ben Lee Volk
  • A New Approach for Constructing Low-Error, Two-Source Extractors
    Dean Doron, Amnon Ta-Shma, Avraham Ben-Aroya, Eshan Chattopadhyay and Xin Li
  • Earthmover Resilience and Testing in Ordered Structures
    Omri Ben-Eliezer and Eldar Fischer
  • Algebraic dependencies and PSPACE algorithms in approximative complexity
    Zeyu Guo, Nitin Saxena and Amit Sinhababu
  • Pseudorandom Generators from Polarizing Random Walks
    Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini and Shachar Lovett
  • Lower Bounds on Non-Adaptive Data Structures Maintaining Sets of Numbers, from Sunflowers
    Sivaramakrishnan Natarajan Ramamoorthy and Anup Rao
  • Hardness vs Randomness for Bounded Depth Arithmetic Circuits
    Chi-Ning Chou, Mrinal Kumar and Noam Solomon
  • Reordering Rule Makes OBDD Proof Systems Stronger
    Sam Buss, Dmitry Itsykson, Alexander Knop and Dmitry Sokolov
  • Testing Linearity against Non-Signaling Strategies
    Alessandro Chiesa, Peter Manohar and Igor Shinkar
  • Complexity Classification of Conjugated Clifford Circuits
    Adam Bouland, Joseph Fitzsimons and Dax Enshan Koh
  • Lossless dimension expanders via linearized polynomials and subspace designs
    Venkatesan Guruswami, Nicolas Resch and Chaoping Xing
  • On The Complexity of the Cayley Semigroup Membership Problem
    Lukas Fleischer
  • Two-player entangled games are NP-hard
    Anand Natarajan and Thomas Vidick
  • A PRG for Boolean PTF of degree 2 with seed length subpolynomial in $\epsilon$ and logarithmic in $n$
    Daniel Kane and Sankeerth Rao Karingula
  • Linear Sketching over F2
    Sampath Kannan, Elchanan Mossel, Swagato Sanyal and Grigory Yaroslavtsev
  • The Power of Natural Properties as Oracles
    Russell Impagliazzo, Valentine Kabanets and Ilya Volkovich
  • Small Normalized Boolean Circuits for Semi-disjoint Bilinear Forms Require Logarithmic Conjunction-depth
    Andrzej Lingas
  • Hardness Amplification for Non-Commutative Arithmetic Circuits
    Marco Carmosino, Russel Impagliazzo, Shachar Lovett and Ivan Mihajlin
  • Hardness of Function Composition for Semantic Read once Branching Programs
    Jeff Edmonds, Venkatesh Medabalimi and Toniann Pitassi
  • NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits
    Shuichi Hirahara, Igor Oliveira and Rahul Santhanam
  • Limits on representing Boolean functions by linear combinations of simple functions: thresholds, ReLUs, and low-degree polynomials
    Ryan Williams
  • On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product
    Lijie Chen
  • Efficient Batch Verification for UP
    Omer Reingold, Guy Rothblum and Ron Rothblum
  • A Tight Lower Bound for Entropy Flattening
    Yi-Hsiu Chen, Mika Göös, Salil Vadhan and Jiapeng Zhang
  • Worst-case to average case reductions for the distance to a code
    Eli Ben-Sasson, Swastik Kopparty and Shubhangi Saraf

Organized by:

In Cooperation with:


Sponsored by:

Microsoft Research