Search ACM DL

Search Issue

enter search term and/or author name

**On the competitive ratio of evaluating priced functions**

Ferdinando Cicalese, Eduardo Sany Laber

Article No.: 9

DOI: 10.1145/1970392.1970393

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...

**Market equilibrium under separable, piecewise-linear, concave utilities**

Vijay V. Vazirani, Mihalis Yannakakis

Article No.: 10

DOI: 10.1145/1970392.1970394

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...

**Robust principal component analysis?**

Emmanuel J. Candès, Xiaodong Li, Yi Ma, John Wright

Article No.: 11

DOI: 10.1145/1970392.1970395

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,...

**Introduction to JACM invited article**

Victor Vianu

Article No.: 12

DOI: 10.1145/1970392.1970396

**Estimating PageRank on graph streams**

Atish Das Sarma, Sreenivas Gollapudi, Rina Panigrahy

Article No.: 13

DOI: 10.1145/1970392.1970397

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...