Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 58 Issue 4, July 2011

Online geometric reconstruction
Bernard Chazelle, C. Seshadhri
Article No.: 14
DOI: 10.1145/1989727.1989728

We investigate a new class of geometric problems based on the idea of online error correction. Suppose one is given access to a large geometric dataset though a query mechanism; for example, the dataset could be a terrain and a query might ask for...

Probabilistic data exchange
Ronald Fagin, Benny Kimelfeld, Phokion G. Kolaitis
Article No.: 15
DOI: 10.1145/1989727.1989729

The work reported here lays the foundations of data exchange in the presence of probabilistic data. This requires rethinking the very basic concepts of traditional data exchange, such as solution, universal solution, and the certain answers of...

Invited articles foreword
Victor Vianu
Article No.: 16
DOI: 10.1145/1989727.1989730

XPath evaluation in linear time
Mikołaj Bojańczyk, Paweł Parys
Article No.: 17
DOI: 10.1145/1989727.1989731

We consider a fragment of XPath 1.0, where attribute and text values may be compared. We show that for any unary query ϕ in this fragment, the set of nodes that satisfy the query in a document t can be calculated in time...

Breaking the O(n2) bit barrier: Scalable byzantine agreement with an adaptive adversary
Valerie King, Jared Saia
Article No.: 18
DOI: 10.1145/1989727.1989732

We describe an algorithm for Byzantine agreement that is scalable in the sense that each processor sends only Õ(&sqrt;n) bits, where n is the total number of processors. Our algorithm succeeds with high probability against an...