Пятница 15.12. А. Смаль: "PPSZ for General k-SAT - Making Hertli's Analysis Simpler and 3-SAT Faster"

Пятница, 15 декабря, 402. Начало в 12:00.

Докладчик: А. Смаль.

Тема: PPSZ for General k-SAT - Making Hertli's Analysis Simpler and 3-SAT Faster.

Abstract

Доклад по статье Dominik Scheder, John Steinberger "PPSZ for General k-SAT - Making Hertli's Analysis Simpler and 3-SAT Faster" (http://drops.dagstuhl.de/opus/volltexte/2017/7535/)

В докладе будет представлено простое изложение статьи Хертли о PPSZ. Кроме того будет показано, что если мы улучшим PPSZ для Unique-k-SAT, то из этого получится улучшение для обычного k-SAT (но с худшими параметрами).