Showing cs.CCShow all
2 papers · 1 filter
cs.CC2020
Complexity Measures on the Symmetric Group and Beyond
Neta Dafni, Yuval Filmus, Noam Lifshitz +2
We extend the definitions of complexity measures of functions to domains such as the symmetric group. The complexity measures we consider include degree, approximate degree, decisi…
cs.CC2020
Towards a Complexity-theoretic Understanding of Restarts in SAT solvers
Chunxiao Li, Noah Fleming, Marc Vinyals +2
Restarts are a widely-used class of techniques integral to the efficiency of Conflict-Driven Clause Learning (CDCL) Boolean SAT solvers. While the utility of such policies has been…