Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
  
 

16.07.2018

Best paper award at SAT

Tobias Friedrich and Ralf Rothenberger received the 2018 Best Paper Award of the International Conference on Theory and Applications of Satisfiability Testing (SAT). They showed that random propositional formulas exhibit a sharp satisfiability threshold for a wide range of heterogeneous probability ensembles, notably including power-law distributions. This generalizes the uniform sharp-threshold result by Friedgut from 1999 to the non-uniform case.

We congratulate the two authors for this achievement.

  • Sharpness of the Satisfia... - Download
    Friedrich, Tobias; Rothenberger, Ralf Sharpness of the Satisfiability Threshold for Non-Uniform Random k-SAT. Theory and Applications of Satisfiability Testing (SAT) 2018: 273--291