Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 58 Issue 1, December 2010

Invited articles section foreword
Victor Vianu
Article No.: 1
DOI: 10.1145/1870103.1870104

Epistemic privacy
Alexandre Evfimievski, Ronald Fagin, David Woodruff
Article No.: 2
DOI: 10.1145/1870103.1870105

We present a novel definition of privacy in the framework of offline (retroactive) database query auditing. Given information about the database, a description of sensitive data, and assumptions about users' prior knowledge, our goal is to...

Approximation algorithms for restless bandit problems
Sudipto Guha, Kamesh Munagala, Peng Shi
Article No.: 3
DOI: 10.1145/1870103.1870106

The restless bandit problem is one of the most well-studied generalizations of the celebrated stochastic multi-armed bandit (MAB) problem in decision theory. In its ultimate generality, the restless bandit problem is known to be PSPACE-Hard...

XML with incomplete information
Pablo Barceló, Leonid Libkin, Antonella Poggi, Cristina Sirangelo
Article No.: 4
DOI: 10.1145/1870103.1870107

We study models of incomplete information for XML, their computational properties, and query answering. While our approach is motivated by the study of relational incompleteness, incomplete information in XML documents may appear not only as null...