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 DP2 is contained in probabilistic linear time and where BPP has linear sized circuits, as well as oracles for the negation of these questions. This indicates that these questions will not be solved by techniques that relativize. Finally, we note that probabilistic linear time can not contain both NP and BPP, implying that there are languages solvable by interactive proof systems that can not be solved in probabilistic linear time.

Using expander graphs, we construct a new family of asymptotically good, linear error-correcting codes. These codes have linear time sequential decoding algorithms and logarithmic time parallel decoding algorithms that use a linear number of processors. We present both randomized and explicit constructions of these codes. Experimental results demonstrate the good performance of the randomly chosen codes.

A hidden Markov chain (hmc) is a finite ergodic Markov chain in which each of the states is labelled 0 or 1. As the Markov chain moves through a random trajectory, the hmc emits a 0 or a 1 at each times step according to the label of the state just entered.

We present a new class of asymptotically good, linear error-correcting codes based upon expander graphs. These codes have linear time sequential decoding algorithms, logarithmic time parallel decoding algorithms with a linear number of processors, and are simple to understand. We present both randomized and explicit constructions for some of these codes. Experimental results demonstrate the extremely good performance of the randomly chosen codes.>

this article, I have attempted to organize and describe this literature, including an occasional opinion about the most fruitful directions, but no technical details. In the first half of this century, work on the power of formal systems led to the formalization of the notion of algorithm and the realization that certain problems are algorithmically unsolvable. At around this time, forerunners of the programmable computing machine were beginning to appear. As mathematicians contemplated the practical capabilities and limitations of such devices, computational complexity theory emerged from the theory of algorithmic unsolvability. Early on, a particular type of computational task became evident, where one is seeking an object which lies

A complexity-theoretic approach to the classical data compression problem is presented. A notion of language compressibility is defined, and it is shown that essentially all strings in a sufficiently sparse “easy” (e.g., polynomial-time) language can be compressed efficiently. A notion of ranking as a form of optimal compression is also defined, and it is shown that some “very easy” languages (e.g., unambiguous context-free languages) can be ranked efficiently. Languages that cannot be compressed or ranked efficiently under various complexity-theoretic assumptions are exhibited. The notion of compressibility is closely related to Kolmogorov complexity and randomness. This relationship and the complexity-theoretic implications of our results are discussed.

An efficient simulation is given to show that dynamic networks are as fast as static ones up to a constant multiplicative factor. That is, any task can be performed in a dynamic asynchronous network essentially as fast as in a static synchronous network. The simulation protocol is based on an approach in which locality is perceived as the key to fast adaptation to changes in network topology. The heart of the simulation is a technique called a dynamic synchronizer, which achieves 'local' simulation of a global 'clock' in a dynamic asynchronous network. Using this result, improved solutions to a number of well-known problems on dynamic networks are obtained. It can also be used to improve the solution to certain static network problems.>

An interactive proof system with Perfect Completeness (resp. Perfect Soundness) for a language L is an interactive proof (for L) in which for every x ∈ L (resp. x ∉ L) the verifier always accepts (resp. always rejects). Zachos and Fuerer showed that any language having a bounded interactive proof has one with perfect completeness. We extend their result and show that any language having a (possibly unbounded) interactive proof system has one with perfect completeness. On the other hand, only languages in NP have interactive proofs with perfect soundness. We present two proofs of the main result. One proof extends Lautemann's proof that BPP is in the polynomial-time hierarchy. The other proof, uses a new protocol for proving approximately lower bounds and "random selection". The problem of random selection consists of a verifier selecting at random, with uniform probability distribution, an element from an arbitrary set held by the prover. Previous protocols known for approximate lower bound do not solve the random selection problem. Interestingly, random selection can be implemented by an unbounded Arthur-Merlin game but can not be implemented by a two-iteration game.

