MIT Math Dept., Cambridge, MA
Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, 1983 – STOC
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. ...
Thang Nguyen Bui, Soma Chaudhuri, Frank Thomson Leighton, Michael Sipser
Shafi Goldwasser, Michael Sipser
Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, 1986 – STOC
An interactive proof system is a method by which one party of unlimited resources, called the prover, can convince a party of limited resources, call the verifier, of the truth of a proposition. The verifier may toss coins, ask repeated questions of ...
Michael Sipser, Daniel A. Spielman
IEEE Transactions on Information Theory, vol. 42,no. 6,1996 – TIT
Using expander graphs, we construct a new family of asymptotically good, linear errorcorrecting codes. These codes have linear time sequential decoding algorithms and logarithmic time parallel decoding algorithms that use a linear number of ...
Christos H. Papadimitriou, Michael Sipser
Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, 1982 – STOC
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 ...
Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, 1983 – STOC
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.
Journal of Computer and System Sciences, vol. 36,no. 3,1988 – JCSS
Baruch Awerbuch, Michael Sipser
FOCS 1988: White Plains, 1988 – FOCS
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 ...