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