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