enter search term and/or author name
Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations
Kousha Etessami, Mihalis Yannakakis
Article No.: 1
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...
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...
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
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...