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 verification (by M.Blum and his followers)
and techniques used in several results matching 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
https://www.cs.bu.edu/fac/lnd/expo/holo.htm for an exposition accessible
to non-experts.
One of the simple effects 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 their use for pseudorandomness in
[Levin 87].
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. (In the form of ergodicity of all 1-dimensional particle
systems it was sometimes claimed as theorem by physicists.) it was refuted by
P.Gacs in an enormously complicated 1986 construction. Looking for simple
arguments we designed a 2-state (>,<) automaton changing when opposed by
its both first and third neighbor from the sharp end. In circular arrays with
n=3k1.8 or more cells it keeps the common bit and recovers within n
steps form any configuration with < k 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.