First Symposium on Structure in Hard Combinatorial Problems

DATE:Thursday, May 16, 2013 – Saturday, May 18, 2013
VENUE:Zemanek seminar room (ground floor), Favoritenstraße 9-11, 1040 Vienna (see below for map)

ORGANIZATION

This symposium is jointly funded by the Wolfgang Pauli Institute and VCLA.

Symposium chairs:
Bart Selman (Cornell University)
Stefan Szeider (Vienna University of Technology)

AIMS AND SCOPE

Many fundamental computational problems that arise in various applications such as planning, scheduling, automated reasoning, or machine learning are theoretically intractable. In spite of their theoretical hardness, heuristic solvers are often able to solve large realistic problem instances surprisingly fast. For instance, the propositional satisfiability problem is NP-complete and it is believed that it cannot be solved in subexponential time. In contrast, today’s satisfiability solvers can handle routinely large real-world instances with hundreds of thousands of variables.

This discrepancy between theoretical hardness and practically solubility is often explained by the presence of a certain “hidden structure” in real-world instances. Apparently, heuristic solvers are able to exploit this hidden structure to solve the instances efficiently.

There are various approaches for identifying and studying hidden structure: among others, structure has been defined in terms of decomposability, in terms of the distance from some class of instances (backdoors), by measures that capture the small world phenomenon, or by proof complexity measures like resolution width or space. Some of these approaches are rigorous and theoretical, some are empirical. Some approaches give rise to qualitative notions of problem hardness or problem easiness.

The aim of this symposium is to bring together researchers from various disciplines who are concerned with hidden structure in problem instances. Lectures and discussions will put all these different approaches into context and will stimulate a fruitful exchange of ideas between different fields.

FORMAT

The symposium will feature invited talks and provide opportunities for all participants to engage in discussions on open problems and future directions.

Participation is by invitation only. Registration is free of charge and includes attendance to all symposium events and lectures, coffee breaks, and lunches.

The invited talks will be open to the public. Local people who are interested in some of the talks but do not want to participate in the entire symposium (and the social program) do not need to register.

INVITED SPEAKERS

Albert Atserias (Universitat Politècnica de Catalunya)
Armin Biere (Johannes Kepler University, Linz)
Rina Dechter (University of California, Irvine)
Serge Gaspers (NICTA and University of New South Wales, Sydney)
Georg Gottlob (Oxford University)
Holger Hoos (University of British Columbia)
Pete Jeavons (Oxford University)
Rolf Niedermeier (TU Berlin)
Jakob Nordström (KTH Royal Institute of Technology)
Jan Arne Telle (University of Bergen)
Toby Walsh (NICTA and University of New South Wales, Sydney)
Ryan Williams (Stanford)

DATE AND VENUE

May 16-18, 2013
Vienna University of Technology

Zemanek seminar room (location on ground floor)

Favoritenstraße 9-11 (Google Maps)
1040 Vienna, Austria

CO-LOCATED EVENT

Prof. Donald E. Knuth (Stanford) will give a lecture at the Vienna University of Technology on May 16th. Please follow this link for more information.

SCHEDULE

May 16th:

08:30-09:00 Registration
09:00-09:05 Welcome

09:05-10:05  Rolf Niedermeier
10:05-10:30  Coffee break
10:30-11:30   Ryan Williams
11:30-12:30   Serge Gaspers
12:30-14:00  Lunch break  (TU Mensa at Wiedner Hauptstraße 8-10, 1040 Vienna, vouchers will be available)
14:00-15:00  Toby Walsh
15:00-16:00  Holger Hoos
16:00-16:30  Coffee break

17:30 Prof. Knuth’s lecture (more information)

May 17th:

09:00 -10:00 Jakob Nordström
10:00-10:30  Coffee break
10:30-11:30   Albert Atserias
11:30-12:30    Pete Jeavons
12:30-14:00   Lunch break (Vouchers will be available for TU Mensa at Wiedner Hauptstraße 8-10, 1040 Vienna)
14:00-15:00   Georg Gottlob
15:00-16:00   Jan Arne Telle

