Prof. Dr. Tobias Friedrich


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.

  • sharp_SAT_final.pdf
    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