7,520 Works

Fast Implementation of the Scalable Video Coding Extension of the H.264/AVC Standard

Xin Lu & Graham R. Martin
In order to improve coding efficiency in the scalable extension of H.264/AVC, an inter-layer prediction mechanism is incorporated. This exploits as much lower layer information as possible to inform the process of coding the enhancement layer(s). However it also greatly increases the computational complexity. In this paper, a fast mode decision algorithm for efficient implementation of the SVC encoder is described. The proposed algorithm not only considers inter-layer correlation but also fully exploits both spatial...

Origamizer: A Practical Algorithm for Folding Any Polyhedron

Erik D. Demaine & Tomohiro Tachi

Res Publica: The Universal Model of Computation (Invited Talk)

Nachum Dershowitz
We proffer a model of computation that encompasses a broad variety of contemporary generic models, such as cellular automata---including dynamic ones, and abstract state machines---incorporating, as they do, interaction and parallelism. We ponder what it means for such an intertwined system to be effective and note that the suggested framework is ideal for representing continuous-time and asynchronous systems.

Placing your Coins on a Shelf

Helmut Alt, Kevin Buchin, Steven Chaplick, Otfried Cheong, Philipp Kindermann, Christian Knauer & Fabian Stehn
We consider the problem of packing a family of disks 'on a shelf,' that is, such that each disk touches the x-axis from above and such that no two disks overlap. We prove that the problem of minimizing the distance between the leftmost point and the rightmost point of any disk is NP-hard. On the positive side, we show how to approximate this problem within a factor of 4/3 in O(n log n) time, and...

The Positivication of Coalgebraic Logics

Fredrik Dahlqvist & Alexander Kurz
We present positive coalgebraic logic in full generality, and show how to obtain a positive coalgebraic logic from a boolean one. On the model side this involves canonically computing a endofunctor T': Pos->Pos from an endofunctor T: Set->Set, in a procedure previously defined by the second author et alii called posetification. On the syntax side, it involves canonically computing a syntax-building functor L': DL->DL from a syntax-building functor L: BA->BA, in a dual procedure which...

Compact LP Relaxations for Allocation Problems

Klaus Jansen & Lars Rohwedder
We consider the restricted versions of Scheduling on Unrelated Machines and the Santa Claus problem. In these problems we are given a set of jobs and a set of machines. Every job j has a size p_j and a set of allowed machines \Gamma(j), i.e., it can only be assigned to those machines. In the first problem, the objective is to minimize the maximum load among all machines; in the latter problem it is to...

The First-Order Theory of Ground Tree Rewrite Graphs

