Arrow Research search

Author name cluster

Michael Sipser

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

23 papers
2 author rows

Possible papers

23

FOCS Conference 1994 Conference Paper

Expander Codes

  • Michael Sipser
  • Daniel A. Spielman

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. >

Details

TCS Journal 1994 Journal Article

On the power of multi-prover interactive protocols

  • Lance Fortnow
  • John Rompel
  • Michael Sipser

We look at complexity issues of interactive proof systems with multiple provers separated from each other. This model, developed by Ben-Or et al. (1988) allows the verifier to play the provers off each other. We show this model equivalent to an alternative interactive proof system model using oracles as provers. We also show that every language accepted by these models lies in nondeterministic exponential time. We exhibit a relativized world where a co-NP language does not have multiple prover interactive proofs. Finally, we show a simple example that one cannot parallelize multiple prover protocols as easily as the single prover model.

Details DOI

FOCS Conference 1988 Conference Paper

Dynamic Networks Are as Fast as Static Networks (Preliminary Version)

  • Baruch Awerbuch
  • Michael Sipser

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. >

Details

FOCS Conference 1987 Conference Paper

Interactive Proof Systems: Provers that never Fail and Random Selection (Extended Abstract)

  • Oded Goldreich 0001
  • Yishay Mansour
  • Michael Sipser

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.

Details

STOC Conference 1985 Conference Paper

Compression and Ranking

  • Andrew V. Goldberg
  • Michael Sipser

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.

Details

FOCS Conference 1984 Conference Paper

Graph Bisection Algorithms with Good Average Case Behavior

  • Thang Nguyen Bui
  • Soma Chaudhuri
  • Frank Thomson Leighton
  • Michael Sipser

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(n 1-(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.

Details

STOC Conference 1983 Conference Paper

Borel Sets and Circuit Complexity

  • Michael Sipser

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.

Details

STOC Conference 1982 Conference Paper

Communication Complexity

  • Christos H. Papadimitriou
  • Michael Sipser

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 function f(n) < n, there are languages recognizable with communication f(n) but not with communication f (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.

Details

TCS Journal 1981 Journal Article

Several results in program size complexity

  • Howard P. Katseff
  • Michael Sipser

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.

Details DOI

STOC Conference 1979 Conference Paper

Lower Bounds on the Size of Sweeping Automata

  • Michael Sipser

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.

Details
v2026.09.13