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

60 papers

math.CO2022

On approximating the rank of graph divisors

Kristóf Bérczi, Hung P. Hoang, Lilla Tóthmérész

Baker and Norine initiated the study of graph divisors as a graph-theoretic analogue of the Riemann-Roch theory for Riemann surfaces. One of the key concepts of graph divisor theor…

cs.DM2019★ 20 cited

Fake news and rumors: a trigger for proliferation or fading away

Ahad N. Zehmakan, Serge Galam

The dynamics of fake news and rumor spreading is investigated using a model with three kinds of agents who are respectively the Seeds, the Agnostics and the Others. While Seeds are…

cs.DS2018★ 6 cited

Smoothed Analysis of Discrete Tensor Decomposition and Assemblies of Neurons

Nima Anari, Constantinos Daskalakis, Wolfgang Maass +3

We analyze linear independence of rank one tensors produced by tensor powers of randomly perturbed vectors. This enables efficient decomposition of sums of high-order tensors. Our…

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…

cs.DS2016★ 25 cited

Collaborative Delivery with Energy-Constrained Mobile Robots

Andreas Bärtschi, Jérémie Chalopin, Shantanu Das +5

We consider the problem of collectively delivering some message from a specified source to a designated target location in a graph, using multiple mobile agents. Each agent has a l…

math.CO2016★ 2 cited

Colorability Saturation Games

Ralph Keusch

We consider the following two-player game: Maxi and Mini start with the empty graph on $n$ vertices and take turns, always adding one additional edge to the graph such that the chr…

math.PR2016

Most edge-orderings of $K_{n}$ have maximal altitude

Anders Martinsson

Suppose the edges of the complete graph on $n$ vertices are assigned a uniformly chosen random ordering. Let $X$ denote the corresponding number of Hamiltonian paths that are incre…

math.CO2015★ 2 cited

Almost-spanning universality in random graphs

David Conlon, Asaf Ferber, Rajko Nenadov +1

A graph $G$ is said to be $H (n, Δ)$ -universal if it contains every graph on $n$ vertices with maximum degree at most $Δ$ . It is known that for any $ε > 0$ and any…

math.OC2014

On low complexity Acceleration Techniques for Randomized Optimization: Supplementary Online Material

Sebastian U. Stich

Recently it was shown by Nesterov (2011) that techniques form convex optimization can be used to successfully accelerate simple derivative-free randomized optimization methods. The…

math.CO2014

On the threshold for the Maker-Breaker $H$ -game

Rajko Nenadov, Angelika Steger, Miloš Stojaković

We study the Maker-Breaker $H$ -game played on the edge set of the random graph $G_{n, p}$ . In this game two players, Maker and Breaker, alternately claim unclaimed edges of $G_{n,p}…

math.CO2014★ 2 cited

Higher Dimensional Discrete Cheeger Inequalities

Anna Gundert, May Szedlák

For graphs there exists a strong connection between spectral and combinatorial expansion properties. This is expressed, e.g., by the discrete Cheeger inequality, the lower bound of…

cs.CG2013★ 1 cited

Counting Triangulations and other Crossing-free Structures via Onion Layers

Victor Alvarez, Karl Bringmann, Radu Curticapean +1

Let $P$ be a set of $n$ points in the plane. A crossing-free structure on $P$ is a plane graph with vertex set $P$ . Examples of crossing-free structures include triangulations of $…

math.CO2013★ 3 cited

Universality of random graphs and rainbow embedding

Asaf Ferber, Rajko Nenadov, Ueli Peter

In this paper we show how to use simple partitioning lemmas in order to embed spanning graphs in a typical member of $G (n, p)$ . Let the \emph{maximum density} of a graph $H$ be the…

math.CO2013★ 1 cited

Generating random graphs in biased Maker-Breaker games

Asaf Ferber, Michael Krivelevich, Humberto Naves

We present a general approach connecting biased Maker-Breaker games and problems about local resilience in random graphs. We utilize this approach to prove new results and also to…

stat.ML2013★ 3 cited

Learning Non-Parametric Basis Independent Models from Point Queries via Low-Rank Methods

Hemant Tyagi, Volkan Cevher

We consider the problem of learning multi-ridge functions of the form f(x) = g(Ax) from point evaluations of f. We assume that the function f is defined on an l_2-ball in R^d, g is…

math.PR2013★ 1 cited

Balls into bins via local search: cover time and maximum load

Karl Bringmann, Thomas Sauerwald, Alexandre Stauffer +1

We study a natural process for allocating m balls into n bins that are organized as the vertices of an undirected graph G. Balls arrive one at a time. When a ball arrives, it first…

math.MG2013

Curves in R^d intersecting every hyperplane at most d+1 times

Imre Barany, Jiri Matousek, Attila Por

By a curve in R^d we mean a continuous map gamma:I -> R^d, where I is a closed interval. We call a curve gamma in R^d at most k crossing if it intersects every hyperplane at most k…

math.MG2013★ 2 cited

Large Shadows from Sparse Inequalities

Bernd Gärtner, Christian Helbling, Yoshiki Ota +1

The $d$ -dimensional Goldfarb cube is a polytope with the property that all its $2^{d}$ vertices appear on some \emph{shadow} of it (projection onto a 2-dimensional plane). The Goldfa…

math.CO2013★ 2 cited

Lower bounds on geometric Ramsey functions

Marek Eliáš, Jiří Matoušek, Edgardo Roldán-Pensado +1

We continue a sequence of recent works studying Ramsey functions for semialgebraic predicates in $R^{d}$ . A $k$ -ary semialgebraic predicate $Φ (x_{1}, \dots, x_{k})$ on $\mathbb{R…

cs.DS2013

Counting approximately-shortest paths in directed acyclic graphs

Matúš Mihalák, Rastislav Šrámek, Peter Widmayer

Given a directed acyclic graph with positive edge-weights, two vertices s and t, and a threshold-weight L, we present a fully-polynomial time approximation-scheme for the problem o…

math.CO2012★ 1 cited

Counting and packing Hamilton cycles in dense graphs and oriented graphs

Asaf Ferber, Michael Krivelevich, Benny Sudakov

We present a general method for counting and packing Hamilton cycles in dense graphs and oriented graphs, based on permanent estimates. We utilize this approach to prove several ex…

math.OC2012★ 2 cited

Variable Metric Random Pursuit

Sebastian U. Stich, Christian L. Müller, Bernd Gärtner

We consider unconstrained randomized optimization of smooth convex objective functions in the gradient-free setting. We analyze Random Pursuit (RP) algorithms with fixed (F-RP) and…