8,805 Works

Amplification with One NP Oracle Query

Thomas Watson
We provide a complete picture of the extent to which amplification of success probability is possible for randomized algorithms having access to one NP oracle query, in the settings of two-sided, one-sided, and zero-sided error. We generalize this picture to amplifying one-query algorithms with q-query algorithms, and we show our inclusions are tight for relativizing techniques.

The Maximum Label Propagation Algorithm on Sparse Random Graphs

Charlotte Knierim, Johannes Lengler, Pascal Pfister, Ulysse Schaller & Angelika Steger
In the Maximum Label Propagation Algorithm (Max-LPA), each vertex draws a distinct random label. In each subsequent round, each vertex updates its label to the label that is most frequent among its neighbours (including its own label), breaking ties towards the larger label. It is known that this algorithm can detect communities in random graphs with planted communities if the graphs are very dense, by converging to a different consensus for each community. In [Kothapalli...

Minimal Paradefinite Logics for Reasoning with Incompleteness and Inconsistency

Ofer Arieli & Arnon Avron
Paradefinite (`beyond the definite') logics are logics that can be used for handling contradictory or partial information. As such, paradefinite logics should be both paraconsistent and paracomplete. In this paper we consider the simplest semantic framework for defining paradefinite logics, consisting of four-valued matrices, and study the better accepted logics that are induced by these matrices.

Touching the 3rd Dimension (Dagstuhl Seminar 12151)

Daniel Keefe, Antonio Krüger, Frank Steinicke & Jean-Baptiste De La Rivière
In recent years interactive visualization of 3D data has become important and widespread due to the requirements of several application areas. However, current user interfaces often lack adequate support for 3D interactions: 2D desktop systems are often limited in cases where natural interaction with 3D content is required, and 3D user interfaces consisting of stereoscopic projections and tracked input devices are rarely adopted by ordinary users. Touch interaction has received considerable attention for 2D interfaces,...

Making "Fast" Atomic Operations Computationally Tractable

Antonio Fernández Anta, Nicolas Nicolaou & Alexandru Popa
Communication overhead is the most commonly used performance metric for the operation complexity of distributed algorithms in message-passing environments. However, aside with communication, many distributed operations utilize complex computations to reach their desired outcomes. Therefore, a most accurate operation latency measure should account of both computation and communication metrics. In this paper we focus on the efficiency of read and write operations in an atomic read/write shared memory emulation in the message-passing environment. We examine...

Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class

Erik D. Demaine, Timothy D. Goodrich, Kyle Kloster, Brian Lavallee, Quanquan C. Liu, Blair D. Sullivan, Ali Vakilian & Andrew Van Der Poel
We develop a framework for generalizing approximation algorithms from the structural graph algorithm literature so that they apply to graphs somewhat close to that class (a scenario we expect is common when working with real-world networks) while still guaranteeing approximation ratios. The idea is to edit a given graph via vertex- or edge-deletions to put the graph into an algorithmically tractable class, apply known approximation algorithms for that class, and then lift the solution to...

THRIFTY: Towards High Reduction In Flow Table memorY

Ali Malik, Benjamin Aziz & Chih-Heng Ke
The rapid evolution of information technology has compelled the ubiquitous systems and computing to adapt with this expeditious development. Because of its rigidity, computer networks failed to meet that evolvement for decades, however, the recently emerged paradigm of software-defined networks gives a glimpse of hope for a new networking architecture that provides more flexibility and adaptability. Fault tolerance is considered one of the key concerns with respect to the software-defined networks dependability. In this paper,...

Approximate Matchings in Massive Graphs via Local Structure (Invited Talk)

Clifford Stein
Finding a maximum matching is a fundamental algorithmic problem and is fairly well understood in traditional sequential computing models. Some modern applications require that we handle massive graphs and hence we need to consider algorithms in models that do not allow the entire input graph to be held in the memory of one computer, or models in which the graph is evolving over time. We introduce a new concept called an "Edge Degree Constrained Subgraph...

The Delta-Framework

Furio Honsell, Luigi Liquori, Claude Stolze & Ivan Scagnetto
We introduce the Delta-framework, LF_Delta, a dependent type theory based on the Edinburgh Logical Framework LF, extended with the strong proof-functional connectives, i.e. strong intersection, minimal relevant implication and strong union. Strong proof-functional connectives take into account the shape of logical proofs, thus reflecting polymorphic features of proofs in formulae. This is in contrast to classical or intuitionistic connectives where the meaning of a compound formula depends only on the truth value or the provability...

On the Number of Variables in Special Classes of Random Lambda-Terms

Bernhard Gittenberger & Isabella Larcher
We investigate the number of variables in two special subclasses of lambda-terms that are restricted by a bound of the number of abstractions between a variable and its binding lambda, and by a bound of the nesting levels of abstractions, respectively. These restrictions are on the one hand very natural from a practical point of view, and on the other hand they simplify the counting problem compared to that of unrestricted lambda-terms in such a...

Listing Induced Steiner Subgraphs as a Compact Way to Discover Steiner Trees in Graphs

Alessio Conte, Roberto Grossi, Mamadou Moustapha Kanté, Andrea Marino, Takeaki Uno & Kunihiro Wasa
This paper investigates induced Steiner subgraphs as a variant of the classical Steiner trees, so as to compactly represent the (exponentially many) Steiner trees sharing the same underlying induced subgraph. We prove that the enumeration of all (inclusion-minimal) induced Steiner subgraphs is harder than the well-known Hypergraph Transversal enumeration problem if the number of terminals is not fixed. When the number of terminals is fixed, we propose a polynomial delay algorithm for listing all induced...

Lightweight Support for Magic Wands in an Automatic Verifier (Artifact)

Malte Schwerhoff & Alexander J. Summers
This artifact is based on Silicon, which is an automatic verification tool for programs written in the Silver Intermediate Verification Language. Silver is designed to natively support permission-based reasoning, in the style of separation logic and similar approaches. Our extension of Silicon provides support for specification and verification of programs using the magic wand operator, which can be used to represent ways to exchange views on the program state, or to represent partial versions of...

Tuning PI controller in non-linear uncertain closed-loop systems with interval analysis

Julien Alexandre Dit Sandretto, Alexandre Chapoutot & Olivier Mullier
The tuning of a PI controller is usually done through simulation, except for few classes of problems, e.g., linear systems. With a new approach for validated integration allowing us to simulate dynamical systems with uncertain parameters, we are able to design guaranteed PI controllers. In practical, we propose a new method to identify the parameters of a PI controller for non-linear plants with bounded uncertain parameters using tools from interval analysis and validated simulation. This...

A Framework for Static Analysis of VHDL Code

Marc Schlickling & Markus Pister
Software in real time systems underlies strict timing constraints. These are among others hard deadlines regarding the worst-case execution time (WCET) of the application. Thus, the computation of a safe and precise WCET is a key issue1 for validating the behavior of safety-critical systems, e.g. the flight control system in avionics or the airbag control software in the automotive industry. Saarland University and AbsInt Angewandte Informatik GmbH have developed a successful approach for computing the...

Succinct Data Structures for Chordal Graphs

J. Ian Munro & Kaiyu Wu
We study the problem of approximate shortest path queries in chordal graphs and give a n log n + o(n log n) bit data structure to answer the approximate distance query to within an additive constant of 1 in O(1) time. We study the problem of succinctly storing a static chordal graph to answer adjacency, degree, neighbourhood and shortest path queries. Let G be a chordal graph with n vertices. We design a data structure...

Recognizing a DOG is Hard, But Not When It is Thin and Unit

William Evans, Mereke Van Garderen, Maarten Löffler & Valentin Polishchuk
We define the notion of disk-obedience for a set of disks in the plane and give results for diskobedient graphs (DOGs), which are disk intersection graphs (DIGs) that admit a planar embedding with vertices inside the corresponding disks. We show that in general it is hard to recognize a DOG, but when the DIG is thin and unit (i.e., when the disks are unit disks), it can be done in linear time.

Locating User Interface Concepts in Source Code

Matúš Sulír & Jaroslav Porubän
Developers often start their work by exploring a graphical user interface (GUI) of a program. They spot a textual label of interest in the GUI and try to find it in the source code, as a straightforward way of feature location. We performed a study on four Java applications, asking a simple question: Are strings displayed in the GUI of a running program present in its source code? We came to a conclusion that the...

Settlement Fund Circulation Problem

Hitoshi Hayakawa, Toshimasa Ishii, Hirotaka Ono & Yushi Uno
In the economic activities, the central bank has an important role to cover payments of banks, when they are short of funds to clear their debts. For this purpose, the central bank timely puts funds so that the economic activities go smooth. Since payments in this mechanism are processed sequentially, the total amount of funds put by the central bank critically depends on the order of the payments. Then an interest goes to the amount...

A Negative Conjunctive Query is Easy if and only if it is Beta-Acyclic

Johann Brault-Baron
It is known that the data complexity of a Conjunctive Query (CQ) is determined *only* by the way its variables are shared between atoms, reflected by its hypergraph. In particular, Yannakakis [Yannakakis VLDB'81,Beeri/Fagin/Maier/Yannakakis JACM'83] proved that a CQ is decidable in linear time when it is alpha-acyclic, i.e. its hypergraph is alpha-acyclic; Bagan et al. [Bagan/Durand/Grandjean CSL'07] even state: * Any CQ is decidable in linear time iff it is alpha-acyclic. (under certain hypotheses) (By...

Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication

Debarati Das, Michal Koucký & Michael Saks
In this paper we propose models of combinatorial algorithms for the Boolean Matrix Multiplication (BMM), and prove lower bounds on computing BMM in these models. First, we give a relatively relaxed combinatorial model which is an extension of the model by Angluin (1976), and we prove that the time required by any algorithm for the BMM is at least Omega(n^3 / 2^{O( sqrt{ log n })}). Subsequently, we propose a more general model capable of...

Periods in Subtraction Games (Keynote Speakers)

Bret Benesh, Jamylle Carter, Deidra A. Coleman, Douglas G. Crabill, Jack H. Good, Michael A. Smith, Jennifer Travis & Mark Daniel Ward
We discuss the structure of periods in subtraction games. In particular, we discuss ways that a computational approach yields insights to the periods that emerge in the asymptotic structure of these combinatorial games.

On Improved Degree Lower Bounds for Polynomial Approximation

Srikanth Srinivasan
A polynomial P in F[X_1,...,X_n] is said to epsilon-approximate a boolean function F:{0,1}^n -> {0,1} under distribution D over {0,1}^n if for a random x chosen according to distribution D, the probability that P(x) is not equal to F(x) is at most epsilon. Smolensky (1987) showed that for any constant distinct primes p and q, any polynomial P in F_p[x_1,...,x_n] that (1/2q - Omega(1))-approximates the boolean function MOD_q:{0,1}^n->{0,1} -- which accepts its input iff the...

A New Hybrid Approach on WCET Analysis for Real-Time Systems Using Machine Learning

Thomas Huybrechts, Siegfried Mercelis & Peter Hellinckx
The notion of the Worst-Case Execution Time (WCET) allows system engineers to create safe real-time systems. This value is used to schedule all software tasks before their deadlines. Failing these deadlines will cause catastrophic events, e.g. vehicle crashes, failing to detect dangerous anomalies, etc. Different analysis methodologies exist to determine the WCET. However, these methods do not provide early insight in the WCET during development. Therefore, pessimistic assumptions are made by system designers resulting in...

Algorithmic Complexity for the Realization of an Effective Subshift By a Sofic

Mathieu Sablik & Michael Schraudner
Realization of d-dimensional effective subshifts as projective sub-actions of d + d'-dimensional sofic subshifts for d' >= 1 is now well known [Hochman, 2009; Durand/Romashchenko/Shen, 2012; Aubrun/Sablik, 2013]. In this paper we are interested in qualitative aspects of this realization. We introduce a new topological conjugacy invariant for effective subshifts, the speed of convergence, in view to exhibit algorithmic properties of these subshifts in contrast to the usual framework that focuses on undecidable properties.

Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible

Zachary Abel, Jeffrey Bosboom, Erik D. Demaine, Linus Hamilton, Adam Hesterberg, Justin Kopinsky, Jayson Lynch & Mikhail Rudoy
We analyze the computational complexity of the many types of pencil-and-paper-style puzzles featured in the 2016 puzzle video game The Witness. In all puzzles, the goal is to draw a path in a rectangular grid graph from a start vertex to a destination vertex. The different puzzle types place different constraints on the path: preventing some edges from being visited (broken edges); forcing some edges or vertices to be visited (hexagons); forcing some cells to...

Registration Year

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

Resource Types

  • Text
  • Software