18:30 Bus departure for restaurant Heuriger Werner Welser (click here for location)  from Favoritenstraße 12 (in front of Hotel Johann Strauß, directly opposite our computer science building)
19:00-21:30 Dinner
21:30 Bus departs for Favoritenstraße 12, 1040 Vienna

It is of course possible to take the public transport to our restaurant, so you will not depend on our rented bus.

May 18th:

09:30-10:30 Rina Dechter
10:30-11:30  Armin Biere

12:30 end of symposium, joint lunch (Restaurant Ischia, Mozartplatz 1, 1040 Vienna) until ~13:30

TALKS

  • Albert Atserias: On the Proof-Search Problem for Resolution [abstract]

  • Armin Biere: Simulating Structual Reasoning on the CNF-Level [abstract] [slides]

  • Rina Dechter: Weighted ­­­AND/OR Multivalued Decision Diagrams (AOMDD) and the Semantic-Width [abstract] [slides]

  • Serge Gaspers: Backdoors to Satisfaction: Parameterized Complexity [abstract] [slides]

  • Georg Gottlob: Robust Constraint Satisfaction and Local Hidden Variables in Quantum Mechanics [abstract]

  • Holger Hoos: Structure at the meta-level: Observations on the structure of design spaces of high-performance solvers for hard combinatorial problems [abstract] [slides]

  • Pete Jeavons: Structure in CSP and SAT: A case study [abstract] [slides]

  • Rolf Niedermeier: On Multivariate Algorithmics and Structure Detection [abstract] [slides]

  • Jakob Nordström: Relating Proof Complexity Measures and Practical Hardness of SAT [abstract] [slides]

  • Jan Arne Telle: Dynamic programming on dense graphs [abstract]

  • Toby Walsh: Detecting and Exploiting Subproblem Tractability / Global Scheduling Constraints under Structural Restrictions [abstract] [slides: scheduling] [slides: subproblem]

  • Ryan Williams: Substructure in SAT [abstract] [slides]

PARTICIPANTS

  • Sebastian Arming (Vienna University of Technology)
  • Albert Atserias (Universiat Politècnica de Catalunya)
  • Adrian Balint (Ulm University)
  • Armin Biere (Johannes Kepler University Linz)
  • Simone Bova (Vienna University of Technology)
  • Ronald de Haan (Vienna University of Technology)
  • Rina Dechter (University of California, Irvine)
  • Wolfgang Dvorák (University of Vienna)
  • Johannes Fichte (Vienna University of Technology)
  • Robert Ganian (Vienna University of Technology)
  • Serge Gaspers (NICTA, U. of NS-Wales, Sydney)
  • Georg Gottlob (Oxford University)
  • Monika Henzinger (Universitaet Wien)
  • Petr Hlinený (FI MU Brno)
  • Holger Hoos (University of British Columbia)
  • Markus Iser (Institute for Theoretical Informatics @KIT)
  • Matti Järvisalo (University of Helsinki)
  • Pete Jeavons (Oxford University)
  • EunJung Kim (LAMSADE-Paris Dauphine)
  • Donald Knuth (Stanford University)
  • Mikko Koivisto (University of Helsinki)
  • Martin Kronegger (Vienna University of Technology)
  • O-joung Kwon (KAIST)
  • Martin Lackner (Vienna University of Technology)
  • Norbert Manthey (TU Dresden)
  • Moritz Müller (Kurt Gödel Research Center, Wien)
  • Nysret Musliu (Vienna University of Technology)
  • Rolf Niedermeier (TU Berlin)
  • Jakob Nordström (KTH Royal Institute of Technology)
  • Sebastian Ordyniak (Vienna University of Technology)
  • Sang-il Oum (KAIST)
  • Daniel Paulusma (Durham University)
  • Justyna Petke (University College London)
  • Andreas Pfandler (Vienna University of Technology)
  • Stefan Rümmele (TU Wien)
  • Abdallah Saffidine (Lamsade, Université Paris-Dauphine)
  • Bart Selman (Cornell University)
  • Carsten Sinz (Karlsruhe Institute of Technology)
  • Friedrich Slivovsky (Vienna University of Technology)
  • Stefan Szeider (Vienna University of Technology)
  • Jan Arne Telle (University of Bergen)
  • Toby Walsh (NICTA, U. of NS-Wales, Sydney)
  • Ryan Williams (Stanford)
  • Stefan Woltran (Vienna University of Technology)
  • Florian Zuleger (Vienna University of Technology)

