STOC

Let ƒ(x₁, ···· x_k) be a Boolean function that k parties wish to collaboratively evaluate. The i'th party knows each input argument except x_i; and each party has unlimited computational power. They share a blackboard, viewed by all parties, where they ...

We show that the existence of one-way functions is necessary and sufficient for the existence of pseudo-random generators in the following sense. Let ƒ be an easily computable function such that when x is chosen randomly: (1) from ƒ(x) it is hard to ...

A central tool in constructing pseudorandom generators, secure encryption functions, and in other areas are “hard-core” predicates b of functions (permutations) ƒ, discovered in [Blum Micali 82]. Such b(x) cannot be efficiently guessed (substantially ...

We define a Universal One-Way Hash Function family, a new primitive which enables the compression of elements in the function domain. The main property of this primitive is that given an element x. We prove constructively that universal one-way hash ...

We present strong evidence that the implication, “if one-way permutations exist, then secure secret key agreement is possible”, is not provable by standard techniques. Since both sides of this implication are widely believed true in real life, to show ...

A Boolean function ƒ: A₁ X A₂ X … X A_n → {0,1} is t - private if there exists a protocol for computing ƒ so that no coalition of size ≤ t can infer any additional information from the execution, other than the value of the function. We show that ƒ is ⌈n/...

Under the assumption that each participant can broadcast a message to all other participants and that each pair of participants can communicate secretly, we present a verifiable secret sharing protocol, and show that any multiparty protocol, or game ...

A program correctness checker is an algorithm for checking the output of a computation. This paper defines the concept of a program checker. It designs program checkers for a few specific and carefully chosen problems in the class P of problems solvable ...

Finding small quadratic residues modulo n, when n is a large composite number of unknown factorisation is almost certainly a computationally hard problem. This problem arises in a natural way when factoring n by the use of congruences of squares. We ...

We study the effect of various syntactic restrictions on the expressive power of database logic programs. We find natural examples of programs which

• require recursively defined predicates of arbitrarily large width,

• require rules with arbitrarily many ...

We study here the use of different representation for infinitary regular languages in extended temporal logic. We focus on three different kinds of acceptance conditions for finite automata on infinite words, due to Büchi, Streett, and Emerson and Lei (...

In this paper we develop a fast parallel procedure for deciding when a set of multivariate polynomials with coefficients in an arbitrary field K have a common algebraic solution. Moreover, since the proposed algorithm is algebraic, it easily yields a ...

In this paper, we give an oracle under which BPP is equal to probabilistic linear time, an unusual collapse of a complexity time hierarchy. In addition, we also give oracles where Δ^P₂ is contained in probabilistic linear time and where BPP has linear ...

Berman and Hartmanis [BH77] conjectured that there is a polynomial-time computable isomorphism between any two languages m-complete (“Karp” complete) for NP. Joseph and Young [JY85] discovered a structurally defined class of NP-complete sets and ...

We consider the quadratic complexity of certain sets of quadratic forms. We study a classes of direct sums of quadratic forms. For these classes of problems we show that the complexity of one direct sum is the sum of the complexity of the summands and ...

This paper contains two parts. In Part I, we show that polynomial-size monotone threshold circuits of depth k form a proper hierarchy in parameter k. This implies in particular that monotone TC⁰ is properly contained in NC¹. In Part II, we introduce a ...

An optimal Ω(n²) lower bound is shown for the time-space product of any R-way branching program that determines those values which occur exactly once in a list of n integers in the range [1, R] where R ≥ n. This Ω(n²) tradeoff also applies to the ...

This paper takes the next step in developing the theory of average case complexity initiated by Leonid A. Levin. Previous works [Levin 84, Gurevich 87, Venkatesan and Levin 88] have focused on the existence of complete problems. We widen the scope to ...

This paper initiates the study of communication complexity when the processors have limited work space. The following tradeoffs between number C of communications steps and space S are proved:

• For multiplying two n × n matrices in the arithmetic model ...

In this paper, we study the problem of emulating T_G steps of an N_G-node guest network on an N_H-node host network. We call an emulation work-preserving if the time required by the host, T_H, is Ο(T_GN_G/N_H) because then both the guest and host networks ...

We present a deterministic Ο(log N) time algorithm for the problem of routing an arbitrary permutation on an N-processor bounded-degree network with bounded buffers.

Unlike all previous deterministic solutions to this problem, our routing scheme does not ...

We consider the computational power of a hypercube containing a potentially large number of randomly located faulty components. We describe a randomized algorithm which embeds an N-node hypercube in an N-node hypercube with faulty processors. Provided ...

Division is a fundamental problem for arithmetic and algebraic computation. This paper describes Boolean circuits (of bounded fan-in) for integer division (finding reciprocals) that have size Ο(M(n)) and depth Ο(lognlog logn), where M(n) is the size ...

A radio network is a synchronous network of processors that communicate by transmitting messages to their neighbors. A processor receives a message in a given step if and only if it is silent then and precisely one of its neighbors transmits. This ...

Almost every problem on digraphs requires computing strongly connected components and directed spanning trees in one form or another. It has long been an open problem whether polylog time and linear processors are enough to find the strongly connected ...

A directed cycle separator of an n-vertex directed graph is a simple directed cycle such that when the vertices of the cycle are deleted, the resulting graph has no strongly connected component with more than n/2 vertices. This paper shows that the ...

We obtain tight bounds on the relative powers of the Priority and Common models of parallel random-access machines (PRAMs). Specifically we prove that:

• The Element Distinctness function of n integers, though solvable in constant time on a Priority PRAM ...