Issue Downloads
On the competitive ratio of evaluating priced functions
Let f be a function on a set of variables V. For each x ∈ V, let c(x) be the cost of reading the value of x. An algorithm for evaluating f is a strategy for adaptively identifying and reading a set of variables U ⊆ V whose values uniquely determine the ...
Market equilibrium under separable, piecewise-linear, concave utilities
We consider Fisher and Arrow--Debreu markets under additively separable, piecewise-linear, concave utility functions and obtain the following results. For both market models, if an equilibrium exists, there is one that is rational and can be written ...
Robust principal component analysis?
This article is about a curious phenomenon. Suppose we have a data matrix, which is the superposition of a low-rank component and a sparse component. Can we recover each component individually? We prove that under some suitable assumptions, it is ...
Estimating PageRank on graph streams
This article focuses on computations on large graphs (e.g., the web-graph) where the edges of the graph are presented as a stream. The objective in the streaming model is to use small amount of memory (preferably sub-linear in the number of nodes n) and ...