The width of a resolution proof is the maximal number of literals in any clause of the proof. The space of a proof is the maximal number of memory cells used if the proof is only allowed to resolve on clauses kept in memory. Both of these measures have previously ... more >>>

For a family X of k-subsets of the set 1...n, let |X| be the cardinality of X and let Gamma(X, mu) be the expected maximum weight of a subset from X when the weights of 1...n are chosen independently at random from a symmetric probability distribution mu on R. We ... more >>>

We study the classification problem {\sc Metric Labeling} and its special case {\sc 0-Extension} in the context of earthmover metrics. Researchers recently proposed using earthmover metrics to get a polynomial time-solvable relaxation of {\sc Metric Labeling}; until now, however, no one knew if the integrality ratio was constant or not, ... more >>>