Articles under category:
CCC
CCC
Vol 19, Article 4 (pp 1-61)
[CCC20 Spec Issue]
Non-Disjoint Promise Problems from Meta-Computational View of Pseudorandom Generator Constructions
by Shuichi Hirahara
Non-Disjoint Promise Problems from Meta-Computational View of Pseudorandom Generator Constructions
by Shuichi Hirahara
Vol 18, Article 21 (pp 1-32)
[CCC20 Spec Issue]
Hitting Sets Give Two-Sided Derandomization of Small Space
by Kuan Cheng and William M. Hoza
Hitting Sets Give Two-Sided Derandomization of Small Space
by Kuan Cheng and William M. Hoza
Vol 18, Article 19 (pp 1-22)
[CCC20 Spec Issue]
Sign-Rank vs. Discrepancy
by Kaave Hosseini, Hamed Hatami, and Shachar Lovett
Sign-Rank vs. Discrepancy
by Kaave Hosseini, Hamed Hatami, and Shachar Lovett
Vol 18, Article 15 (pp 1-33)
[CCC20 Spec Issue]
Multiparty Karchmer-Wigderson Games and Threshold Circuits
by Alexander Kozachinskiy and Vladimir Podolskii
Multiparty Karchmer-Wigderson Games and Threshold Circuits
by Alexander Kozachinskiy and Vladimir Podolskii
Vol 18, Article 14 (pp 1-4)
[CCC20 Spec Issue]
Special Issue: CCC 2020: Guest Editors' Foreword
by Zeev Dvir and Avishay Tal
Special Issue: CCC 2020: Guest Editors' Foreword
by Zeev Dvir and Avishay Tal
Vol 18, Article 8 (pp 1-18)
[CCC18 Spec Issue]
The Cayley Semigroup Membership Problem
by Lukas Fleischer
The Cayley Semigroup Membership Problem
by Lukas Fleischer
Vol 18, Article 5 (pp 1-28)
[CCC19 Spec Issue]
UG-hardness to NP-hardness by Losing Half
by Amey Bhangale and Subhash Khot
UG-hardness to NP-hardness by Losing Half
by Amey Bhangale and Subhash Khot
Vol 17, Article 11 (pp 1-38)
[CCC19 Spec Issue]
Hardness Magnification Near State-of-the-Art Lower Bounds
by Igor C. Oliveira, Ján Pich, and Rahul Santhanam
Hardness Magnification Near State-of-the-Art Lower Bounds
by Igor C. Oliveira, Ján Pich, and Rahul Santhanam
Vol 17, Article 10 (pp 1-88)
[CCC16 Spec Issue]
Proof Complexity Lower Bounds from Algebraic Circuit Complexity
by Michael A. Forbes, Amir Shpilka, Iddo Tzameret, and Avi Wigderson
Proof Complexity Lower Bounds from Algebraic Circuit Complexity
by Michael A. Forbes, Amir Shpilka, Iddo Tzameret, and Avi Wigderson
Vol 17, Article 9 (pp 1-30)
[CCC19 Spec Issue]
Sherali--Adams Strikes Back
by Ryan O'Donnell and Tselil Schramm
Sherali--Adams Strikes Back
by Ryan O'Donnell and Tselil Schramm
Vol 17, Article 2 (pp 1-32)
[CCC19 Spec Issue]
Barriers for Fast Matrix Multiplication from Irreversibility
by Matthias Christandl, Péter Vrana, and Jeroen Zuiddam
Barriers for Fast Matrix Multiplication from Irreversibility
by Matthias Christandl, Péter Vrana, and Jeroen Zuiddam
Vol 17, Article 1 (pp 1-30)
[CCC19 Spec Issue]
Limits on the Universal Method for Matrix Multiplication
by Josh Alman
Limits on the Universal Method for Matrix Multiplication
by Josh Alman
Vol 16, Article 20 (pp 1-48)
[CCC19 Spec Issue]
Fourier and Circulant Matrices are Not Rigid
by Zeev Dvir and Allen Liu
Fourier and Circulant Matrices are Not Rigid
by Zeev Dvir and Allen Liu
Vol 16, Article 19 (pp 1-5)
[CCC19 Spec Issue]
Special Issue: CCC 2019: Guest Editor's Foreword
by Yuval Filmus
Special Issue: CCC 2019: Guest Editor's Foreword
by Yuval Filmus
Vol 16, Article 4 (pp 1-50)
[CCC18 Spec Issue]
On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product
by Lijie Chen
On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product
by Lijie Chen
Vol 15, Article 16 (pp 1-30)
[CCC18 Spec Issue]
Algebraic Dependencies and PSPACE Algorithms in Approximative Complexity over Any Field
by Zeyu Guo, Nitin Saxena, and Amit Sinhababu
Algebraic Dependencies and PSPACE Algorithms in Approximative Complexity over Any Field
by Zeyu Guo, Nitin Saxena, and Amit Sinhababu
Vol 15, Article 10 (pp 1-26)
[CCC18 Spec Issue]
Pseudorandom Generators from Polarizing Random Walks
by Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, and Shachar Lovett
Pseudorandom Generators from Polarizing Random Walks
by Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, and Shachar Lovett
Vol 15, Article 9 (pp 1-3)
[CCC18 Spec Issue]
Special Issue: CCC 2018: Guest Editor's Foreword
by Srikanth Srinivasan
Special Issue: CCC 2018: Guest Editor's Foreword
by Srikanth Srinivasan
Vol 15, Article 6 (pp 1-47)
[CCC17 Spec Issue]
Noise Stability is Computable and Approximately Low-Dimensional
by Anindya De, Elchanan Mossel, and Joe Neeman
Noise Stability is Computable and Approximately Low-Dimensional
by Anindya De, Elchanan Mossel, and Joe Neeman
Vol 14, Article 10 (pp 1-33)
[CCC17 Spec Issue]
From Weak to Strong Linear Programming Gaps for All Constraint Satisfaction Problems
by Mrinalkanti Ghosh and Madhur Tulsiani
From Weak to Strong Linear Programming Gaps for All Constraint Satisfaction Problems
by Mrinalkanti Ghosh and Madhur Tulsiani
Vol 14, Article 9 (pp 1-55)
[CCC16 Spec Issue]
Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits
by Ruiwen Chen, Rahul Santhanam, and Srikanth Srinivasan
Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits
by Ruiwen Chen, Rahul Santhanam, and Srikanth Srinivasan
Vol 14, Article 6 (pp 1-73)
[CCC17 Spec Issue]
Trading Information Complexity for Error
by Yuval Dagan, Yuval Filmus, Hamed Hatami, and Yaqiao Li
Trading Information Complexity for Error
by Yuval Dagan, Yuval Filmus, Hamed Hatami, and Yaqiao Li
Vol 14, Article 3 (pp 1-21)
[CCC17 Spec Issue]
A Deterministic PTAS for the Commutative Rank of Matrix Spaces
by Markus Bläser, Gorav Jindal, and Anurag Pandey
A Deterministic PTAS for the Commutative Rank of Matrix Spaces
by Markus Bläser, Gorav Jindal, and Anurag Pandey
Vol 14, Article 2 (pp 1-2)
[CCC17 Spec Issue]
Special Issue: CCC 2017: Guest Editor's Foreword
by Shachar Lovett and Ryan O'Donnell
Special Issue: CCC 2017: Guest Editor's Foreword
by Shachar Lovett and Ryan O'Donnell
Vol 13, Article 21 (pp 1-38)
[CCC16 Spec Issue]
Decoding Reed–Muller Codes over Product Sets
by John Y. Kim and Swastik Kopparty
Decoding Reed–Muller Codes over Product Sets
by John Y. Kim and Swastik Kopparty
Vol 13, Article 6 (pp 1-33)
[CCC16 Spec Issue]
Arithmetic Circuits with Locally Low Algebraic Rank
by Mrinal Kumar and Shubhangi Saraf
Arithmetic Circuits with Locally Low Algebraic Rank
by Mrinal Kumar and Shubhangi Saraf
Vol 13, Article 2 (pp 1-21)
[CCC16 Spec Issue]
Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs
by Rohit Gurjar, Arpita Korwar, and Nitin Saxena
Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs
by Rohit Gurjar, Arpita Korwar, and Nitin Saxena
Vol 13, Article 1 (pp 1-3)
[CCC16 Spec Issue]
Special Issue: CCC 2016: Guest Editor's Foreword
by Prahladh Harsha
Special Issue: CCC 2016: Guest Editor's Foreword
by Prahladh Harsha