8,383 Works

An Optimal Dual Fault Tolerant Reachability Oracle

Keerti Choudhary
Let G=(V,E) be an n-vertices m-edges directed graph. Let s inV be any designated source vertex. We address the problem of reporting the reachability information from s under two vertex failures. We show that it is possible to compute in polynomial time an O(n) size data structure that for any query vertex v, and any pair of failed vertices f_1, f_2, answers in O(1) time whether or not there exists a path from s to...

On Randomized Generation of Slowly Synchronizing Automata

Costanza Catalano & Raphaël M. Jungers
Motivated by the randomized generation of slowly synchronizing automata, we study automata made of permutation letters and a merging letter of rank n-1 . We present a constructive randomized procedure to generate synchronizing automata of that kind with (potentially) large alphabet size based on recent results on primitive sets of matrices. We report numerical results showing that our algorithm finds automata with much larger reset threshold than a mere uniform random generation and we present...

Hiding Communication Delays in Contention-Free Execution for SPM-Based Multi-Core Architectures

Benjamin Rouxel, Stefanos Skalistis, Steven Derrien & Isabelle Puaut
Multi-core systems using ScratchPad Memories (SPMs) are attractive architectures for executing time-critical embedded applications, because they provide both predictability and performance. In this paper, we propose a scheduling technique that jointly selects SPM contents off-line, in such a way that the cost of SPM loading/unloading is hidden. Communications are fragmented to augment hiding possibilities. Experimental results show the effectiveness of the proposed technique on streaming applications and synthetic task-graphs. The overlapping of communications with computations...

Structure and Stability of the 1-Dimensional Mapper

Mathieu Carrière & Steve Oudot
Given a continuous function f:X->R and a cover I of its image by intervals, the Mapper is the nerve of a refinement of the pullback cover f^{-1}(I). Despite its success in applications, little is known about the structure and stability of this construction from a theoretical point of view. As a pixelized version of the Reeb graph of f, it is expected to capture a subset of its features (branches, holes), depending on how the...

The iBUG Eye Segmentation Dataset

Bingnan Luo, Jie Shen, Yujiang Wang & Maja Pantic
This paper presents the first dataset for eye segmentation in low resolution images. Although eye segmentation has long been a vital preprocessing step in biometric applications, this work is the first to focus on low resolutions image that can be expected from a consumer-grade camera under conventional human-computer interaction and / or video-chat scenarios. Existing eye datasets have multiple limitations, including: (a) datasets only contain high resolution images; (b) datasets did not include enough pose...

Distributed Local Strategies in Broadcast Networks

Nathalie Bertrand, Paulin Fournier & Arnaud Sangnier
We study the problems of reaching a specific control state, or converging to a set of target states, in networks with a parameterized number of identical processes communicating via broadcast. To reflect the distributed aspect of such networks, we restrict our attention to executions in which all the processes must follow the same local strategy that, given their past performed actions and received messages, provides the next action to be performed. We show that the...

Can a permutation be sorted by best short swaps?

Shu Zhang, Daming Zhu, Haitao Jiang, Jingjing Ma, Jiong Guo & Haodi Feng
A short swap switches two elements with at most one element caught between them. Sorting permutation by short swaps asks to find a shortest short swap sequence to transform a permutation into another. A short swap can eliminate at most three inversions. It is still open for whether a permutation can be sorted by short swaps each of which can eliminate three inversions. In this paper, we present a polynomial time algorithm to solve the...

New Abilities and Limitations of Spectral Graph Bisection

Martin R. Schuster & Maciej Liskiewicz
Spectral based heuristics belong to well-known commonly used methods which determines provably minimal graph bisection or outputs "fail" when the optimality cannot be certified. In this paper we focus on Boppana's algorithm which belongs to one of the most prominent methods of this type. It is well known that the algorithm works well in the random planted bisection model - the standard class of graphs for analysis minimum bisection and relevant problems. In 2001 Feige...

The Matrix Ring of a mu-Continuous Chomsky Algebra is mu-Continuous

