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 2011 · math.COShow all

5 papers · 2 filters

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…

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…

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…