Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Seminar SAT

Seminar SAT (2015)

Instructor: Emo Welzl

Contact: Chidambaram Annamalai

Language: English (If a student is reluctant to do a presentation in English, we will not enforce it and have a German talk for an exception)

Time and Place: Friday, 10-12, CAB G 57

Prerequisites: Attendance of the course on Satisfiability of Boolean Formulas - Combinatorics and Algorithms (or a comparable course) is recommended.

Goal: To explore, understand and present recent lower bound implications following from the exponential hardness hypothesis of SAT.

Conditions: Talk duration is 45 minutes. A successful participation in the seminar requires the following:

  1. a rehearsal talk, to be given in front of your supervisor at least one week prior to the plenary talk;
  2. a satisfactory plenary talk;
  3. attendance at all other talks.
Additional material:

Important Note:

Proposed Papers:

The papers will be assigned at the first meeting on Friday, September 25.

The list of proposed papers is tentative and might change.

  1. Allan Grønlund, Seth Pettie: Threesomes, Degenerates, and Love Triangles
  2. Mihai Pătraşcu, Ryan Williams: On the possibility of faster algorithms for SAT
  3. Karl Bringmann: Why walking the dog takes time or Frechet distance has no strongly subquadratic algorithms unless SETH fails
  4. Arturs Backurs, Piotr Indyk: Edit distance cannot be computed in strongly subquadratic time
  5. Karl Bringmann, Marvin Künnerman: Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping
    see also: Amir Abboud, Arturs Backurs, Virginia Williams: Quadratic-Time hardness of LCS and other sequence similarity measures.
  6. Amir Abboud, Virginia Williams, Huacheng Yu: Matching triangles and basing hardness on an extremely popular conjecture
  7. Amir Abboud, Arturs Backurs, Thomas Dueholm Hansen, Virginia Williams, Or Zamir: Subtree Isomorphism Revisited (preprint will be made available to attendees)