8,663 Works

Reachability in Networks of Register Protocols under Stochastic Schedulers

Patricia Bouyer, Nicolas Markey, Mickael Randour, Arnaud Sangnier & Daniel Stan
We study the almost-sure reachability problem in a distributed system obtained as the asynchronous composition of N copies (called processes) of the same automaton (called protocol), that can communicate via a shared register with finite domain. The automaton has two types of transitions: write-transitions update the value of the register, while read-transitions move to a new state depending on the content of the register. Non-determinism is resolved by a stochastic scheduler. Given a protocol, we...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Symbolic-Numeric Methods for Problem Solving in CPS (Dagstuhl Seminar 16491)

Sergiy Bogomolov, Martin Fränzle, Kyoko Makino & Nacim Ramdani
Reflecting the fundamental role numeric and mixed symbolic-numeric arguments play in the analysis, decision making, and control of cyber-physical processes, this seminar promoted cross-fertilization between the following research areas relevant to problem solving in cyber-physical domains: verification of numerical reactive systems such as embedded floating-point programs and hybrid systems, including novel means of error-propagation analysis; numerical and/or symbolic methods such as verified integrations, interval methods and arithmetic constraint solving; reactive and in-advance planning and optimization...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

On Decidability of Concurrent Kleene Algebra

Paul Brunet, Damien Pous & Georg Struth
Concurrent Kleene algebras support equational reasoning about computing systems with concurrent behaviours. Their natural semantics is given by series(-parallel) rational pomset languages, a standard true concurrency semantics, which is often associated with processes of Petri nets. We use constructions on Petri nets to provide two decision procedures for such pomset languages motivated by the equational and the refinement theory of concurrent Kleene algebra. The contribution to the first problem lies in a much simpler algorithm...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Interactive Geometric Algorithm Visualization in a Browser

Kirk Gardner, Lynn Asselin & Donald Sheehy
We present an online, interactive tool for writing and presenting interactive geometry demos suitable for classroom demonstrations. Code for the demonstrations is written in JavaScript using p5.js, a JavaScript library based on Processing.
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

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...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

An Overview of Open Information Extraction (Invited talk)

Pablo Gamallo
Open Information Extraction (OIE) is a recent unsupervised strategy to extract great amounts of basic propositions (verb-based triples) from massive text corpora which scales to Web-size document collections. We will introduce the main properties of this extraction method.
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Tree Automata, (Dis-)Equality Constraints and Term Rewriting: What's New?

Sophie Tison
Connections between Tree Automata and Term Rewriting are now well known. Whereas tree automata can be viewed as a subclass of ground rewrite systems, tree automata are successfully used as decision tools in rewriting theory. Furthermore, applications, including rewriting theory, have influenced the definition of new classes of tree automata. In this talk, we will first present a short and not exhaustive reminder of some fruitful applications of tree automata in rewriting theory. Then, we...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Large-Scale Distributed Algorithms for Facility Location with Outliers

