Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 59 Issue 2, April 2012

On the (im)possibility of obfuscating programs
Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, Ke Yang
Article No.: 6
DOI: 10.1145/2160158.2160159

Informally, an obfuscator O is an (efficient, probabilistic) “compiler” that takes as input a program (or circuit) P and produces a new program O(P) that has the same functionality as P yet is...

The notion of a rational convex program, and an algorithm for the arrow-debreu Nash bargaining game
Vijay V. Vazirani
Article No.: 7
DOI: 10.1145/2160158.2160160

We introduce the notion of a rational convex program (RCP) and we classify the known RCPs into two classes: quadratic and logarithmic. The importance of rationality is that it opens up the possibility of computing an optimal solution to the...

A theory of goal-oriented communication
Oded Goldreich, Brendan Juba, Madhu Sudan
Article No.: 8
DOI: 10.1145/2160158.2160161

We put forward a general theory of goal-oriented communication, where communication is not an end in itself, but rather a means to achieving some goals of the communicating parties. Focusing on goals provides a framework for...

Invited article foreword
Victor Vianu
Article No.: 9
DOI: 10.1145/2160158.2160162

In this issue, the Invited Articles section is comprised of the article “Continuous Sampling from Distributed Streams” by Graham Cormode, Muthu Muthukrishnan, Ke Yi and Qin Zhang. This article was selected from the 29th ACM...

Continuous sampling from distributed streams
Graham Cormode, S. Muthukrishnan, Ke Yi, Qin Zhang
Article No.: 10
DOI: 10.1145/2160158.2160163

A fundamental problem in data management is to draw and maintain a sample of a large data set, for approximate query answering, selectivity estimation, and query planning. With large, streaming data sets, this problem becomes particularly...