Stefan Göller & Markus Lohrey
We prove that the complexity of the uniform first-order theory of ground tree rewrite graphs is in ATIME(2^{2^{poly(n)}},O(n). Providing a matching lower bound, we show that there is some fixed ground tree rewrite graph whose first-order theory is hard for ATIME(2^{2^{poly(n)}},poly(n)) with respect to logspace reductions. Finally, we prove that there exists a fixed ground tree rewrite graph together with a single unary predicate in form of a regular tree language such that the resulting...

New Exact and Approximation Algorithms for the Star Packing Problem in Undirected Graphs

Maxim Babenko & Alexey Gusakov
By a T-star we mean a complete bipartite graph K_{1,t} for some t <= T. For an undirected graph G, a T-star packing is a collection of node-disjoint T-stars in G. For example, we get ordinary matchings for $T = 1$ and packings of paths of length 1 and 2 for $T = 2$. Hereinafter we assume that T >= 2. Hell and Kirkpatrick devised an ad-hoc augmenting algorithm that finds a T-star packing covering...

Deterministic Sub-Linear Space LCE Data Structures With Efficient Construction

Yuka Tanimura, Tomohiro I, Hideo Bannai, Shunsuke Inenaga, Simon J. Puglisi & Masayuki Takeda
Given a string S of n symbols, a longest common extension query LCE(i,j) asks for the length of the longest common prefix of the $i$th and $j$th suffixes of S. LCE queries have several important applications in string processing, perhaps most notably to suffix sorting. Recently, Bille et al. (J. Discrete Algorithms 25:42-50, 2014, Proc. CPM 2015:65-76) described several data structures for answering LCE queries that offers a space-time trade-off between data structure size and...

Framework for Comprehensive Size and Resolution Utilization of Arbitrary Displays

Taimur Khan, Daniel Schneider, Yasmin Al-Zokari, Dirk Zeckzer & Hans Hagen
Scalable large high-resolution displays such as tiled displays are imperative for the visualization of large and complex datasets. In recent times, the relatively low costs for setting up large display systems have led to an highly increased usage of such devices. However, it is equally vital to optimally utilize their size and resolution to effectively explore such data through a combination of diverse visualizations, views, and interaction mechanisms. In this paper, we present a lightweight...

Intersection Types and Denotational Semantics: An Extended Abstract (Invited Paper)

Simona Ronchi Della Rocca
This is a short survey of the use of intersection types for reasoning in a finitary way about terms interpretations in various models of lambda-calculus.

Quantum Capacity Can Be Greater Than Private Information for Arbitrarily Many Uses

David Elkouss & Sergii Strelchuk
The quantum capacity of a quantum channel is always smaller than the capacity of the channel for private communication. However, both quantities are given by the infinite regularization of respectively the coherent and the private information. Here, we construct a family of channels for which the private and coherent information can remain strictly superadditive for unbounded number of uses. We prove this by showing that the coherent information is strictly larger than the private information...

Recovering Sparse Graphs

Jakub Gajarský & Daniel Král'
We construct a fixed parameter algorithm parameterized by d and k that takes as an input a graph G' obtained from a d-degenerate graph G by complementing on at most k arbitrary subsets of the vertex set of G and outputs a graph H such that G and H agree on all but f(d,k) vertices. Our work is motivated by the first order model checking in graph classes that are first order interpretable in classes...

Computing Semantic Relatedness using DBPedia

José Paulo Leal, Vânia Rodrigues & Ricardo Queirós
Extracting the semantic relatedness of terms is an important topic in several areas, including data mining, information retrieval and web recommendation. This paper presents an approach for computing the semantic relatedness of terms using the knowledge base of DBpedia - a community effort to extract structured information from Wikipedia. Several approaches to extract semantic relatedness from Wikipedia using bag-of-words vector models are already available in the literature. The research presented in this paper explores a...

Shape Analysis: Euclidean, Discrete and Algebraic Geometric Methods (Dagstuhl Seminar 18422)

Michael Breuß, Alfred M. Bruckstein, Christer Oscar Kiselman & Petros Maragos
In computer vision, geometric processing and image analysis, the notation of a shape of a 3-D object has been studied either by an embedded manifold for the continuous stetting or as a collection of a discrete set of marker positions on the manifold. Within the last years, there have been many rapid developments in the field of shape representation, shape correspondence and shape manipulation with technical applications ranging from laser-range scanners to 3-D printing. Classic...

Bisimilarity of Probabilistic Pushdown Automata

Vojtech Forejt, Petr Jancar, Stefan Kiefer & James Worrell
We study the bisimilarity problem for probabilistic pushdown automata (pPDA) and subclasses thereof. Our definition of pPDA allows both probabilistic and non-deterministic branching, generalising the classical notion of pushdown automata (without epsilon-transitions). Our first contribution is a general construction that reduces checking bisimilarity of probabilistic transition systems to checking bisimilarity of non-deterministic transition systems. This construction directly yields decidability of bisimilarity for pPDA, as well as an elementary upper bound for the bisimilarity problem on...

Towards an Automated Test Bench Environment for Prolog Systems

Ricardo Gonçalves, Miguel Areias & Ricardo Rocha
Software testing and benchmarking is a key component of the software development process. Nowadays, a good practice in big software projects is the Continuous Integration (CI) software development technique. The key idea of CI is to let developers integrate their work as they produce it, instead of doing the integration at the end of each software module. In this paper, we extend a previous work on a benchmark suite for the Yap Prolog system and...

Flight Planning in Free Route Airspaces

Casper Kehlet Jensen, Marco Chiarandini & Kim S. Larsen
We consider the problem of finding cheapest flight routes through free route airspaces in a 2D setting. We subdivide the airspace into regions determined by a Voronoi subdivision around the points from a weather forecast. This gives rise to a regular grid of rectangular regions (quads) with every quad having an associated vector-weight that represents the wind magnitude and direction. Finding a cheapest path in this setting corresponds to finding a piece-wise linear path determined...

QL: Object-oriented Queries on Relational Data

Pavel Avgustinov, Oege De Moor, Michael Peyton Jones & Max Schäfer
This paper describes QL, a language for querying complex, potentially recursive data structures. QL compiles to Datalog and runs on a standard relational database, yet it provides familiar-looking object-oriented features such as classes and methods, reinterpreted in logical terms: classes are logical properties describing sets of values, subclassing is implication, and virtual calls are dispatched dynamically by considering the most specific classes containing the receiver. Furthermore, types in QL are prescriptive and actively influence program...

The Computational Complexity of Portal and Other 3D Video Games

Erik D. Demaine, Joshua Lockhart & Jayson Lynch
We classify the computational complexity of the popular video games Portal and Portal 2. We isolate individual mechanics of the game and prove NP-hardness, PSPACE-completeness, or pseudo-polynomiality depending on the specific game mechanics allowed. One of our proofs generalizes to prove NP-hardness of many other video games such as Half-Life 2, Halo, Doom, Elder Scrolls, Fallout, Grand Theft Auto, Left 4 Dead, Mass Effect, Deus Ex, Metal Gear Solid, and Resident Evil. These results build...

Approximating Fault-Tolerant Group-Steiner Problems

Rohit Khandekar, Guy Kortsarz & Zeev Nutov
In this paper, we initiate the study of designing approximation algorithms for {\sf Fault-Tolerant Group-Steiner} ({\sf FTGS}) problems. The motivation is to protect the well-studied group-Steiner networks from edge or vertex failures. In {\sf Fault-Tolerant Group-Steiner} problems, we are given a graph with edge- (or vertex-) costs, a root vertex, and a collection of subsets of vertices called groups. The objective is to find a minimum-cost subgraph that has two edge- (or vertex-) disjoint paths...

Approximating Smallest Containers for Packing Three-Dimensional Convex Objects

Helmut Alt & Nadja Scharf
We investigate the problem of computing a minimum-volume container for the non-overlapping packing of a given set of three-dimensional convex objects. Already the simplest versions of the problem are NP-hard so that we cannot expect to find exact polynomial time algorithms. We give constant ratio approximation algorithms for packing axis-parallel (rectangular) cuboids under translation into an axis-parallel (rectangular) cuboid as container, for packing cuboids under rigid motions into an axis-parallel cuboid or into an arbitrary...

Fine-grained Lower Bounds on Cops and Robbers

Sebastian Brandt, Seth Pettie & Jara Uitto
Cops and Robbers is a classic pursuit-evasion game played between a group of g cops and one robber on an undirected N-vertex graph G. We prove that the complexity of deciding the winner in the game under optimal play requires Omega (N^{g-o(1)}) time on instances with O(N log^2 N) edges, conditioned on the Strong Exponential Time Hypothesis. Moreover, the problem of calculating the minimum number of cops needed to win the game is 2^{Omega (sqrt{N})},...

Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs

Jérémie Chalopin, Victor Chepoi, Feodor F. Dragan, Guillaume Ducoffe, Abdulhakeem Mohammed & Yann Vaxès
In this paper, we study Gromov hyperbolicity and related parameters, that represent how close (locally) a metric space is to a tree from a metric point of view. The study of Gromov hyperbolicity for geodesic metric spaces can be reduced to the study of graph hyperbolicity. Our main contribution in this note is a new characterization of hyperbolicity for graphs (and for complete geodesic metric spaces). This characterization has algorithmic implications in the field of...

Closure of Resource-Bounded Randomness Notions Under Polynomial-Time Permutations

André Nies & Frank Stephan
An infinite bit sequence is called recursively random if no computable strategy betting along the sequence has unbounded capital. It is well-known that the property of recursive randomness is closed under computable permutations. We investigate analogous statements for randomness notions defined by betting strategies that are computable within resource bounds. Suppose that S is a polynomial time computable permutation of the set of strings over the unary alphabet (identified with the set of natural numbers)....

Registration Year

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

Resource Types

  • Text
  • Software