enter search term and/or author name
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...
Delegating Computation: Interactive Proofs for Muggles
Shafi Goldwasser, Yael Tauman Kalai, Guy N. Rothblum
Article No.: 27
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....
Algorithmic Applications of Baur-Strassen’s Theorem: Shortest Cycles, Diameter, and Matchings
Marek Cygan, Harold N. Gabow, Piotr Sankowski
Article No.: 28
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...
Invited Articles Foreword
Article No.: 29
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
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,...
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
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...