### The Complexity of Quantified Constraints Using the Algebraic Formulation

Catarina Carvalho, Barnaby Martin & Dmitriy Zhuk
Let A be an idempotent algebra on a finite domain. We combine results of Chen, Zhuk and Carvalho et al. to argue that if A satisfies the polynomially generated powers property (PGP), then QCSP(Inv(A)) is in NP. We then use the result of Zhuk to prove a converse, that if Inv(A) satisfies the exponentially generated powers property (EGP), then QCSP(Inv(A)) is co-NP-hard. Since Zhuk proved that only PGP and EGP are possible, we derive a...

### Vision for Autonomous Vehicles and Probes (Dagstuhl Seminar 15461)

André Bruhn, Atsushi Imiya, Ales Leonardis & Tomas Pajdla
The vision-based autonomous driving and navigation of vehicles has a long history. In 2013, Daimler succeeded autonomous driving on a public drive way. Today, the Curiosity mars rover is sending video views from Mars to Earth. Computer vision plays a key role in advanced driver assistance systems (ADAS) as well as in exploratory and service robotics. Continuing topics of interest in computer vision are scene and environmental understanding using single- and multiple-camera systems, which are...

### All Fingers Are Not the Same: Handling Variable-Length Sequences in a Discriminative Setting Using Conformal Multi-Instance Kernels

Sarvesh Nikumbh, Peter Ebert & Nico Pfeifer
Most string kernels for comparison of genomic sequences are generally tied to using (absolute) positional information of the features in the individual sequences. This poses limitations when comparing variable-length sequences using such string kernels. For example, profiling chromatin interactions by 3C-based experiments results in variable-length genomic sequences (restriction fragments). Here, exact position-wise occurrence of signals in sequences may not be as important as in the scenario of analysis of the promoter sequences, that typically have...

### Track Allocation in Freight-Train Classification with Mixed Tracks

Markus Bohlin, Holger Flier, Jens Maue & Matús Mihalák
We consider the process of forming outbound trains from cars of inbound trains at rail-freight hump yards. Given the arrival and departure times as well as the composition of the trains, we study the problem of allocating classification tracks to outbound trains such that every outbound train can be built on a separate classification track. We observe that the core problem can be formulated as a special list coloring problem in interval graphs, which is...

Piotr Sankowski & Christos Zaroliagis

### Web Application Security (Dagstuhl Seminar 18321)

Martin Johns, Nick Nikiforakis, Melanie Volkamer & John Wilander
This report documents the program and the outcomes of Dagstuhl Seminar 18321 "Web Application Security". In this third seminar on the topic, a healthy mix of academics, practitioners and representatives of all major browser vendors reflected on the last decade of web security research and discussed the upcoming security challenges for the Web platform. In addition, for the first time, the list of attendees included several members of the human factors in security community, to...

### Improved Algorithms for Adaptive Compressed Sensing

