Workshop on Algorithms, Complexity and Logic (“Theorietag”)
There will be a workshop on Algorithms, Complexity and Logic (‘Theorietag’) immediately before the STACS conference. The 87th Theorietag will take place as a combined workshop of the GI groups Algorithms, Complexity, and Logic on 03-04 March 2025. Anyone is welcome to attend.
Dates and schedule
March 03-04, 2025
The workshop will start Monday noon and end Tuesday noon and will be held at the same venue as the STACS conference. The conference STACS will start on Tuesday at 1:30 pm. For more details, see the schedule.
Invited Speakers
- Heribert Vollmer, Leibniz University Hannover:
The Complexity of Enumerating Satisfying Assignments
We study the algorithmic problem to enumerate all satisfying assignments of a given propositional formula. Well known is that for formula classes with a polynomial-time decision problem, this can be done within the class DelayP, introduced by Johnson, Papadimitriou and Yannakakis in 1988 and regarded since then as a reasonable notion of “efficient” enumeration.
We will present two results:
- We generalize the class DelayP to a hierarchy analogous to the polynomial-time hierarchy of decision problems and show that Enum-SAT is complete in the Sigma_1 level of this hierarchy under some form of enumeration Turing reductions.
- We define a hierarchy of very efficiently enumerable problems within DelayP, based on the Boolean circuit class AC_0, and place the enumeration problems for monotone, IHS, Krom, and affine formulas in lower levels of this hierarchy.
Open remains an exact classification of the problem Enum-Horn-SAT.
- Sebastian Wild, University of Marburg:
Quicksort, Timsort, Powersort - Algorithmic ideas, engineering tricks, and trivia behind CPython’s new sorting algorithm
In 2002, Tim Peters invented Timsort, a clever Mergesort variant, for the CPython reference implementation of the Python programming language. Timsort is both effective in Python and a popular export product: it is used in many languages and frameworks, notably OpenJDK, the Android runtime, and the V8 JavaScript engine. Despite its widespread use, algorithms researchers eventually discovered two flaws in Timsort's underlying algorithm: The first could lead to a stack overflow in CPython and Java; although meanwhile fixed, it exposed conceptual intricacies of the algorithm. The second flaw concerns its performance: the order in which detected sorted segments, the “runs” of the input, are merged, can be 50% more costly than necessary.
Based on ideas from optimal alphabetic trees, our Powersort merge policy finds nearly optimal merging orders with negligible overhead and using a much more transparent rule. Since Python 3.11, it is part of the CPython reference implementation. The talk will describe the involved algorithms assuming no prior familiarity.
Contributed talks
If you are interested to contribute a talk on algorithms, complexity, or logic, please send an email to stacs2025@uni-jena.de by 5 February 2025 containing the following information:
- Speaker and affiliation
- Title
- Abstract
Notifications on acceptance of contributions will be sent by 10 February, 2025.
Registration to the workshop
Registration for the workshop is mandatory and can be done through the registration page.