Symposium on New Frontiers in Knowledge Compilation

ORGANIZATION

This symposium is supported by  VCLA and the Wolfgang Pauli Institute.

Symposium chairs:

Pierre Marquis (CRIL-CNRS/Université d’Artois, France)
Stefan Szeider (TU Wien, Austria)

AIMS AND SCOPE

Many reasoning problems in artificial intelligence and automated deduction are computationally intractable in general. Various approaches have been devised to deal with this complexity by exploiting additional conditions that are satisfied in the domain of application at hand. One example involves the case where many instances share a common part, which can be preprocessed once for many instances. Knowledge compilation is devoted to understanding the potential and the limits of preprocessing in computational models and concrete applications.

In typical reasoning scenarios (for instance, automated configuration) many instances share a common background knowledge that is not very often subject to change. This “constant” piece of information can be compiled into a format that allows for more efficient reasoning, once the “varying” part of the instances becomes available. The time needed to compile the background knowledge together with the cumulative time needed to solve a sequence of instances with the compiled background knowledge can be lower (sometimes by orders of magnitude) than the cumulative time needed to solve the sequence of instances with the non-compiled background knowledge. Consequently, sometimes a relatively expensive compilation process may be worthwhile if its results are amortized by repeated use of the compiled knowledge.

Pioneered more than two decades ago, knowledge compilation is now a very active field of research. The aim of this symposium is to bring together researchers who work on knowledge compilation from various angles, including knowledge representation, constraints, theory of algorithms, complexity, machine learning, and databases, as well as researchers from related areas. Lectures and discussions will put all these different approaches into context and will stimulate a fruitful exchange of ideas between researchers from different fields.

kc-logo

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

  • Simone Bova (TU Wien, Austria)
  • Guy Van den Broeck (University of California Los Angeles, USA)
  • Hubie Chen (Universidad del País Vasco and Ikerbasque, Spain)
  • Adnan Darwiche (University of California Los Angeles, USA)
  • Hélène Fargier (IRIT-CNRS, Université Paul Sabatier, France)
  • Frédéric Koriche (CRIL-CNRS, Université d’Artois, France)
  • Stefan Kratsch (Universität Bonn, Gemany)
  • João Marques-Silva  (IST/INESC-ID, Portugal and University College Dublin, Ireland)
  • Igor Razgon (Birkbeck University of London, UK)
  • Dan Suciu (University of Washington, USA)

DATE AND VENUE

June 4-6, 2015
Vienna University of Technology

Zemanek seminar room (location on ground floor)

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

SCHEDULE

June 4th:

10:20-11:10 Adnan Darwiche: Knowledge Compilation and Machine Learning: A New Frontier.
11:10-12:00 Frédéric Koriche: Affine Decision Trees.
12:00-13:00 Lunch break (sandwiches)
13:00-13:50 Hubie Chen: Parameter Compilation.
13:50-14:15 Ronald de Haan: Parameterized Compilability.
14:15-14:40 Umut Oztok: Exhaustive DPLL for Model Counting and Knowledge Compilation.
14:40-15:05 Friedrich Slivovsky: On Compiling CNFs into Structured Deterministic DNNFs.
15:05-15:35 Coffee break
15:35-16:25 Hélène Fargier: A KC Map of Valued Decision Diagrams – application to product configuration.
16:25-16:50 Alexandre Niveau: Towards a knowledge compilation map for heterogeneous representation languages
16:50-17:10 Adnan Darwiche: Beyond NP: Keeping up with solvers that reach beyond NP!

June 5th:

9:30-10:20 João Marques-Silva: Prime Compilation of Non-Clausal Formulae.
10:20-10:45 Laurent Simon: SAT and Knowledge Compilation: a Just-in-Time Approach.
10:45-11:15 Coffee break
11:15-11:40 Ondrej Cepek: Complexity aspects of CNF to CNF compilation. 
11:40-12:05 Oliver Kullmann: A measured approach towards “good representations”.
12:05-13:30 Lunch break (in the garden if the weather is good, otherwise in Seminar room 388 on first floor)
13:30-14:20 Igor Razgon: On the relationship between Non-deterministic read-once branching programs and DNNFs.
14:20-15:10 Simone Bova:  A Strongly Exponential Separation of DNNFs from CNFs.
18:30 Bus departure for restaurant from Favoritenstraße 12 (in front of Hotel Johann Strauß, directly opposite our computer science building)
19:00-22:00 Dinner at Heuriger Werner Welser (Probusgasse 12, 1190 Vienna)
22:00 Bus departs for Favoritenstraße 12, 1040 Vienna