Vasileios Nakos, Xiaofei Shi, David P. Woodruff & Hongyang Zhang
In the problem of adaptive compressed sensing, one wants to estimate an approximately k-sparse vector x in R^n from m linear measurements A_1 x, A_2 x,..., A_m x, where A_i can be chosen based on the outcomes A_1 x,..., A_{i-1} x of previous measurements. The goal is to output a vector x^ for which |x-x^|_p <=C * min_{k-sparse x'} |x-x'|_q, with probability at least 2/3, where C > 0 is an approximation factor. Indyk, Price...

### Representing the Suffix Tree with the CDAWG

Djamal Belazzougui & Fabio Cunial
Given a string T, it is known that its suffix tree can be represented using the compact directed acyclic word graph (CDAWG) with e_T arcs, taking overall O(e_T+e_REV(T)) words of space, where REV(T) is the reverse of T, and supporting some key operations in time between O(1) and O(log(log(n))) in the worst case. This representation is especially appealing for highly repetitive strings, like collections of similar genomes or of version-controlled documents, in which e_T grows...

### Treasure Hunt with Barely Communicating Agents

Stefan Dobrev, Rastislav Královic & Dana Pardubská
We consider the problem of fault-tolerant parallel exhaustive search, a.k.a. “Treasure Hunt”, introduced by Fraigniaud, Korman and Rodeh in [13]: Imagine an infinite list of “boxes”, one of which contains a “treasure”. The ordering of the boxes reflects the importance of finding the treasure in a given box. There are k agents, whose goal is to locate the treasure in the least amount of time. The system is synchronous; at every step, an agent can...

### Playing Safe

Thomas Colcombet, Nathanael Fijalkow & Florian Horn
We consider two-player games over graphs and give tight bounds on the memory size of strategies ensuring safety conditions. More specifically, we show that the minimal number of memory states of a strategy ensuring a safety condition is given by the size of the maximal antichain of left quotients with respect to language inclusion. This result holds for all safety conditions without any regularity assumptions, and for all (finite or infinite) graphs of finite degree....

### Effective Divergence Analysis for Linear Recurrence Sequences

Shaull Almagor, Brynmor Chapman, Mehran Hosseini, Joël Ouaknine & James Worrell
We study the growth behaviour of rational linear recurrence sequences. We show that for low-order sequences, divergence is decidable in polynomial time. We also exhibit a polynomial-time algorithm which takes as input a divergent rational linear recurrence sequence and computes effective fine-grained lower bounds on the growth rate of the sequence.

### Characterisation of an Algebraic Algorithm for Probabilistic Automata

Nathanaël Fijalkow
We consider the value 1 problem for probabilistic automata over finite words: it asks whether a given probabilistic automaton accepts words with probability arbitrarily close to 1. This problem is known to be undecidable. However, different algorithms have been proposed to partially solve it; it has been recently shown that the Markov Monoid algorithm, based on algebra, is the most correct algorithm so far. The first contribution of this paper is to give a characterisation...

### Improved Algorithms for the Shortest Vector Problem and the Closest Vector Problem in the Infinity Norm

Ajtai, Kumar and Sivakumar [Ajtai et al., 2001] gave the first 2^O(n) algorithm for solving the Shortest Vector Problem (SVP) on n-dimensional Euclidean lattices. The algorithm starts with N in 2^O(n) randomly chosen vectors in the lattice and employs a sieving procedure to iteratively obtain shorter vectors in the lattice, and eventually obtaining the shortest non-zero vector. The running time of the sieving procedure is quadratic in N. Subsequent works [Arvind and Joglekar, 2008; Blömer...

### Nominal Presentation of Cubical Sets Models of Type Theory

Andrew M. Pitts
The cubical sets model of Homotopy Type Theory introduced by Bezem, Coquand and Huber uses a particular category of presheaves. We show that this presheaf category is equivalent to a category of sets equipped with an action of a monoid of name substitutions for which a finite support property holds. That category is in turn isomorphic to a category of nominal sets equipped with operations for substituting constants 0 and 1 for names. This formulation...

### The Genus of the Erdös-Rényi Random Graph and the Fragile Genus Property

Chris Dowden, Mihyun Kang & Michael Krivelevich
We investigate the genus g(n,m) of the Erdös-Rényi random graph G(n,m), providing a thorough description of how this relates to the function m=m(n), and finding that there is different behaviour depending on which region' m falls into. Existing results are known for when m is at most n/(2) + O(n^{2/3}) and when m is at least omega (n^{1+1/(j)}) for j in N, and so we focus on intermediate cases. In particular, we show that g(n,m)...

### The complexity of analyzing infinite-state Markov chains, Markov decision processes, and stochastic games (Invited talk)

Kousha Etessami
In recent years, a considerable amount of research has been devoted to understanding the computational complexity of basic analysis problems, and model checking problems, for finitely-presented countable infinite-state probabilistic systems. In particular, we have studied recursive Markov chains (RMCs), recursive Markov decision processes (RMDPs) and recursive stochastic games (RSGs). These arise by adding a natural recursion feature to finite-state Markov chains, MDPs, and stochastic games. RMCs and RMDPs provide natural abstract models of probabilistic procedural...

### Exact Quantum Query Algorithm for Error Detection Code Verification

Alina Vasilieva
Quantum algorithms can be analyzed in a query model to compute Boolean functions. Function input is provided in a black box, and the aim is to compute the function value using as few queries to the black box as possible. A repetition code is an error detection scheme that repeats each bit of the original message r times. After a message with redundant bits is transmitted via a communication channel, it must be verified. If...

### Online Row Sampling

Michael B. Cohen, Cameron Musco & Jakub Pachocki
Finding a small spectral approximation for a tall n x d matrix A is a fundamental numerical primitive. For a number of reasons, one often seeks an approximation whose rows are sampled from those of A. Row sampling improves interpretability, saves space when A is sparse, and preserves row structure, which is especially important, for example, when A represents a graph. However, correctly sampling rows from A can be costly when the matrix is large...

### Is Salience Robust? A Heterogeneity Analysis of Survey Ratings

Markus Kattenbeck, Eva Nuhn & Sabine Timpf
Differing weights for salience subdimensions (e.g. visual or structural salience) have been suggested since the early days of salience models in GIScience. Up until now, however, it remains unclear whether weights found in studies are robust across environments, objects and observers. In this study we examine the robustness of a survey-based salience model. Based on ratings of N_{o}=720 objects by N_{p}=250 different participants collected in-situ in two different European cities (Regensburg and Augsburg) we conduct...

### Commutative Algorithms Approximate the LLL-distribution

Fotis Iliopoulos
Following the groundbreaking Moser-Tardos algorithm for the Lovász Local Lemma (LLL), a series of works have exploited a key ingredient of the original analysis, the witness tree lemma, in order to: derive deterministic, parallel and distributed algorithms for the LLL, to estimate the entropy of the output distribution, to partially avoid bad events, to deal with super-polynomially many bad events, and even to devise new algorithmic frameworks. Meanwhile, a parallel line of work has established...

### Distance Labeling Schemes for Trees

Stephen Alstrup, Inge Li Gørtz, Esben Bistrup Halvorsen & Ely Porat
We consider distance labeling schemes for trees: given a tree with n nodes, label the nodes with binary strings such that, given the labels of any two nodes, one can determine, by looking only at the labels, the distance in the tree between the two nodes. A lower bound by Gavoille et al. [Gavoille et al., J. Alg., 2004] and an upper bound by Peleg [Peleg, J. Graph Theory, 2000] establish that labels must use...

### Public-Key Cryptography (Dagstuhl Seminar 11391)

Marc Fischlin, Anna Lysyanskaya, Ueli Maurer & Alexander May
From September 25th till September 30th, 2011, the Dagstuhl Seminar 11391 about `Public-Key Cryptography'' took place at Schloss Dagstuhl. The meeting hosted 33 international researchers and incited active discussions about recent developments in this area.

### Visualizing Scissors Congruence

Satyan Devadoss, Ziv Epstein & Dmitriy Smirnov
Consider two simple polygons with equal area. The Wallace-Bolyai-Gerwien theorem states that these polygons are scissors congruent, that is, they can be dissected into finitely many congruent polygonal pieces. We present an interactive application that visualizes this constructive proof.

### Derandomizing Local Distributed Algorithms under Bandwidth Restrictions

Keren Censor-Hillel, Merav Parter & Gregory Schwartzman
This paper addresses the cornerstone family of local problems in distributed computing, and investigates the curious gap between randomized and deterministic solutions under bandwidth restrictions. Our main contribution is in providing tools for derandomizing solutions to local problems, when the n nodes can only send O(log n)-bit messages in each round of communication. We combine bounded independence, which we show to be sufficient for some algorithms, with the method of conditional expectations and with additional...

### Augmented Index and Quantum Streaming Algorithms for DYCK(2)

Ashwin Nayak & Dave Touchette
We show how two recently developed quantum information theoretic tools can be applied to obtain lower bounds on quantum information complexity. We also develop new tools with potential for broader applicability, and use them to establish a lower bound on the quantum information complexity for the Augmented Index function on an easy distribution. This approach allows us to handle superpositions rather than distributions over inputs, the main technical challenge faced previously. By providing a quantum...

• 2009
134
• 2010
453
• 2011
366
• 2012
447
• 2013
462
• 2014
432
• 2015
732
• 2016
1,178
• 2017
1,326
• 2018
1,647
• 2019
1,497
• 2020
131

• Text
8,705
• Software
100