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 cs.DSShow all

5 papers · 1 filter

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…

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…

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…

cs.DS2012★ 52 cited

Computing Lempel-Ziv Factorization Online

Tatiana Starikovskaya

We present an algorithm which computes the Lempel-Ziv factorization of a word of length on an alphabet of size online in the following sense: it reads starting…

cs.DS2010★ 1 cited

Minimum and maximum against k lies

Michael Hoffmann, Jiří Matoušek, Yoshio Okamoto +1

A neat 1972 result of Pohl asserts that [3n/2]-2 comparisons are sufficient, and also necessary in the worst case, for finding both the minimum and the maximum of an n-element tota…