enter search term and/or author name
(Almost) Tight bounds and existence theorems for single-commodity confluent flows
Jiangzhuo Chen, Robert D. Kleinberg, László Lovász, Rajmohan Rajaraman, Ravi Sundaram, Adrian Vetta
Article No.: 16
A flow of a commodity is said to be confluent if at any node all the flow of the commodity leaves along a single edge. In this article, we study single-commodity confluent flow problems, where we need to route given node demands to a single...
A new look at survey propagation and its generalizations
Elitza Maneva, Elchanan Mossel, Martin J. Wainwright
Article No.: 17
This article provides a new conceptual perspective on survey propagation, which is an iterative algorithm recently introduced by the statistical physics community that is very effective in solving random k-SAT problems even with...
Optimal pants decompositions and shortest homotopic cycles on an orientable surface
Éric Colin De Verdière, Francis Lazarus
Article No.: 18
We consider the problem of finding a shortest cycle (freely) homotopic to a given simple cycle on a compact, orientable surface. For this purpose, we use a pants decomposition of the surface: a set of disjoint simple cycles that cut the...
On deciding well-definedness for query languages on trees
Article No.: 19
The well-definedness problem for a database query language consists of checking, given an expression and an input type, that the expression never yields a runtime error on any input adhering to the input type. In this article, we study the...
Periodicity and unbordered words: A proof of the extended duval conjecture
Tero Harju, Dirk Nowotka
Article No.: 20
The relationship between the length of a word and the maximum length of its unbordered factors is investigated in this article. Consider a finite word w of length n. We call a word bordered if it has a proper prefix, which is...
Sampling from large matrices: An approach through geometric functional analysis
Mark Rudelson, Roman Vershynin
Article No.: 21
We study random submatrices of a large matrix A. We show how to approximately compute A from its random submatrix of the smallest possible size O(rlog r) with a small error in the spectral norm, where r...