Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 63 Issue 2, May 2016

Section: Economics and Computation

Bayesian Combinatorial Auctions
George Christodoulou, Annamária Kovács, Michael Schapira
Article No.: 11
DOI: 10.1145/2835172

We study the following simple Bayesian auction setting: m items are sold to n selfish bidders in m independent second-price auctions. Each bidder has a private valuation function that specifies his or her complex...

Section: Analysis of Algorithms

A Combinatorial, Primal-Dual Approach to Semidefinite Programs
Sanjeev Arora, Satyen Kale
Article No.: 12
DOI: 10.1145/2837020

Semidefinite programs (SDPs) have been used in many recent approximation algorithms. We develop a general primal-dual approach to solve SDPs using a generalization of the well-known multiplicative weights update rule to symmetric matrices. For a...

Section: Distributed Computing

Byzantine Agreement in Expected Polynomial Time
Valerie King, Jared Saia
Article No.: 13
DOI: 10.1145/2837019

We address the problem of Byzantine agreement, to bring processors to agreement on a bit in the presence of a strong adversary. This adversary has full information of the state of all processors, the ability to control message scheduling in...

Section: Database Systems and Theory

Querying Graphs with Data
Leonid Libkin, Wim Martens, Domagoj Vrgoč
Article No.: 14
DOI: 10.1145/2850413

Graph databases have received much attention as of late due to numerous applications in which data is naturally viewed as a graph; these include social networks, RDF and the Semantic Web, biological databases, and many others. There are many...

Section: Complexity Theory

Almost Optimal Local Graph Clustering Using Evolving Sets
Reid Andersen, Shayan Oveis Gharan, Yuval Peres, Luca Trevisan
Article No.: 15
DOI: 10.1145/2856030

Spectral partitioning is a simple, nearly linear time algorithm to find sparse cuts, and the Cheeger inequalities provide a worst-case guarantee for the quality of the approximation found by the algorithm. A local graph partitioning...

A New Kind of Tradeoffs in Propositional Proof Complexity
Alexander Razborov
Article No.: 16
DOI: 10.1145/2858790

We exhibit an unusually strong tradeoff in propositional proof complexity that significantly deviates from the established pattern of almost all results of this kind. Namely, restrictions on one resource (width, in our case) imply an increase in...

Section: Distributed Algorithms

Local Computation: Lower and Upper Bounds
Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer
Article No.: 17
DOI: 10.1145/2742012

The question of what can be computed, and how efficiently, is at the core of computer science. Not surprisingly, in distributed systems and networking research, an equally fundamental question is what can be computed in a distributed...

Section: Invited Articles Section

Invited Articles Foreword
Eva Tardos
Article No.: 18
DOI: 10.1145/2896919

Section: Logic and Computation

Computational Complexity of Quantum Satisfiability
Christian Herrmann, Martin Ziegler
Article No.: 19
DOI: 10.1145/2869073

We connect both discrete and algebraic complexity theory with the satisfiability problem in certain non-Boolean lattices.

Specifically, quantum logic was introduced in 1936 by Garrett Birkhoff and John von Neumann as a framework for...