Hans Leiss
In the course of providing an (infinitary) axiomatization of the equational theory of the class of context-free languages, Grathwohl, Kozen and Henglein (2013) have introduced the class of mu-continuous Chomsky algebras. These are idempotent semirings where least solutions for systems of polynomial inequations (i.e. context-free grammars) can be computed iteratively and where multiplication is continuous with respect to the least fixed point operator mu. We prove that the matrix ring of a mu-continuous Chomsky algebra...

A Unified Algorithm for Accelerating Edit-Distance Computation via Text-Compression

Danny Hermelin, Gad M. Landau, Shir Landau & Oren Weimann
The edit distance problem is a classical fundamental problem in computer science in general, and in combinatorial pattern matching in particular. The standard dynamic-programming solution for this problem computes the edit-distance between a pair of strings of total length $O(N)$ in $O(N^2)$ time. To this date, this quadratic upper-bound has never been substantially improved for general strings. However, there are known techniques for breaking this bound in case the strings are known to compress well...

Improved Dynamic Graph Coloring

Shay Solomon & Nicole Wein
This paper studies the fundamental problem of graph coloring in fully dynamic graphs. Since the problem of computing an optimal coloring, or even approximating it to within n^{1-epsilon} for any epsilon > 0, is NP-hard in static graphs, there is no hope to achieve any meaningful computational results for general graphs in the dynamic setting. It is therefore only natural to consider the combinatorial aspects of dynamic coloring, or alternatively, study restricted families of graphs....

The Containment Problem for Unambiguous Register Automata

Antoine Mottet & Karin Quaas
We investigate the complexity of the containment problem "Does L(A)subseteq L(B) hold?", where B is an unambiguous register automaton and A is an arbitrary register automaton. We prove that the problem is decidable and give upper bounds on the computational complexity in the general case, and when B is restricted to have a fixed number of registers.

Front Matter, Table of Contents, Preface, Conference Organization

Maribel Fernández
Front Matter, Table of Contents, Preface, Conference Organization

Interprocedural Type Specialization of JavaScript Programs Without Type Analysis

Maxime Chevalier-Boisvert & Marc Feeley
Previous work proposed lazy basic block versioning, a technique for just-in-time compilation of dynamic languages which we believe represents an interesting point in the design space. Basic block versioning is simple to implement, simple enough that a single developer can build a complete just-in-time compiler for JavaScript in a year, yet it performs surprisingly well as it propagates context-sensitive type information to generate type-specialized code on the fly. In this paper, we demonstrate that lazy...

Finding Secluded Places of Special Interest in Graphs

René Van Bevern, Till Fluschnik, George B. Mertzios, Hendrik Molter, Manuel Sorge & Ondrej Suchý
Finding a vertex subset in a graph that satisfies a certain property is one of the most-studied topics in algorithmic graph theory. The focus herein is often on minimizing or maximizing the size of the solution, that is, the size of the desired vertex set. In several applications, however, we also want to limit the "exposure" of the solution to the rest of the graph. This is the case, for example, when the solution represents...

Determinisation of Finitely-Ambiguous Copyless Cost Register Automata

Théodore Lopez, Benjamin Monmege & Jean-Marc Talbot
Cost register automata (CRA) are machines reading an input word while computing values using write-only registers: values from registers are combined using the two operations, as well as the constants, of a semiring. Particularly interesting is the subclass of copyless CRAs where the content of a register cannot be used twice for updating the registers. Originally deterministic, non-deterministic variant of CRA may also be defined: the semantics is then obtained by combining the values of...

Barriers for Rank Methods in Arithmetic Complexity

Klim Efremenko, Ankit Garg, Rafael Oliveira & Avi Wigderson
Arithmetic complexity, the study of the cost of computing polynomials via additions and multiplications, is considered (for many good reasons) simpler to understand than Boolean complexity, namely computing Boolean functions via logical gates. And indeed, we seem to have significantly more lower bound techniques and results in arithmetic complexity than in Boolean complexity. Despite many successes and rapid progress, however, foundational challenges, like proving super-polynomial lower bounds on circuit or formula size for explicit polynomials,...

Outdoor and Large-Scale Real-World Scene Analysis. 15th Workshop Theoretic Foundations of Computer Vision (Dagstuhl Seminar 11261)

