How to Reduce Temporal Cliques to Find Sparse Spanners
Many real-world networks, such as transportation or trade networks, are dynamic in the sense that the edge set may change over time, but these changes are known in advance. This behavior is...
Schelling Games with Continuous Types
In most major cities and urban areas, residents form homogeneous neighborhoods along ethnic or socioeconomic lines. This phenomenon is widely known as residential segregation and has been studied...
On the work of dynamic constant-time parallel algorithms for regular tree languages and context-free languages
Previous work on Dynamic Complexity has established that there exist dynamic constant-time parallel algorithms for regular tree languages and context-free languages under label or symbol changes....
Towards Explainable Real Estate Valuation via Evolutionary Algorithms
Human lives are increasingly influenced by algorithms, which therefore need to meet higher standards not only in accuracy but also with respect to explainability. This is especially true for...
Iltis: Learning Logic in the Web
The Iltis project provides an interactive, web-based system for teaching the foundations of formal methods. It is designed with the objective to allow for simple inclusion of new educational...
Introduction to Iltis: An Interactive, Web-Based System for Teaching Logic
Logic is a foundation for many modern areas of computer science. In artificial intelligence, as a basis of database query languages, as well as in formal software and hardware verification ---...
Dynamic Complexity Meets Parameterised Algorithms
Dynamic Complexity studies the maintainability of queries with logical formulas in a setting where the underlying structure or database changes over time. Most often, these formulas are from...
Near-Linear Time Maximum Clique in Circular Arc Graphs
We present a near-linear time algorithm to find a maximum clique in circular arc graphs, the intersection graphs of arcs on the circumference of a circle, answering a 30-year-old open question...
Preprocessed 3SUM: From Reals to Integers
The Preprocessed 3SUM problem asks to preprocess a set $A$ of $n$ numbers so that we can quickly decide whether a query subset $A' \subseteq A$ contains a solution $a+b=c$. The best known query...
A Simple Algorithm for Counting Solutions to Integer Programs
We consider the problem of counting solutions to integer linear programming problems of the form $\{x \in \mathbb{Z}^n_{\geq 0} : Ax = b\}$ where $A \in \{-\Delta,\ldots,\Delta\}^{m \times n}$ and...
3SUM Is Really Hard: A Real-to-Integer Reduction
We show that if the 3SUM problem on integer-valued inputs can be solved in truly subquadratic time, then it can also be solved in truly subquadratic time on real-valued inputs. This answers an...