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

9 papers · 1 filter

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…