Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 61 Issue 6, November 2014

Section: Arithmetic Complexity

Approaching the Chasm at Depth Four
Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi
Article No.: 33
DOI: 10.1145/2629541

Agrawal and Vinay [2008], Koiran [2012], and Tavenas [2013] have recently shown that an exp (ω(√n log n)) lower bound for depth four homogeneous circuits computing the permanent with bottom layer of × gates having...

Section: Communication Complexity

Communication Lower Bounds Using Directional Derivatives
Alexander A. Sherstov
Article No.: 34
DOI: 10.1145/2629334

We study the set disjointness problem in the most powerful model of bounded-error communication, the k-party randomized number-on-the-forehead model. We show that set disjointness requires Ω(√n/2kk) bits...

Section: Communication Theory

Fast Interactive Coding against Adversarial Noise
Zvika Brakerski, Yael Tauman Kalai, Moni Naor
Article No.: 35
DOI: 10.1145/2661628

Consider two parties who wish to communicate in order to execute some interactive protocol π. However, the communication channel between them is noisy: An adversary sees everything that is transmitted over the channel and can change a constant...

Section: Distributed Computing

SKIP+: A Self-Stabilizing Skip Graph
Riko Jacob, Andrea Richa, Christian Scheideler, Stefan Schmid, Hanjo Täubig
Article No.: 36
DOI: 10.1145/2629695

Peer-to-peer systems rely on a scalable overlay network that enables efficient routing between its members. Hypercubic topologies facilitate such operations while each node only needs to connect to a small number of other nodes. In contrast to...

Section: Graph Theory and Algorithms

Multiway Spectral Partitioning and Higher-Order Cheeger Inequalities
James R. Lee, Shayan Oveis Gharan, Luca Trevisan
Article No.: 37
DOI: 10.1145/2665063

A basic fact in spectral graph theory is that the number of connected components in an undirected graph is equal to the multiplicity of the eigenvalue zero in the Laplacian matrix of the graph. In particular, the graph is disconnected if and only...

Section: Machine Learning

Privacy Aware Learning
John C. Duchi, Michael I. Jordan, Martin J. Wainwright
Article No.: 38
DOI: 10.1145/2666468

We study statistical risk minimization problems under a privacy model in which the data is kept confidential even from the learner. In this local privacy framework, we establish sharp upper and lower bounds on the convergence rates of statistical...

Section: Visual Cryptography and Security

A New Approach to Image Sharing with High-Security Threshold Structure
Xiaojing Wang, Qizhao Yuan, Hongliang Cai, Jiajia Fang
Article No.: 39
DOI: 10.1145/2666470

Image sharing is an attractive research subject in computer image techniques and in the information security field. This article presents a novel scheme of image sharing with a (t, n) high-security threshold structure. The scheme can...

Section: Invited Articles Section

Invited Article Foreword
Victor Vianu
Article No.: 40
DOI: 10.1145/2684458

Section: Computer-Aided Verification

Efficient Analysis of Probabilistic Programs with an Unbounded Counter
Tomás Brázdil, Stefan Kiefer, Antonín Kŭcera
Article No.: 41
DOI: 10.1145/2629599

We show that a subclass of infinite-state probabilistic programs that can be modeled by probabilistic one-counter automata (pOC) admits an efficient quantitative analysis. We start by establishing a powerful link between pOC and martingale theory,...