PHOTOS

[nggallery id=7]

TRAVEL INFORMATION

Here are some suggestions for hotels close to the symposium venue:

Clima Cityhotel (www.climacity-hotel.com)

15 rooms available for special price (see below), book until 15.3.2013 via phone, fax or e-mail with the heading “Structure Workshop” (credit card number and expiration date needed for confirmation)

Single room: EUR 70 per night

Double room: EUR 80 per night

Phone: 0043 1 5051693

Fax: 0043 1 5043552

Email: moc.letoh-yticamilcnull@gnureivreser

Contact person: Ms Karina Gryska

Cancellation policy:

up to 8 weeks before arrival: no costs

up to 4 weeks before arrival: 60% of total room price

less than 4 weeks or no-show: 100% of total room price

 

Hotel Carlton Opera (www.carlton.at)

15 rooms available for special price (see below), book until 15.3.2013 via phone or e-mail with the heading “Structure Workshop” (credit card number and expiration date needed for confirmation)

Price EUR 79 per night

Phone: 0043 1 5875302

Email: ta.notlracnull@letoh

Contact person: Ms Doris Ferenczy

Cancellations: no costs until 1 day before arrival

 

Hotel Erzherzog Rainer (www.schick-hotels.com)

17 rooms available for special price (see below), book until 15.3.2013 via phone, fax or e-mail with the heading “Structure Workshop” (credit card number and expiration date needed for confirmation)

6 single rooms economy: EUR 89 per night

6 single rooms comfort: EUR 108 per night

5 double rooms: EUR 154 per night ( for single use: EUR 125 per night)

Phone: 0043 1 22111 316
Fax: 0043 1 22111 350
Email: moc.sletoh-kcihcsnull@reniar

Contact person: Ms Maria Leitgeb

Cancellation: no costs until 2 days before arrival

 

Hotel Europa (www.austria-trend.at)

40 rooms available, book until 30.4.2013, via phone, fax or e-mail with the heading “Structure Workshop” (credit card number and expiration date needed for confirmation)

Price: EUR 160 per night

Phone: 0043 1 5157788
Fax: 0043 1 5157782
Email: ta.dnert-airtsuanull@neiw.aporue.gnureivreser

Contact person: Ms Neriza Panek

Cancellations:
until21 before arrival: no costs
until 14 days before arrival: 50% of complete stay
until 7 days before arrival: 80% of complete stay
less than 7 days before arrival or no-show: 100% of complete stay

Hotel Astoria (www.austria-trend.at)

20 rooms available, book until 30.4.2013 via phone, fax or e-mail with the heading “Structure Workshop” (credit card number and expiration date needed for confirmation)

Price: EUR 170 per night

Phone: 0043 1 5157788
Fax: 0043 1 5157782
Email: ta.dnert-airtsuanull@airotsa.gnureivreser

Contact person: Frau Neriza Panek

Cancellations:
until21 before arrival: no costs
until 14 days before arrival: 50% of complete stay
until 7 days before arrival: 80% of complete stay
less than 7 days before arrival or no-show: 100% of complete stay

Wombats City Hostel (http://www.wombats-hostels.com)

If you are on a tight budget you might want to consider the following option:

Recently opened a city hostel Wombats, very close to the workshop venue. They offer double rooms for EUR 32, rooms shared by several people are even much cheaper. Please make sure to select “THE NASCHMARKT” as other branches of the hostel are located further away. We could not reserve rooms at the hostel, but if you book early, there should be rooms available.

For further information, please have a look at our visitors’ guide.

Comments are closed.