Article Private coins versus public coins in interactive proof systems Share on Authors: S Goldwasser Computer Science Department, MIT Computer Science Department, MITView Profile , M Sipser Computer Science Department, University of California at Berkeley and Mathematics Department, MIT Computer Science Department, University of California at Berkeley and Mathematics Department, MITView Profile Authors Info & Claims STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computingNovember 1986 Pages 59–68https://doi.org/10.1145/12130.12137Online:01 November 1986Publication History 169citation1,122DownloadsMetricsTotal Citations169Total Downloads1,122Last 12 Months108Last 6 weeks11 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

A complexity-theoretic approach to the classical data compression problem is to define a notion of language compression by a machine in a certain complexity class, and to study language classes compressible under the above definition. Languages that can be compressed efficiently (e.g. by a probabilistic polynomial time machine) are of special interest.

We describe a polynomial time algorithm that, for every input graph, either outputs the minimum bisection of the graph or halts without output. More importantly, we show that the algorithm chooses the former course with high probability for many natural classes of graphs. In particular, for every fixed d⩾3, all suffciently large n and all b = o(n1-(1/[(d+1)/2]), the algorithm finds the minimum bisection for almost all d-regular labelled simple graphs with 2n nodes and bisection width b.

It is shown that for every k, polynomial-size, depth-k Boolean circuits are more powerful than polynomial-size, depth-(k−1) Boolean circuits. Connections with a problem about Borel sets and other questions are discussed.

We study a time bounded variant of Kolmogorov complexity. This notion, together with universal hashing, can be used to show that problems solvable probabilistically in polynomial time are all within the second level of the polynomial time hierarchy. We also discuss applications to the theory of probabilistic constructions.

In this paper we prove several results concerning this complexity measure. First we establish (in a non-constructive manner) that there exist languages which cannot be recognized with less than n communication (obviously, communication n is always enough for recognizing any language). In fact, we show that for any functionf(n) < n, there are languages recognizable with communicationf(n) but not with communicationf (n)-1. In other words, this complexity measure possesses a very dense hierarchy or complexity classes, as miniscule increments in communication add to the languages that can be recognized.

A super-polynomial lower bound is given for the size of circuits of fixed depth computing the parity function. Introducing the notion of polynomial-size, constant-depth reduction, similar results are shown for the majority, multiplication, and transitive closure functions. Connections are given to the theory of programmable logic arrays and to the relativization of the polynomial-time hierarchy.

It is shown that, given an arbitrary GO position on an n × n board, the problem of determining the winner is Pspace hard. New techniques are exploited to overcome the difficulties arising from the planar nature of board games. In particular, it is proved that GO is Pspace hard by reducing a Pspace-complete set, TQBF, to a game called generalized geography, then to a planar version of that game, and finally to GO.

Establishing good lower bounds on the complexity of languages is an important area of current research in the theory of computation. However, despite much effort, fundamental questions such as P =? NP and L =? NL remain open. To resolve these questions it may be necessary to develop a deep combinatorial understanding of polynomial time or log space computations, possibly a formidable task.

A great deal of effort has been spent in the search for optimal and computationally feasible game strategies. In some cases (e.g. Bridge-it, Nim), such strategies have been found, \vhile in others the search has been unsuccessful. Recently, it has become possible to provide compelling evidence that such strategies may not always exist. Even and Tarjan [1] and Schaefer [2] have shown that determining which player has a winning strategy in certain combinatorial games is a polynomial space complete problem [3]. (See also [4;5].)

Article Free Access Share on Nondeterminism and the size of two way finite automata Authors: William J. Sakoda View Profile , Michael Sipser View Profile Authors Info & Claims STOC '78: Proceedings of the tenth annual ACM symposium on Theory of computingMay 1978 Pages 275–286https://doi.org/10.1145/800133.804357Online:01 May 1978Publication History 129citation98DownloadsMetricsTotal Citations129Total Downloads98Last 12 Months33Last 6 weeks7 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Abstract Intuitively, the program size complexity of a binary string measures the amount of information in the string. Researchers have formalized this notion in a number of different ways. Here, we demonstrate similarities between some of these formulations. We also investigate in some detail the properties of Kolmogorov's complexity measure.