Skip to content Search
Search our website:

Attacking very hard problems

  • Speaker: Dr Oliver Kullman, Dept of Computer Science, Swansea University
  • Date: Tuesday, 16 May 2017 from 17:00 to 18:00
  • Location: Room 151

In my talk I will outline "theory and practice" of attacking very hard
*concrete* problems in the neighbourhood of NP, via SAT solving and
other related tools, exploiting massive computations.

On the problem side, I will focus on problems from Ramsey theory, where
on the one hand a rich theory is available, and where, perhaps
surprisingly, on the other hand the problems show some strong similarities to
real-world problems.

Concerning algorithms, I will outline the Cube-and-Conquer paradigm, a
hybrid scheme for SAT solving. This will prompt the need for a "hybrid"
complexity theory, employing oracles, and leveraging the advantages of
trees *and* dags.