research
∙
07/21/2023
Computations with polynomial evaluation oracle: ruling out superlinear SETH-based lower bounds
The field of fine-grained complexity aims at proving conditional lower b...
share
research
∙
05/16/2022
Polynomial formulations as a barrier for reduction-based hardness proofs
The Strong Exponential Time Hypothesis (SETH) asserts that for every ε>0...
research
∙
03/02/2022
CNF Encodings of Parity
The minimum number of clauses in a CNF representation of the parity func...
research
∙
04/24/2020
Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds
We prove that the Hadwiger number of an n-vertex graph G (the maximum si...
research
∙
09/23/2018