Back to the root file of my research overview.

Error-Resistant Computations

Holographic Proofs and Error Correcting Codes

In [Babai, Fortnow, Levin, Szegedy: STOC-91] we show that any computation or mathematical proof can be put in a transparent (or holographic or PCP) form in nearly linear time. Proofs in this form can be verified instantly (in polylogarithmic Monte-Carlo time). For that, one needs random access to the proof, to the proven statement (or input/output of computation) in error-correcting code, and to a source of coin-flips. This paper used earlier ideas of proof verifications (by M.Blum and his followers) and techniques used in several results on identity of high interactive complexity classes (by Nisan, Lund, Karloff, Fortnow, Babai, Shamir). Our paper was followed by a great number of papers that have tightened its results and found other remarkable (and seemingly unrelated) applications, e.g., to proving approximation problems NP-complete. Look at http://www.cs.bu.edu/fac/lnd/expo/holo.htm for an exposition accessible to non-experts.

A very primitive aspect of holographic proofs provides error-correcting codes with a remarkable, not known before our paper, property. Suppose, we want to preserve the human heritage from catastrophic loss by keeping, say, Library of Congress in the form of an error correcting code. The code would guarantee that any loss or corruption of, say, < 5% of bits is completely recoverable. The problem is that to decode any part of the library (say one paper) requires decoding everything. The ``holographic'' codes ( nearly-linear, of length n^(1+o(1)) ) do not have this problem. They have the same immunity to corruption, but require only polylogarithmic Monte-Carlo time to recover any bit.

It is interesting that the powerful technique of error correcting codes was not used in general theory of computation for a long time: I know no such applications prior to [Levin 87] and few before [bfls-91].

Selfstabilizing Computations.

[Gacs, Kurdiumov, Levin 78] is related to a difficult problem of whether one-dimensional computing media can resist errors. A negative answer was a popular conjecture, now refuted. In the form of ergodicity of all 1-dimensional particle systems it was sometimes claimed as theorem by physicists. Looking for counter-evidence, we designed a very simple (but far from obvious) automaton with 2 states "<,>" changing when opposed by its both first and third neighbor from the sharp end. In circular arrays with n=3k^1.8 or more cells it keeps the common bit and recovers within n steps form any configuration with < k of errors.

[Itkis, Levin, FOCS-94] shows that all computational protocols can be efficiently made self-stabilizing and immune to asynchrony on any network even with constant memory per node, and worst-case dynamic faults.

Games: Multi-party Computations with Faulty Players.

[Goldwasser, Levin 91] modifies in a polynomial time any partial information game (with trusted arbitrator) into an equivalent full information game (no trusted parties). Private, broadcasting, and oblivious-transfer channels are used as primitives. Unlike predecessors, we do not assume honest majority of players or boolean output, nor do we allow a polynomial chance of successful cheating. We also define useful general concepts of robust protocols.