June 6th:

9:15-10:05 Stefan Kratsch: Kernelization: Efficient Preprocessing for NP-hard Problems.
10:05-10:30 Dan Olteanu: Factorized Databases.
10:30-10:45 Short break
10:45-11:35 Guy Van den Broeck: First-Order Knowledge Compilation for Probabilistic Reasoning. 
11:35-12:25 Dan Suciu: Query Compilation: the View from the Database Side.
12:30 end of symposium, joint lunch (Restaurant Ischia, Mozartplatz 1, 1040 Vienna) until ~13:30

TALKS

  • Simone Bova: A Strongly Exponential Separation of DNNFs from CNFs.  [abstract] [slides]
  • Guy Van den Broeck: First-Order Knowledge Compilation for Probabilistic Reasoning. [abstract] [slides]
  • Ondrej Cepek: Complexity aspects of CNF to CNF compilation.  [abstract] [slides]
  • Hubie Chen: Parameter Compilation. [abstract] [slides]
  • Adnan DarwicheKnowledge Compilation and Machine Learning: A New Frontier.  [abstract] [slides]
  • Adnan Darwiche: Beyond NP: Keeping up with solvers that reach beyond NP! [abstract]
  • Hélène Fargier: A KC Map of Valued Decision Diagrams – application to product configuration.  [abstract] [slides]
  • Ronald de Haan: Parameterized Compilability. [abstract] [slides]
  • Frédéric Koriche: Affine Decision Trees. [abstract]
  • Stefan Kratsch: Kernelization: Efficient Preprocessing for NP-hard Problems. [abstract]
  • Oliver Kullmann: A measured approach towards “good representations”. [abstract] [slides]
  • João Marques-Silva: Prime Compilation of Non-Clausal Formulae. [abstract] [slides]
  • Alexandre Niveau: Towards a knowledge compilation map for heterogeneous representation languages.  [abstract] [slides]
  • Dan Olteanu: Factorized Databases. [abstract]
  • Umut Oztok: Exhaustive DPLL for Model Counting and Knowledge Compilation. [abstract] [slides]
  • Igor Razgon: On the relationship between Non-deterministic read-once branching programs and DNNFs. [abstract] [slides]
  • Laurent Simon: SAT and Knowledge Compilation: a Just-in-Time Approach. [abstract]
  • Friedrich Slivovsky: On Compiling CNFs into Structured Deterministic DNNFs. [abstract] [slides]
  • Dan Suciu: Query Compilation: the View from the Database Side. [abstract] [slides]

PARTICIPANTS

Gilles Audemard
Simone Bova
Guy van den Broeck
Florent Capelli
Ondrej Cepek
Hubie Chen
Jessica Davies
Adnan Darwiche
Eduard Eiben
Hélène Fargier
Johannes Fichte
Ronald de Haan
Frédéric Koriche
Stefan Kratsch
Oliver Kullmann
Jean-Marie Lagniez
Neha Lodha
Joao Marques-Silva
Pierre Marquis
Stefan Mengel
Alexandre Niveau
Jakob Nordström
Dan Olteanu
Sebastian Ordyniak
Umut Oztok
Igor Razgon
Marco Schaerf
Laurent Simon
Friedrich Slivovsky
Zeynep Saribatur
Dan Suciu
Stefan Szeider

PHOTOS

TRAVEL INFORMATION

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

Clima Cityhotel (www.climacity-hotel.com)

Hotel Carlton Opera (www.carlton.at)

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

Hotel Europa (www.austria-trend.at)

Hotel Astoria (www.austria-trend.at)

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

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