Tanmay Inamdar, Shreyas Pai & Sriram V. Pemmaraju
This paper presents fast, distributed, O(1)-approximation algorithms for metric facility location problems with outliers in the Congested Clique model, Massively Parallel Computation (MPC) model, and in the k-machine model. The paper considers Robust Facility Location and Facility Location with Penalties, two versions of the facility location problem with outliers proposed by Charikar et al. (SODA 2001). The paper also considers two alternatives for specifying the input: the input metric can be provided explicitly (as an...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

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...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Weak 1/r-Nets for Moving Points

Alexandre Rok & Shakhar Smorodinsky
In this paper, we extend the weak 1/r-net theorem to a kinetic setting where the underlying set of points is moving polynomially with bounded description complexity. We establish that one can find a kinetic analog N of a weak 1/r-net of cardinality O(r^(d(d+1)/2)log^d r) whose points are moving with coordinates that are rational functions with bounded description complexity. Moreover, each member of N has one polynomial coordinate.
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

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...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

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...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Lempel-Ziv Compression in a Sliding Window

Philip Bille, Patrick Hagge Cording, Johannes Fischer & Inge Li Gørtz
We present new algorithms for the sliding window Lempel-Ziv (LZ77) problem and the approximate rightmost LZ77 parsing problem. Our main result is a new and surprisingly simple algorithm that computes the sliding window LZ77 parse in O(w) space and either O(n) expected time or O(n log log w+z log log s) deterministic time. Here, w is the window size, n is the size of the input string, z is the number of phrases in the...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

A Simple Topology Preserving Max-Flow Algorithm for Graph Cut Based Image Segmentation

Ondrej Danek & Martin Maska
In this paper, we propose a modification to the Boykov-Kolmogorov maximum flow algorithm [Boykov, Kolmogorv, IEEE 2004] in order to make the algorithm preserve the topology of an initial interface. This algorithm is being widely used in computer vision and image processing fields for its efficiency and speed when dealing with problems such as graph cut based image segmentation. Using our modification we are able to incorporate a topology prior into the algorithm allowing us...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Approximating Hit Rate Curves using Streaming Algorithms

Zachary Drudi, Nicholas J. A. Harvey, Stephen Ingram, Andrew Warfield & Jake Wires
A hit rate curve is a function that maps cache size to the proportion of requests that can be served from the cache. (The caching policy and sequence of requests are assumed to be fixed.) Hit rate curves have been studied for decades in the operating system, database and computer architecture communities. They are useful tools for designing appropriate cache sizes, dynamically allocating memory between competing caches, and for summarizing locality properties of the request...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Declutter and Resample: Towards Parameter Free Denoising

Mickael Buchet, Tamal K. Dey, Jiayuan Wang & Yusu Wang
In many data analysis applications the following scenario is commonplace: we are given a point set that is supposed to sample a hidden ground truth K in a metric space, but it got corrupted with noise so that some of the data points lie far away from K creating outliers also termed as ambient noise. One of the main goals of denoising algorithms is to eliminate such noise so that the curated data lie within...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness

Julian Dörfler, Marc Roth, Johannes Schmitt & Philip Wellnitz
We study the problem #IndSub(Phi) of counting all induced subgraphs of size k in a graph G that satisfy the property Phi. This problem was introduced by Jerrum and Meeks and shown to be #W[1]-hard when parameterized by k for some families of properties Phi including, among others, connectivity [JCSS 15] and even- or oddness of the number of edges [Combinatorica 17]. Very recently [IPEC 18], two of the authors introduced a novel technique for...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

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...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

List Decoding Group Homomorphisms Between Supersolvable Groups

Alan Guo & Madhu Sudan
We show that the set of homomorphisms between two supersolvable groups can be locally list decoded up to the minimum distance of the code, extending the results of Dinur et al. (Proc. STOC 2008) who studied the case where the groups are abelian. Moreover, when specialized to the abelian case, our proof is more streamlined and gives a better constant in the exponent of the list size. The constant is improved from about 3.5 million...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Multivariate Amortised Resource Analysis for Term Rewrite Systems

Martin Hofmann & Georg Moser
We study amortised resource analysis in the context of term rewrite systems. We introduce a novel amortised analysis based on the potential method. The method is represented in an inference system akin to a type system and gives rise to polynomial bounds on the innermost runtime complexity of the analysed rewrite system. The crucial feature of the inference system is the admittance of multivariate bounds in the context of arbitrary data structures in a completely...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

On the Number of Ordinary Lines Determined by Sets in Complex Space

Abdul Basit, Zeev Dvir, Shubhangi Saraf & Charles Wolf
Kelly's theorem states that a set of n points affinely spanning C^3 must determine at least one ordinary complex line (a line passing through exactly two of the points). Our main theorem shows that such sets determine at least 3n/2 ordinary lines, unless the configuration has n-1 points in a plane and one point outside the plane (in which case there are at least n-1 ordinary lines). In addition, when at most n/2 points are...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Verification of redecoration for infinite triangular matrices using coinduction

Ralph Matthes & Celia Picard
Finite triangular matrices with a dedicated type for the diagonal elements can be profitably represented by a nested data type, i. e., a heterogeneous family of inductive data types, while infinite triangular matrices form an example of a nested coinductive type, which is a heterogeneous family of coinductive data types. Redecoration for infinite triangular matrices is taken up from previous work involving the first author, and it is shown that redecoration forms a comonad with...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Inverse Unfold Problem and Its Heuristic Solving

Masanori Nagashima, Tomofumi Kato, Masahiko Sakai & Naoki Nishida
Unfold/fold transformations have been widely studied in various programming paradigms and are used in program transformations, theorem proving, and so on. This paper, by using an example, show that restoring an one-step unfolding is not easy, i.e., a challenging task, since some rules used by unfolding may be lost. We formalize this problem by regarding one-step program transformation as a relation. Next we discuss some issues on a specific framework, called pure-constructor systems, which constitute...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Feature Interactions: The Next Generation (Dagstuhl Seminar 14281)

Sven Apel, Joanne M. Atlee, Luciano Baresi & Pamela Zave
The feature-interaction problem is a major threat to modularity and impairs compositional development and reasoning. A feature interaction occurs when the behavior of one feature is affected by the presence of another feature; often it cannot be deduced easily from the behaviors of the individual features involved. The feature-interaction problem became a crisis in the telecommunications industry in the late 1980s, and researchers responded with formalisms that enable automatic detection of feature interactions, architectures that...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

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...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Registration Year

  • 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,486

Resource Types

  • Text
    8,563
  • Software
    100