[Proof Complexity] MIAO seminar Fri Apr 26 at 14:00 CEST with Markus Hecher: A crash course in answer-set programming

[Jakob Nordström]

Dear all,

On Friday April 26 at 14:00 CEST we will have the pleasure of listening to a seminar with Markus Hecher from MIT, who will give a talk titled "A crash course in answer-set programming". You find the abstract at the bottom of this message.

We will run this as a hybrid seminar at Lund University. Local participants are warmly welcome to seminar room E:2116 at Ole Römers väg 3. Other participants are equally warmly welcome to join virtually at https://lu-se.zoom.us/j/61925271827 . Please feel free to share this information with colleagues who you think might be interested. We are also hoping to record the seminar and post on the MIAO Research YouTube channel https://youtube.com/@MIAOresearch for people who would like to hear the talk but cannot attend.

Most of our seminars consist of two parts: first a 50-55-minute regular talk, and then after a break a ca-1-hour in-depth technical presentation with (hopefully) a lot of interaction. The intention is that the first part of the seminar will give all listeners a self-contained overview of some exciting research results, and after the break people who have the time and interest will get an opportunity to really get into the technical details. (However, for those who feel that the first part was enough, it is perfectly fine to just discretely drop out during the break. No questions asked; no excuses needed.)

More information about upcoming MIAO seminars can be found at https://jakobnordstrom.se/miao-seminars/. In particular, note that this week we also have a seminar tomorrow Tuesday April 23 with Daniel Neuen titled "Compressing CFI graphs and lower bounds for Weisfeiler-Leman refinements" and another seminar on Thursday April 25 with Mathias Fleury titled "Verifying a SAT solver from ground up". If you do not wish to receive these announcements, or receive several copies of them, please send a message to jn at di.ku.dk.

Best regards,
Jakob Nordström

**********

Friday Apr 26 at 14:00 in seminar room E:2116, Ole Römers väg 3, Lund University, and on Zoom
A crash course in answer-set programming
(Markus Hecher, MIT)

In this talk we briefly showcase the answer set programming (ASP) framework and demonstrate some use cases for rapid prototyping. After introducing basic notation and extended syntactic sugar, we will discuss the computational complexity of different fragments of interest. In the propositional (ground) case, ASP reaches up to the second level of the polynomial hierarchy (third level for optimization). Since ASP enables the use of first-order like variables, there are also fragments reaching beyond NEXPTIME. In practice, this results in the so-called ASP grounding bottleneck, as practical systems typically comprise two phases: During grounding, first-order like variables are instantiated with every potential domain value, which is then followed by a (ground) solving phase. However, if predicate arities are bounded (practically well-motivated), compared to the ground case, complexity only increases by one level in the polynomial hierarchy. Based on these complexity results, we will briefly discuss recent works that propose alternative grounding techniques by reducing from simpler non-ground fragments to harder ground fragments.


Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +45 28 78 38 11 / +46 70 742 21 98
https://jakobnordstrom.se