default search action
Computational Complexity, Volume 33
Volume 33, Number 1, June 2024
- Ferenc Bencs, Jeroen Huijben, Guus Regts:
Approximating the chromatic polynomial is as hard as computing it exactly. 1 - Daniel Avraham, Amir Yehudayoff:
On Blocky Ranks Of Matrices. 2 - Pranjal Dutta, Nitin Saxena, Thomas Thierauf:
Weighted Sum-of-Squares Lower Bounds for Univariate Polynomials Imply VP ≠q VNP. 3 - Susanna F. de Rezende
, Or Meir, Jakob Nordström
KRW Composition Theorems via Lifting. 4 - Yuval Filmus, Yuval Ishai, Avi Kaplan, Guy Kindler:
Limits of Preprocessing. 5 - Noah G. Singer, Madhu Sudan, Santhoshini Velusamy:
Streaming approximation resistance of every ordering CSP. 6 - Hubie Chen:
Algebraic Global Gadgetry for Surjective Constraint Satisfaction. 7
Volume 33, Number 2, December 2024
- Miroslav Rada, Michal Cerný, Ondrej Sokol:
The NP-hard problem of computing the maximal sample variance over interval data is solvable in almost linear time with a high probability. 8 - Laurence Kluge
Combinatorial refinement on circulant graphs. 9 - Zeyu Guo:
Variety Evasive Subspace Families. 10 - Abhranil Chatterjee, Mrinal Kumar, Ben Lee Volk:
Determinants vs. Algebraic Branching Programs. 11 - Ján Pich:
Localizability of the approximation method. 12 - Dominik Scheder, John P. Steinberger:
PPSZ for General k-SAT and CSP - Making Hertli's Analysis Simpler and 3-SAT Faster. 13
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-12-12 20:59 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: