### The Heaviest Induced Ancestors Problem Revisited

Paniz Abedin, Sahar Hooshmand, Arnab Ganguly & Sharma V. Thankachan
We revisit the heaviest induced ancestors problem, which has several interesting applications in string matching. Let T_1 and T_2 be two weighted trees, where the weight W(u) of a node u in either of the two trees is more than the weight of u's parent. Additionally, the leaves in both trees are labeled and the labeling of the leaves in T_2 is a permutation of those in T_1. A node x in T_1 and a...

### The Power of Natural Properties as Oracles

Russell Impagliazzo, Valentine Kabanets & Ilya Volkovich
We study the power of randomized complexity classes that are given oracle access to a natural property of Razborov and Rudich (JCSS, 1997) or its special case, the Minimal Circuit Size Problem (MCSP). We show that in a number of complexity-theoretic results that use the SAT oracle, one can use the MCSP oracle instead. For example, we show that ZPEXP^{MCSP} !subseteq P/poly, which should be contrasted with the previously known circuit lower bound ZPEXP^{NP} !subseteq...

### Formal Executable Models for Automatic Detection of Timing Anomalies

Mihail Asavoae, Belgacem Ben Hedia & Mathieu Jan
A timing anomaly is a counterintuitive timing behavior in the sense that a local fast execution slows down an overall global execution. The presence of such behaviors is inconvenient for the WCET analysis which requires, via abstractions, a certain monotony property to compute safe bounds. In this paper we explore how to systematically execute a previously proposed formal definition of timing anomalies. We ground our work on formal designs of architecture models upon which we...

### Whole-System WCEC Analysis for Energy-Constrained Real-Time Systems (Artifact)

Peter Wägemann, Christian Dietrich, Tobias Distler, Peter Ulbrich & Wolfgang Schröder-Preikschat
Although internal devices (e.g., memory, timers) and external devices (e.g., sensors, transceivers) significantly contribute to the energy consumption of an embedded real-time system, their impact on the worst-case response energy consumption (WCRE) of tasks is usually not adequately taken into account. Most WCRE analysis techniques only focus on the processor and neglect the energy consumption of other hardware units that are temporarily activated and deactivated in the system. To solve the problem of system-wide energy-consumption...

### Consistency for Counting Quantifiers

Florent R. Madelaine & Barnaby Martin
We apply the algebraic approach for Constraint Satisfaction Problems (CSPs) with counting quantifiers, developed by Bulatov and Hedayaty, for the first time to obtain classifications for computational complexity. We develop the consistency approach for expanding polymorphisms to deduce that, if H has an expanding majority polymorphism, then the corresponding CSP with counting quantifiers is tractable. We elaborate some applications of our result, in particular deriving a complexity classification for partially reflexive graphs endowed with all...

### Dagstuhl Reports, Table of Contents, Volume 7, Issue 3, 2017

Marc Herbstritt
Table of Contents, Frontmatter

### Towards Static Performance Guarantees for Programs with Run-Time Checks

Maximiliano Klemen, Nataliia Stulova, Pedro Lopez-Garcia, José F. Morales & Manuel V. Hermenegildo
This document is an extended abstract of the Technical Report CLIP-1/2018.0.

### Assessing Neighborhood Conditions using Geographic Object-Based Image Analysis and Spatial Analysis (Short Paper)

Chi-Feng Yen, Ming-Hsiang Tsou & Chris Allen
Traditionally, understanding urban neighborhood conditions heavily relies on time-consuming and labor-intensive surveying. As the growing development of computer vision and GIScience technology, neighborhood conditions assessment can be more cost-effective and time-efficient. This study utilized Google Earth Engine (GEE) to acquire 1m aerial imagery from the National Agriculture Image Program (NAIP). The features within two main categories: (i) aesthetics and (ii) street morphology that have been selected to reflect neighborhood socio-economic (SE) and demographic (DG) conditions...

### Deletion in Abstract Voronoi Diagrams in Expected Linear Time

Kolja Junginger & Evanthia Papadopoulou
Updating an abstract Voronoi diagram in linear time, after deletion of one site, has been an open problem for a long time. Similarly for various concrete Voronoi diagrams of generalized sites, other than points. In this paper we present a simple, expected linear-time algorithm to update an abstract Voronoi diagram after deletion. We introduce the concept of a Voronoi-like diagram, a relaxed version of a Voronoi construct that has a structure similar to an abstract...

