Institute of Theoretical Computer Science

output

20052022

most citedThe Uncertainty Principle in the Presence of Quantum Memory

850 citations

researchers with a paper here

Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.

collaborating institutions

Showing 2011Show all

11 papers · 1 filter

cs.DC2011

The Efficiency of MapReduce in Parallel External Memory

Gero Greiner, Riko Jacob

Since its introduction in 2004, the MapReduce framework has become one of the standard approaches in massive distributed and parallel computation. In contrast to its intensive use…

math.OC2011

A Polynomial-Time Algorithm for the Tridiagonal and Hessenberg P-Matrix Linear Complementarity Problem

Bernd Gärtner, Markus Sprecher

We give a polynomial-time dynamic programming algorithm for solving the linear complementarity problem with tridiagonal or, more generally, Hessenberg P-matrices. We briefly review…

q-bio.MN2011★ 1 cited

Global parameter identification of stochastic reaction networks from single trajectories

Christian L. Muller, Rajesh Ramaswamy, Ivo F. Sbalzarini

We consider the problem of inferring the unknown parameters of a stochastic biochemical network model from a single measured time-course of the concentration of some of the involve…

math.CO2011★ 15 cited

Construction of 2-factors in the middle layer of the discrete cube

Torsten Mütze, Franziska Weber

Define the middle layer graph as the graph whose vertex set consists of all bitstrings of length $2 n + 1$ that have exactly $n$ or $n + 1$ entries equal to 1, with an edge between any…

cs.DM2011★ 4 cited

Counting Plane Graphs: Perfect Matchings, Spanning Cycles, and Kasteleyn's Technique

Micha Sharir, Adam Sheffer, Emo Welzl

We derive improved upper bounds on the number of crossing-free straight-edge spanning cycles (also known as Hamiltonian tours and simple polygonizations) that can be embedded over…

math.CO2011★ 3 cited

On globally sparse Ramsey graphs

Torsten Mütze, Ueli Peter

We say that a graph $G$ has the Ramsey property w.r.t.\ some graph $F$ and some integer $r \geq 2$ , or $G$ is $(F, r)$ -Ramsey for short, if any $r$ -coloring of the edges of $G$ conta…

cs.NE2011

Black-Box Complexities of Combinatorial Problems

Benjamin Doerr, Timo Kötzing, Johannes Lengler +1

Black-box complexity is a complexity theoretic measure for how difficult a problem is to be optimized by a general purpose optimization algorithm. It is thus one of the few means t…

math.CO2011★ 3 cited

Coloring random graphs online without creating monochromatic subgraphs

Torsten Mütze, Thomas Rast, Reto Spöhel

Consider the following random process: The vertices of a binomial random graph $G_{n, p}$ are revealed one by one, and at each step only the edges induced by the already revealed ve…

math.CO2011

On the path-avoidance vertex-coloring game

Torsten Mütze, Reto Spöhel

For any graph $F$ and any integer $r \geq 2$ , the \emph{online vertex-Ramsey density of $F$ and $r$ }, denoted $m^{*} (F, r)$ , is a parameter defined via a deterministic two-player Ramse…

math.CO2011★ 4 cited

On Gromov's Method of Selecting Heavily Covered Points

Jiří Matoušek, Uli Wagner

A result of Boros and Füredi ( $d = 2$ ) and of Bárány (arbitrary $d$ ) asserts that for every $d$ there exists $c_{d} > 0$ such that for every $n$ -point set $P \subset R^{d}$ , some point of…

cs.LO2011★ 25 cited

Analysing the Control Software of the Compact Muon Solenoid Experiment at the Large Hadron Collider

Yi-Ling Hwong, Vincent J. J. Kusters, Tim A. C. Willemse

The control software of the CERN Compact Muon Solenoid experiment contains over 30,000 finite state machines. These state machines are organised hierarchically: commands are sent d…