Search ACM DL

Search Issue

enter search term and/or author name

Section:

**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/2^{k}*k*) 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,...