### Smaller Parameters for Vertex Cover Kernelization

Eva-Maria C. Hols & Stefan Kratsch
We revisit the topic of polynomial kernels for Vertex Cover relative to structural parameters. Our starting point is a recent paper due to Fomin and Strømme [WG 2016] who gave a kernel with O(|X|^{12}) vertices when X is a vertex set such that each connected component of G-X contains at most one cycle, i.e., X is a modulator to a pseudoforest. We strongly generalize this result by using modulators to d-quasi-forests, i.e., graphs where each...

### Oligopolistic Competitive Packet Routing

Britta Peis, Bjoern Tauer, Veerle Timmermans & Laura Vargas Koch
Oligopolistic competitive packet routing games model situations in which traffic is routed in discrete units through a network over time. We study a game-theoretic variant of packet routing, where in contrast to classical packet routing, we are lacking a central authority to decide on an oblivious routing protocol. Instead, selfish acting decision makers ("players") control a certain amount of traffic each, which needs to be sent as fast as possible from a player-specific origin to...

### Optimizing Society? Ensuring Fairness in Automated Decision-Making (Invited Talk)

Sorelle Friedler
Algorithms are increasingly used to make high-stakes decisions about people; who goes to jail, what neighborhoods police deploy to, and who should be hired for a job. But if we want these decisions to be fair, this means we must take societal notions of fairness and express them using the language of math. What is a fair decision and how can it be guaranteed? In this talk, we'll discuss recent work from the new and...

### A Novel Algorithm for the All-Best-Swap-Edge Problem on Tree Spanners

Davide Bilò & Kleitos Papadopoulos
Given a 2-edge connected, unweighted, and undirected graph G with n vertices and m edges, a sigma-tree spanner is a spanning tree T of G in which the ratio between the distance in T of any pair of vertices and the corresponding distance in G is upper bounded by sigma. The minimum value of sigma for which T is a sigma-tree spanner of G is also called the stretch factor of T. We address the...

### Power of d Choices with Simple Tabulation

