3 citations · 3 across the 4 of their papers we have counts for
4 papers
Kolmogorov-Loveland Sets and Advice Complexity Classes
Thomas Hugel
Loveland complexity is a variant of Kolmogorov complexity, where it is asked to output separately the bits of the desired string, instead of the string itself. Similarly to the res…
Second Moment Method on k-SAT: a General Framework
Thomas Hugel, Yacine Boufkhad
We give a general framework implementing the Second Moment Method on k-SAT and discuss the conditions making the Second Moment Method work in this framework. As applications, we ma…
Estimating Satisfiability
Yacine Boufkhad, Thomas Hugel
The problem of estimating the proportion of satisfiable instances of a given CSP (constraint satisfaction problem) can be tackled through weighting. It consists in putting onto eac…
Non Uniform Selection of Solutions for Upper Bounding the 3-SAT Threshold
Thomas Hugel, Yacine Boufkhad
We give a new insight into the upper bounding of the 3-SAT threshold by the first moment method. The best criteria developed so far to select the solutions to be counted discrimina…