STOC

We present a new method for accelerating matrix multiplication asymptotically. This work builds on recent ideas of Volker Strassen, by using a basic trilinear form which is not a matrix product. We make novel use of the Salem-Spencer Theorem, which ...

We introduce a framework for solving minimum-cost flow problems. Our approach measures the quality of a solution by the amount that the complementary slackness conditions are violated. We show how to extend techniques developed for the maximum flow ...

An algorithm is presented for generating a succinct encoding of all pairs shortest path information in a directed planar graph G with real-valued edge costs but no negative cycles. The algorithm runs in Ο(pn) time, where n is the number of vertices in G,...

We present an algorithm for linear programming which requires Ο(((m + n) n² + (m + n)^1.5 n) L) arithmetic operations where m is the number of inequalities, and n is the number of variables. Each operation is performed to a precision of Ο (L) bits. L is ...

We present an algorithm for computing certain kinds of three-dimensional convex hulls in linear time. Using this algorithm, we show that the Voronoi diagram of n points in the plane can be computed in Θ(n) time when these points form the vertices of a ...

This paper gives approximation algorithms of solving the following motion planning problem: Given a set of polyhedral obstacles and points s and t, find a shortest path from s to t that avoids the obstacles. The paths found by the algorithms are ...

Throughout this paper, we use the term subdivision as a shorthand for “a subdivision of E² into convex regions”. A subdivision is said to be of size n if it is made of n convex (open) regions, and it is of degree d if every region is adjacent to at most ...

We use algebraic methods to get lower bounds for complexity of different functions based on constant depth unbounded fan-in circuits with the given set of basic operations. In particular, we prove that depth k circuits with gates NOT, OR and MOD_p where ...

We prove optimal Ω(log n/log log n) lower bounds on the time for CRCW PRAM's with polynomially bounded numbers of processors or memory cells to compute parity and a number of related problems. We also exhibit a strict time hierarchy of explicit Boolean ...

We prove the first superlinear lower bound for a concrete decision problem in P on a Turing machine with one work tape and a two-way input tape (also called: off-line 1-tape Turing machine). In particular we show for off-line Turing machines that 2 ...

Recently a new connection was discovered between the parallel complexity class NC¹ and the theory of finite automata, in the work of Barrington [Ba86] on bounded width branching programs. There (non-uniform) NC¹ was characterized as those languages ...

The polynomial hierarchy, composed of the levels P, NP, P^NP, NP^NP, etc., plays a central role in classifying the complexity of feasible computations. It is not known whether the polynomial hierarchy collapses.

We resolve the question of collapse for an ...

In this paper we show that a wide class of probabilistic algorithms can be simulated by deterministic algorithms. Namely if there is a test in LOGSPACE so that a random sequence of length (log n)² / log log n passes the test with probability at least 1/...

Two properties, called semi-unboundedness, and polynomial proof-size, are identified as key properties shared by the definitions of LOGCFL on several models of computations. The semi-unboundedness property leads to the definition of new models of ...

If secure pseudorandom generators exist, then probabilistic computation does not uniformly speed up deterministic computation. If sets in P must contain infinitely many noncomplex strings, then nondeterministic computation does not uniformly speed up ...

We consider a simple model for a class of discrete control processes, motivated in part by recent work about the behavior of imperfect random sources in computer algorithms. The process produces a string of characters from {0, 1} of length n and is a “...

Improving a result of Mehlhorn and Schmidt, a function f with deterministic communication complexity n² is shown to have Las Vegas communication complexity Ο(n). This is the best possible, because the deterministic complexity cannot be more than the ...

Software protection is one of the most important issues concerning computer practice. There exist many heuristics and ad-hoc methods for protection, but the problem as a whole has not received the theoretical treatment it deserves. In this paper, we ...

We consider the problem of computing with encrypted data. Player A wishes to know the value ƒ(x) for some x but lacks the power to compute it. Player B has the power to compute ƒ and is willing to send ƒ(y) to A if she sends him y, for any y. Informally,...

A Perfect Zero-Knowledge interactive proof system convinces a verifier that a string is in a language without revealing any additional knowledge in an information-theoretic sense. We show that for any language that has a perfect zero-knowledge proof ...

In this paper we extend the notion of zero knowledge proofs of membership (which reveal one bit of information) to zero knowledge proofs of knowledge (which reveal no information whatsoever). After formally defining this notion, we show its relevance to ...

We present a polynomial-time algorithm that, given as a input the description of a game with incomplete information and any number of players, produces a protocol for playing the game that leaks no partial information, provided the majority of the ...

This paper develops linear time distributed algorithms for a class of problems in an asynchronous communication network. Those problems include Minimum-Weight Spanning Tree (MST), Leader Election, counting the number of network nodes, and computing a ...

In the paper, we analyze the stochastic behavior of backoff protocols for multiple access channels such as the Ethernet. In particular, we prove that binary exponential backoff is unstable if the arrival rate of new messages at each station is λ/N for ...

The dynamic parallel complexity of general computational circuits (defined in introduction) is discussed. We exhibit some relationships between parallel circuit evaluation and some uniform closure properties of a certain class of unary functions and ...

In a typical parallel or distributed computation model processors are connected by a sparse interconnection network. To establish open-line communication between pairs of processors that wish to communicate interactively, a set of disjoint paths has to ...

We consider the computational power of a hypercube containing a potentially large number of randomly located faulty components. In particular, we describe algorithms for embedding an N/2-node hypercube in an N-node hypercube with faulty processors. ...