Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 62 Issue 4, August 2015

Section: Complexity Theory

Robust Satisfiability of Systems of Equations
Peter Franek, Marek Krčál
Article No.: 26
DOI: 10.1145/2751524

We study the problem of robust satisfiability of systems of nonlinear equations, namely, whether for a given continuous function f:K → Rn on a finite simplicial complex K and α>0, it holds that each...

Section: Complexity Theory

Delegating Computation: Interactive Proofs for Muggles
Shafi Goldwasser, Yael Tauman Kalai, Guy N. Rothblum
Article No.: 27
DOI: 10.1145/2699436

In this work we study interactive proofs for tractable languages. The (honest) prover should be efficient and run in polynomial time or, in other words, a “muggle”.1 The verifier should be super-efficient and run in nearly linear time....

Section: Complexity Theory

Algorithmic Applications of Baur-Strassen’s Theorem: Shortest Cycles, Diameter, and Matchings
Marek Cygan, Harold N. Gabow, Piotr Sankowski
Article No.: 28
DOI: 10.1145/2736283

Consider a directed or an undirected graph with integral edge weights from the set [-W, W], that does not contain negative weight cycles. In this article, we introduce a general framework for solving problems on such graphs using matrix...

Section: Complexity Theory

Invited Articles Foreword

Article No.: 29
DOI: 10.1145/2809927

Section: Complexity Theory

Upper Bounds for Newton’s Method on Monotone Polynomial Systems, and P-Time Model Checking of Probabilistic One-Counter Automata
Alistair Stewart, Kousha Etessami, Mihalis Yannakakis
Article No.: 30
DOI: 10.1145/2789208

A central computational problem for analyzing and model checking various classes of infinite-state recursive probabilistic systems (including quasi-birth-death processes, multitype branching processes, stochastic context-free grammars,...

Section: Complexity Theory

Signature-Free Asynchronous Binary Byzantine Consensus with t < n/3, O(n2) Messages, and O(1) Expected Time
Achour Mostéfaoui, Hamouma Moumen, Michel Raynal
Article No.: 31
DOI: 10.1145/2785953

This article is on broadcast and agreement in asynchronous message-passing systems made up of n processes, and where up to t processes may have a Byzantine Behavior. Its first contribution is a powerful, yet simple, all-to-all...