Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 58 Issue 6, December 2011

Complete Fairness in Secure Two-Party Computation
S. Dov Gordon, Carmit Hazay, Jonathan Katz, Yehuda Lindell
Article No.: 24
DOI: 10.1145/2049697.2049698

In the setting of secure two-party computation, two mutually distrusting parties wish to compute some function of their inputs while preserving, to the extent possible, various security properties such as privacy, correctness, and more. One...

Truthful and Near-Optimal Mechanism Design via Linear Programming
Ron Lavi, Chaitanya Swamy
Article No.: 25
DOI: 10.1145/2049697.2049699

We give a general technique to obtain approximation mechanisms that are truthful in expectation. We show that for packing domains, any α-approximation algorithm that also bounds the integrality gap of the LP relaxation of the problem...

Compositional Shape Analysis by Means of Bi-Abduction
Cristiano Calcagno, Dino Distefano, Peter W. O’Hearn, Hongseok Yang
Article No.: 26
DOI: 10.1145/2049697.2049700

The accurate and efficient treatment of mutable data structures is one of the outstanding problem areas in automatic program verification and analysis. Shape analysis is a form of program analysis that attempts to infer descriptions of the data...

Randomized Shellsort: A Simple Data-Oblivious Sorting Algorithm
Michael T. Goodrich
Article No.: 27
DOI: 10.1145/2049697.2049701

In this article, we describe a randomized Shellsort algorithm. This algorithm is a simple, randomized, data-oblivious version of the Shellsort algorithm that always runs in O(n log n) time and succeeds in sorting any...

New Constructive Aspects of the Lovász Local Lemma
Bernhard Haeupler, Barna Saha, Aravind Srinivasan
Article No.: 28
DOI: 10.1145/2049697.2049702

The Lovász Local Lemma (LLL) is a powerful tool that gives sufficient conditions for avoiding all of a given set of “bad” events, with positive probability. A series of results have provided algorithms to efficiently construct...

Invited Article Foreword
Victor Vianu
Article No.: 29
DOI: 10.1145/2049697.2049703

Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous
Article No.: 30
DOI: 10.1145/2049697.2049704

This work considers the quantum interactive proof system model of computation, which is the (classical) interactive proof system model’s natural quantum computational analogue. An exact characterization of the expressive power of quantum...