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 2017Show all

3 papers · 1 filter

math.CO2017

A new upper bound on the game chromatic index of graphs

Ralph Keusch

We study the two-player game where Maker and Breaker alternately color the edges of a given graph $G$ with $k$ colors such that adjacent edges never get the same color. Maker's goa…

math.CO2017★ 2 cited

Local resilience of an almost spanning $k$ -cycle in random graphs

Nemanja Škorić, Angelika Steger, Miloš Trujić

The famous Pósa-Seymour conjecture, confirmed in 1998 by Komlós, Sárközy, and Szemerédi, states that for any $k \geq 2$ , every graph on $n$ vertices with minimum degree $kn/(k + 1)…

math.PR2017★ 8 cited

A linear threshold for uniqueness of solutions to random jigsaw puzzles

Anders Martinsson

We consider a problem introduced by Mossel and Ross [Shotgun assembly of labeled graphs, arXiv:1504.07682]. Suppose a random $n \times n$ jigsaw puzzle is constructed by independent…

A new upper bound on the game chromatic index of graphs

Local resilience of an almost spanning k-cycle in random graphs

A linear threshold for uniqueness of solutions to random jigsaw puzzles

Local resilience of an almost spanning $k$ -cycle in random graphs