2 citations · 3 across the 13 of their papers we have counts for
Showing 2022Show all
2 papers · 1 filter
cs.CC2022
Polynomial formulations as a barrier for reduction-based hardness proofs
Tatiana Belova, Alexander Golovnev, Alexander S. Kulikov +2
The Strong Exponential Time Hypothesis (SETH) asserts that for every there exists such that -SAT requires time . The field of fine-grained…
cs.CC2022
CNF Encodings of Parity
Gregory Emdin, Alexander S. Kulikov, Ivan Mihajlin +1
The minimum number of clauses in a CNF representation of the parity function is . One can obtain a more compact CNF encoding by u…