Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 59 Issue 3, June 2012

New Techniques for Noninteractive Zero-Knowledge
Jens Groth, Rafail Ostrovsky, Amit Sahai
Article No.: 11
DOI: 10.1145/2220357.2220358

Noninteractive zero-knowledge (NIZK) proof systems are fundamental primitives used in many cryptographic constructions, including public-key encryption secure against chosen ciphertext attack, digital signatures, and various other cryptographic...

An Efficient Rigorous Approach for Identifying Statistically Significant Frequent Itemsets
Adam Kirsch, Michael Mitzenmacher, Andrea Pietracaprina, Geppino Pucci, Eli Upfal, Fabio Vandin
Article No.: 12
DOI: 10.1145/2220357.2220359

As advances in technology allow for the collection, storage, and analysis of vast amounts of data, the task of screening and assessing the significance of discovered patterns is becoming a major challenge in data mining applications. In this work,...

Defining Fairness in Reactive and Concurrent Systems
Hagen Völzer, Daniele Varacca
Article No.: 13
DOI: 10.1145/2220357.2220360

We define when a linear-time temporal property is a fairness property with respect to a given system. This captures the essence shared by most fairness assumptions that are used in the specification and verification of reactive and...

The Power of Simple Tabulation Hashing
Mihai Pǎtraşcu, Mikkel Thorup
Article No.: 14
DOI: 10.1145/2220357.2220361

Randomized algorithms are often enjoyed for their simplicity, but the hash functions used to yield the desired theoretical guarantees are often neither simple nor practical. Here we show that the simplest possible tabulation hashing provides...

Invited Article Foreword
Victor Vianu
Article No.: 15
DOI: 10.1145/2220357.2220362

Size and Treewidth Bounds for Conjunctive Queries
Georg Gottlob, Stephanie Tien Lee, Gregory Valiant, Paul Valiant
Article No.: 16
DOI: 10.1145/2220357.2220363

This article provides new worst-case bounds for the size and treewith of the result Q(D) of a conjunctive query Q applied to a database D. We derive bounds for the result size |Q(D)| in terms of structural...