Frank Dellaert, Jan-Michael Frahm, Marc Pollefeys & Bodo Rosenhahn
This report documents the program and the outcomes of Dagstuhl Seminar 11261 ``Outdoor and Large-Scale Real-World Scene Analysis, 15th Workshop Theoretic Foundations of Computer Vision''. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in...

Independent Sets near the Lower Bound in Bounded Degree Graphs

Zdenek Dvorák & Bernard Lidický
By Brook's Theorem, every n-vertex graph of maximum degree at most Delta >= 3 and clique number at most Delta is Delta-colorable, and thus it has an independent set of size at least n/Delta. We give an approximate characterization of graphs with independence number close to this bound, and use it to show that the problem of deciding whether such a graph has an independent set of size at least n/Delta+k has a kernel of...

Dimension, Pseudorandomness and Extraction of Pseudorandomness

Manindra Agrawal, Diptarka Chakraborty, Debarati Das & Satyadev Nandakumar
In this paper we propose a quantification of distributions on a set of strings, in terms of how close to pseudorandom a distribution is. The quantification is an adaptation of the theory of dimension of sets of infinite sequences introduced by Lutz. Adapting Hitchcock's work, we also show that the logarithmic loss incurred by a predictor on a distribution is quantitatively equivalent to the notion of dimension we define. Roughly, this captures the equivalence between...

An Efficient Communication Abstraction for Dense Wireless Networks

Magnús M. Halldórsson, Fabian Kuhn, Nancy Lynch & Calvin Newport
In this paper we study the problem of developing efficient distributed algorithms for dense wireless networks. For many problems in this setting, fast solutions must leverage the reality that radio signals fade with distance, which can be exploited to enable concurrent communication among multiple sender/receiver pairs. To simplify the development of these algorithms we describe a new communication abstraction called FadingMAC which exposes the benefits of this concurrent communication, but also hides the details of...

Temporal Vertex Cover with a Sliding Time Window

Eleni C. Akrida, George B. Mertzios, Paul G. Spirakis & Viktor Zamaraev
Modern, inherently dynamic systems are usually characterized by a network structure, i.e. an underlying graph topology, which is subject to discrete changes over time. Given a static underlying graph G, a temporal graph can be represented via an assignment of a set of integer time-labels to every edge of G, indicating the discrete time steps when this edge is active. While most of the recent theoretical research on temporal graphs has focused on the notion...

Evaluation of Social Personalized Adaptive E-Learning Environments: End-User Point of View

Lei Shi, Malik Shahzad Awan & Alexandra I. Cristea
The use of adaptations, along with the social affordances of collaboration and networking, carries a great potential for improving e-learning experiences. However, the review of the previous work indicates current e-learning systems have only marginally explored the integration of social features and adaptation techniques. The overall aim of this research, therefore, is to address this gap by evaluating a system developed to foster social personalized adaptive e-learning experiences. We have developed our first prototype system,...

Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth

Bas A. M. Van Geffen, Bart M. P. Jansen, Arnoud A. W. M. De Kroon & Rolf Morel
Many combinatorial problems can be solved in time O^*(c^{tw}) on graphs of treewidth tw, for a problem-specific constant c. In several cases, matching upper and lower bounds on c are known based on the Strong Exponential Time Hypothesis (SETH). In this paper we investigate the complexity of solving problems on graphs of bounded cutwidth, a graph parameter that takes larger values than treewidth. We strengthen earlier treewidth-based lower bounds to show that, assuming SETH, Independent...

Artifact Evaluation for Publications (Dagstuhl Perspectives Workshop 15452)

Bruce R. Childers, Grigori Fursin, Shriram Krishnamurthi & Andreas Zeller
This report documents the program and the outcomes of Dagstuhl Perspectives Workshop 15452 "Artifact Evaluation for Publications". This Perspectives Workshop conveyed several stakeholders in artifact evaluation from different communities to assess how artifact evaluation is working and make recommendations to the computer systems research community about several issues with the process.

Registration Year

  • 2009
  • 2010
  • 2011
  • 2012
  • 2013
  • 2014
  • 2015
  • 2016
  • 2017
  • 2018
  • 2019

Resource Types

  • Text
  • Software

Data Centers

  • Dagstuhl