Anders Aamand, Mathias Bæk Tejs Knudsen & Mikkel Thorup
We consider the classic d-choice paradigm of Azar et al. [STOC'94] in which m balls are put into n bins sequentially as follows: For each ball we are given a choice of d bins chosen according to d hash functions and the ball is placed in the least loaded of these bins, breaking ties arbitrarily. The interest is in the number of balls in the fullest bin after all balls have been placed. In this...

### Extending the Centerpoint Theorem to Multiple Points

Alexander Pilz & Patrick Schnider
The centerpoint theorem is a well-known and widely used result in discrete geometry. It states that for any point set P of n points in R^d, there is a point c, not necessarily from P, such that each halfspace containing c contains at least n/(d+1) points of P. Such a point c is called a centerpoint, and it can be viewed as a generalization of a median to higher dimensions. In other words, a centerpoint...

### Reliable Computation and Complexity on the Reals (Dagstuhl Seminar 17481)

Norbert T. Müller, Siegfried M. Rump, Klaus Weihrauch & Martin Ziegler
Naive computations with real numbers on computers may cause serious errors. In traditional numerical computation these errors are often neglected or, more seriously, not identified. Two approaches attack this problem and investigate its background, Reliable Computing and Computable Analysis. Methods in Reliable Computing are essentially mathematical theorems, the assumptions of which are verified on the computer. This verification is performed using the very efficient floating point arithmetic. If the verification succeeds, the assertions are true...

### Packing Sporadic Real-Time Tasks on Identical Multiprocessor Systems

Jian-Jia Chen, Nikhil Bansal, Samarjit Chakraborty & Georg Von Der Brüggen
In real-time systems, in addition to the functional correctness recurrent tasks must fulfill timing constraints to ensure the correct behavior of the system. Partitioned scheduling is widely used in real-time systems, i.e., the tasks are statically assigned onto processors while ensuring that all timing constraints are met. The decision version of the problem, which is to check whether the deadline constraints of tasks can be satisfied on a given number of identical processors, has been...

### Constrained Polymorphic Types for a Calculus with Name Variables

Davide Ancona, Paola Giannini & Elena Zucca
We extend the simply-typed lambda-calculus with a mechanism for dynamic rebinding of code based on parametric nominal interfaces. That is, we introduce values which represent single fragments, or families of named fragments, of open code, where free variables are associated with names which do not obey \alpha-equivalence. In this way, code fragments can be passed as function arguments and manipulated, through their nominal interface, by operators such as rebinding, overriding and renaming. Moreover, by using...

### Stationary Distribution Analysis of a Queueing Model with Local Choice

Plinio S. Dester, Christine Fricker & Hanene Mohamed
The paper deals with load balancing between one-server queues on a circle by a local choice policy. Each one-server queue has a Poissonian arrival of customers. When a customer arrives at a queue, he joins the least loaded queue between this queue and the next one, ties solved at random. Service times have exponential distribution. The system is stable if the arrival-to-service rate ratio called load is less than one. When the load tends to...

### Learning Qualitative Constraint Networks

Malek Mouhoub, Hamad Al Marri & Eisa Alanazi
Temporal and spatial reasoning is a fundamental task in artificial intelligence and its related areas including scheduling, planning and Geographic Information Systems (GIS). In these applications, we often deal with incomplete and qualitative information. In this regard, the symbolic representation of time and space using Qualitative Constraint Networks (QCNs) is therefore substantial. We propose a new algorithm for learning a QCN from a non expert. The learning process includes different cases where querying the user...

### Computing Exact Minimum Cuts Without Knowing the Graph

Aviad Rubinstein, Tselil Schramm & S. Matthew Weinberg
We give query-efficient algorithms for the global min-cut and the s-t cut problem in unweighted, undirected graphs. Our oracle model is inspired by the submodular function minimization problem: on query S \subset V, the oracle returns the size of the cut between S and V \ S. We provide algorithms computing an exact minimum $s$-$t$ cut in $G$ with ~{O}(n^{5/3}) queries, and computing an exact global minimum cut of G with only ~{O}(n) queries (while...

### Online Facility Location with Deletions

Marek Cygan, Artur Czumaj, Marcin Mucha & Piotr Sankowski
In this paper we study three previously unstudied variants of the online Facility Location problem, considering an intrinsic scenario when the clients and facilities are not only allowed to arrive to the system, but they can also depart at any moment. We begin with the study of a natural fully-dynamic online uncapacitated model where clients can be both added and removed. When a client arrives, then it has to be assigned either to an existing...

### Brief Announcement: Generalising Concurrent Correctness to Weak Memory

Simon Doherty, Brijesh Dongol, Heike Wehrheim & John Derrick
Correctness conditions like linearizability and opacity describe some form of atomicity imposed on concurrent objects. In this paper, we propose a correctness condition (called causal atomicity) for concurrent objects executing in a weak memory model, where the histories of the objects in question are partially ordered. We establish compositionality and abstraction results for causal atomicity and develop an associated refinement-based proof technique.

### Spalter: A Meta Machine Learning Approach to Distinguish True DNA Variants from Sequencing Artefacts

Till Hartmann & Sven Rahmann
Being able to distinguish between true DNA variants and technical sequencing artefacts is a fundamental task in whole genome, exome or targeted gene analysis. Variant calling tools provide diagnostic parameters, such as strand bias or an aggregated overall quality for each called variant, to help users make an informed choice about which variants to accept or discard. Having several such quality indicators poses a problem for the users of variant callers because they need to...

### On-Body Interaction: Embodied Cognition Meets Sensor/Actuator Engineering to Design New Interfaces (Dagstuhl Seminar 18212)

Kasper Hornbaek, David Kirsh, Joseph A. Paradiso & Jürgen Steimle
On-body technologies are emerging as a new paradigm in human-computer interaction. Instead of moving a mouse or tapping a touch surface, people can use whole-body movements to navigate in games, gesture in mid-air to interact with large displays, or touch their forearm to control a mobile phone. First promising applications are being investigated or have been demonstrated in mobile computing, healthcare, or sports. Two areas of research have been contributing to this paradigm. Research on...

• 2018
1,647

• Text
1,625
• Software
22