8,563 Works

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.

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

Functional Lower Bounds for Arithmetic Circuits and Connections to Boolean Circuit Complexity

Michael A. Forbes, Mrinal Kumar & Ramprasad Saptharishi
We say that a circuit C over a field F {functionally} computes a polynomial P in F[x_1, x_2, ..., x_n] if for every x in {0,1}^n we have that C(x) = P(x). This is in contrast to syntactically computing P, when C = P as formal polynomials. In this paper, we study the question of proving lower bounds for homogeneous depth-3 and depth-4 arithmetic circuits for functional computation. We prove the following results: 1. Exponential...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

NumLin: Linear Types for Linear Algebra

Dhruv C. Makwana & Neelakantan R. Krishnaswami
We present NumLin, a functional programming language whose type system is designed to enforce the safe usage of the APIs of low-level linear algebra libraries (such as BLAS/LAPACK). We do so through a brief description of its key features and several illustrative examples. We show that NumLin's type system is sound and that its implementation improves upon naïve implementations of linear algebra programs, almost towards C-levels of performance. By doing so, we demonstrate (a) that...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Pattern Generation by Cellular Automata (Invited Talk)

Jarkko Kari
A one-dimensional cellular automaton is a discrete dynamical system where a sequence of symbols evolves synchronously according to a local update rule. We discuss simple update rules that make the automaton perform multiplications of numbers by a constant. If the constant and the number base are selected suitably the automaton becomes a universal pattern generator: all finite strings over its state alphabet appear from a finite seed. In particular we consider the automata that multiply...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Termination in Convex Sets of Distributions

Ana Sokolova & Harald Woracek
Convex algebras, also called (semi)convex sets, are at the heart of modelling probabilistic systems including probabilistic automata. Abstractly, they are the Eilenberg-Moore algebras of the finitely supported distribution monad. Concretely, they have been studied for decades within algebra and convex geometry. In this paper we study the problem of extending a convex algebra by a single point. Such extensions enable the modelling of termination in probabilistic systems. We provide a full description of all possible...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Fractional Coverings, Greedy Coverings, and Rectifier Networks

Dmitry Chistikov, Szabolcs Iván, Anna Lubiw & Jeffrey Shallit
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Probabilistic Smallest Enclosing Ball in High Dimensions via Subgradient Sampling

Amer Krivosija & Alexander Munteanu
We study a variant of the median problem for a collection of point sets in high dimensions. This generalizes the geometric median as well as the (probabilistic) smallest enclosing ball (pSEB) problems. Our main objective and motivation is to improve the previously best algorithm for the pSEB problem by reducing its exponential dependence on the dimension to linear. This is achieved via a novel combination of sampling techniques for clustering problems in metric spaces with...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

The PACE 2019 Parameterized Algorithms and Computational Experiments Challenge: The Fourth Iteration (Invited Paper)

M. Ayaz Dzulfikar, Johannes K. Fichte & Markus Hecher
The organizers of the 4th Parameterized Algorithms and Computational Experiments challenge (PACE 2019) report on the 4th iteration of the PACE challenge. This year, the first track featured the MinVertexCover problem, which asks given an undirected graph G=(V,E) to output a set S subseteq V of vertices such that for every edge vw in E at least one endpoint belongs to S. The exact decision version of this problem is one of the most discussed...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs

Jana Novotná, Karolina Okrasa, Michal Pilipczuk, Pawel Rzazewski, Erik Jan Van Leeuwen & Bartosz Walczak
Let C and D be hereditary graph classes. Consider the following problem: given a graph G in D, find a largest, in terms of the number of vertices, induced subgraph of G that belongs to C. We prove that it can be solved in 2^{o(n)} time, where n is the number of vertices of G, if the following conditions are satisfied: - the graphs in C are sparse, i.e., they have linearly many edges in...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Beating Treewidth for Average-Case Subgraph Isomorphism

Gregory Rosenthal
For any fixed graph G, the subgraph isomorphism problem asks whether an n-vertex input graph has a subgraph isomorphic to G. A well-known algorithm of Alon, Yuster and Zwick (1995) efficiently reduces this to the "colored" version of the problem, denoted G-SUB, and then solves G-SUB in time O(n^{tw(G)+1}) where tw(G) is the treewidth of G. Marx (2010) conjectured that G-SUB requires time Omega(n^{const * tw(G)}) and, assuming the Exponential Time Hypothesis, proved a lower...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Improved Analysis of Highest-Degree Branching for Feedback Vertex Set

Yoichi Iwata & Yusuke Kobayashi
Recent empirical evaluations of exact algorithms for Feedback Vertex Set have demonstrated the efficiency of a highest-degree branching algorithm with a degree-based pruning heuristic. In this paper, we prove that this empirically fast algorithm runs in O(3.460^k n) time, where k is the solution size. This improves the previous best O(3.619^k n)-time deterministic algorithm obtained by Kociumaka and Pilipczuk (Inf. Process. Lett., 2014).
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Finding Linear Arrangements of Hypergraphs with Bounded Cutwidth in Linear Time

Thekla Hamm
Cutwidth is a fundamental graph layout parameter. It generalises to hypergraphs in a natural way and has been studied in a wide range of contexts. For graphs it is known that for a fixed constant k there is a linear time algorithm that for any given G, decides whether G has cutwidth at most k and, in the case of a positive answer, outputs a corresponding linear arrangement. We show that such an algorithm also...
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
    720
  • 2016
    1,161
  • 2017
    1,301
  • 2018
    1,625
  • 2019
    1,462

Resource Types

  • Text
    8,563