Comput. Complex.

Keyphrases

Publications

volume 33, number 1, 2024

Noah G. Singer, Madhu Sudan, Santhoshini Velusamy
Streaming approximation resistance of every ordering CSP. Comput. Complex. 33 (1) (2024)
Ferenc Bencs, Jeroen Huijben, Guus Regts
Approximating the chromatic polynomial is as hard as computing it exactly. Comput. Complex. 33 (1) (2024)
Hubie Chen
Algebraic Global Gadgetry for Surjective Constraint Satisfaction. Comput. Complex. 33 (1) (2024)
Daniel Avraham, Amir Yehudayoff
On Blocky Ranks Of Matrices. Comput. Complex. 33 (1) (2024)
Yuval Filmus, Yuval Ishai, Avi Kaplan, Guy Kindler
Limits of Preprocessing. Comput. Complex. 33 (1) (2024)
Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere
KRW Composition Theorems via Lifting. Comput. Complex. 33 (1) (2024)
Pranjal Dutta, Nitin Saxena, Thomas Thierauf
Weighted Sum-of-Squares Lower Bounds for Univariate Polynomials Imply VP ≠q VNP. Comput. Complex. 33 (1) (2024)

volume 33, number 2, 2024

volume 32, number 1, 2023

volume 32, number 2, 2023

volume 31, number 1, 2022

volume 31, number 2, 2022

volume 30, number 1, 2021

Mark Giesbrecht, Armin Jamshidpey, Éric Schost
Subquadratic-Time Algorithms for Normal Bases. Comput. Complex. 30 (1) (2021)
Orr Paradise
Correction to: Smooth and Strong PCPs. Comput. Complex. 30 (1) (2021)
Fedor Part, Iddo Tzameret
Resolution with Counting: Dag-Like Lower Bounds and Different Moduli. Comput. Complex. 30 (1) (2021)

volume 30, number 2, 2021