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
∙
02/19/2021
SAT-based Circuit Local Improvement
Finding exact circuit size is a notorious optimization problem in practi...
research
∙
11/12/2018
Circuit Depth Reductions
The best known circuit lower bounds against unrestricted circuits remain...
research
∙
09/23/2018