501 citations · 1k across the 33 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2008
New Combinatorial Complete One-Way Functions
Arist Kojevnikov, Sergey I. Nikolenko
In 2003, Leonid A. Levin presented the idea of a combinatorial complete one-way function and a sketch of the proof that Tiling represents such a function. In this paper, we present…
cs.CC2003★ 3 cited
Hard satisfiable formulas for DPLL-type algorithms
Sergey I. Nikolenko
We address lower bounds on the time complexity of algorithms solving the propositional satisfiability problem. Namely, we consider two DPLL-type algorithms, enhanced with the unit…