Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 61 Issue 5, August 2014

Section: Coding Theory

High-rate codes with sublinear-time decoding
Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin
Article No.: 28
DOI: 10.1145/2629416

Locally decodable codes are error-correcting codes that admit efficient decoding algorithms; any bit of the original message can be recovered by looking at only a small number of locations of a corrupted codeword. The tradeoff between the rate of...

Section: Cryptographic Protocols

Privacy amplification with asymptotically optimal entropy loss
Nishanth Chandran, Bhavana Kanukurthi, Rafail Ostrovsky, Leonid Reyzin
Article No.: 29
DOI: 10.1145/2630064

We study the problem of “privacy amplification”: key agreement between two parties who both know a weak secret w, such as a password. (Such a setting is ubiquitous on the internet, where passwords are the most commonly used...

Section: Distributed Algorithms

Fault-tolerant algorithms for tick-generation in asynchronous logic: Robust pulse generation
Danny Dolev, Matthias Függer, Ulrich Schmid, Christoph Lenzen
Article No.: 30
DOI: 10.1145/2560561

Today’s hardware technology presents a new challenge in designing robust systems. Deep submicron VLSI technology introduces transient and permanent faults that were never considered in low-level system designs in the past. Still, robustness...

Section: Invited Articles Section

Invited article foreword
Victor Vianu
Article No.: 31
DOI: 10.1145/2656280

Section: Database Systems and Theory

Transducing Markov sequences
Benny Kimelfeld, Christopher Ré
Article No.: 32
DOI: 10.1145/2630065

A Markov sequence is a basic statistical model representing uncertain sequential data, and it is used within a plethora of applications, including speech recognition, image processing, computational biology, radio-frequency identification (RFID),...