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: Arithmetic 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: Arithmetic Complexity

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: Arithmetic Complexity

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: Arithmetic Complexity

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: Arithmetic Complexity

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: Arithmetic Complexity

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: Arithmetic Complexity

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

Section: Arithmetic Complexity

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,...