Universität Tübingen Fakultät > Wilhelm-Schickard-Institut > Algorithmik > Forschung > Workshop on SAT
Arbeitsbereich Algorithmik
Boolean formula in cnf written in DIMACS format

Workshop on SAT Solving

24.02.2011 - 25.02.2011

The Satisfiability problem (SAT) is a very famous problem in computer science. On the one hand the NP-completeness of SAT is often used to prove the complexity of other computer theoretical problems. On the other hand SAT is known to be tractable for some kinds of SAT problems stemming from real world applications. Both, researchers and users besides academics steadily increase the number of applications for SAT solving.

Aim of this workshop

This workshop aims at bringing together researchers that work at different areas of computer science. The areas may be more or less related to SAT. The workshop will be organized as an Open-Problem workshop. So the schedule will reserve the most time for working together in small teams. However, there will also be some talks.
All participants should provide an open problem somehow related (closer or further) to SAT. Some ideas for topics and open problems may include but are not limited to:
  • Transforming problems from your research area to SAT
  • Practical applications of SAT solving
  • Alternative SAT solving approaches
  • Theoretical analysis of SAT
  • Problem encodings - SAT, Pseudo Boolean, CP
  • Problem specific simplification

Important Dates

The group should not be larger than 20 people to make the workshop efficient.
  • Deadline for registration : 15.12.2010 Please contact Stephan Kottler. There is no registration fee for the workshop.
  • Open problem proposals: 16.02.2011
  • Workshop: 24.02.2011, 10:00 h - 25.02.2011, 16:30 h
  • Dinner: 24.02.2011, 19h


The workshop is organized within the DFG-Schwerpunktprogramm 1307 - Algorithm Engineering. People within this SPP are kindly invited to join the workshop.
We are very pleased to welcome Daniel Le Berre as an invited speaker in Tübingen.


  • Hotel Garni is just a few meters walking distance to the computer science building. It offers free WLAN access and can be booked including or excluding breakfast. Use "SAT 11" as subject to get one of the rooms we have already reserved (allows you to book a double bed room as single bed room).
  • Hotel Meteora is about 1,5 km away from the computer science building. Breakfast is always included.

Travel to Tübingen

We assume that most people arrive by train in Tübingen. From the main station you have to take Tü-Bus 2 direction WHO Ulmenweg and exit at Sand Drosselweg. The bus operates every 15 minutes.

If you plan to to travel by car you find the computer science building at Sand 14, 72076 Tübingen.


Thursday 24.02.2011
10:00 - 12:30 Introduction and presentation in Room A104 at Sand 14 .
12:30 - 14:00 Lunch at Mensa Morgenstelle. Travel is organised.
14:00 - 15:00 Invited Talk of Daniel Le Berre.
15:00 - 16:00 Working on problems.
16:00 - 16:15 Coffee break. Time is not really fixed but just to ensure there is one!
16:15 - 17:30 Working on problems.
17:30 - 18:00 Informal presentation of some ideas (and may be results) of each group.
19:00 Dinner and social event at Ratskeller Tübingen.

Friday 25.02.2011
9:00 - 10:30 Static Restart in Room A104
10:30 - 11:00 Coffee break.
11:00 - 12:30 Working on problems.
12:30 - 14:00 Lunch at the restaurant Flavours of India.
14:00 - 15:15 Working on problems.
15:15 - 15:30 Coffee break.
15:30 - 16:30 Informal presentation and discussion of the work of each group.


We thank Daniel Le Berre for a very interesting and appealing invited talk.
The Slides of his talk are available for download .
Anregungen / Kritik Impressum minicms