ACM DL

Journal of the ACM (JACM)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of the ACM (JACM), Volume 56 Issue 1, January 2009

Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations
Kousha Etessami, Mihalis Yannakakis
Article No.: 1
DOI: 10.1145/1462153.1462154

We define Recursive Markov Chains (RMCs), a class of finitely presented denumerable Markov chains, and we study algorithms for their analysis. Informally, an RMC consists of a collection of finite-state Markov chains with the ability to...

The complexity of online memory checking
Moni Naor, Guy N. Rothblum
Article No.: 2
DOI: 10.1145/1462153.1462155

We consider the problem of storing a large file on a remote and unreliable server. To verify that the file has not been corrupted, a user could store a small private (randomized) “fingerprint” on his own computer. This is the setting...

Evolvability
Leslie G. Valiant
Article No.: 3
DOI: 10.1145/1462153.1462156

Living organisms function in accordance with complex mechanisms that operate in different ways depending on conditions. Darwin's theory of evolution suggests that such mechanisms evolved through variation guided by natural selection. However,...

Single-value combinatorial auctions and algorithmic implementation in undominated strategies
Moshe Babaioff, Ron Lavi, Elan Pavlov
Article No.: 4
DOI: 10.1145/1462153.1462157

In this article, we are interested in general techniques for designing mechanisms that approximate the social welfare in the presence of selfish rational behavior. We demonstrate our results in the setting of Combinatorial Auctions (CA). Our first...