Online publications
- The Angel Wins (28 pages)
[pdf],
Slides of a talk
[pdf],
- Book chapter on reliable computation
[54 pages, English pdf],
[60 oldal, magyar pdf]
- Lecture Notes on Descriptional Complexity and Randomness
(133 pages)
[pdf]
Uniform Test of Algorithmic Randomness ...: incorporated, in
strengthened form, into the above Lecture Notes.
Slides of a talk
[pdf]
- Theory of Computing (Popular lecture, 7 pages)
[pdf]
- Clairvoyant Scheduling of Random Walks (69 pages)
[pdf]
Slides of a talk
[pdf]
- Quantum Algorithmic Entropy (20 pages)
[pdf]
- Compatible Sequences and a Slow Winkler Percolation
(37 pages)
[pdf]
Slides of a talk
[pdf]
- Algorithmic Statistics (with Tromp, Vitányi) (22 pages)
[pdf]
- The Clairvoyant Demon Has a Hard Task (4 pages)
[pdf]
- Reliable Cellular Automata with Self-Organization (172 pages)
[pdf]
An introduction for probabilists, by Larry Gray (40 pages)
[ps]
FOCS'97 extended abstract (10 pages)
[ps]
Highest honor: a citation among Church fathers
[link]
- Deterministic Computations Whose History is Independent of the
Order of Asynchronous Updating
(11 pages)
[pdf]
- Ergodicity and Mixing Rate of One-Dimensional Cellular
Automata (Kihong Park's thesis)
(108 pages)
[ps]
- A New Version of Toom's Proof (11 pages)
[pdf]
- A Toom Rule that Increases the Thickness of Sets (16 pages)
[pdf]
- The Boltzmann Entropy and Randomness Tests (28 pages)
[pdf]
- Information Distance (with Bennett, Li, Vitányi, Zurek)
(29 pages)
[pdf]
- Lower Bounds for the Complexity of Reliable Boolean
Circuits with Noisy Gates (with Gál)
(12 pages)
[pdf]
- On Playing "Twenty Questions" with a Liar
(with Dhagat, Spencer, Winkler)
(11 pages)
[pdf]
- Self-Correcting Two-Dimensional Arrays (52 pages)
[pdf]
- On the Relation Between Descriptional Complexity and Algorithmic
Probability (23 pages)
[pdf]
Expanded proof of the main result of the above paper (22 pages)
[pdf]
Slides of a talk
[pdf]
- Causal Nets (with Levin) (11 pages)
[pdf]
- Exact Expressions for Some Randomness Tests (10 pages)
[pdf]
- Common Information is Far Less than Mutual Information
(with Körner) (14 pages)
[pdf]
Talks
-
Self-stabilizing synchronization in 3 dimensions
[pdf]
-
A storage allocation game with application in algorithmic information
theory
[pdf]
-
Algorithmic randomness test for a class of measures
[pdf]
-
The angel wins
[pdf]
-
Compatible sequences and a slow Winkler percolation
[pdf]
-
Clairvoyant scheduling of random walks
[pdf]
Lectures
-
cs235 Fall 05 (Algebraic algorithms)
[pdf]
-
cs332 Spring 05 (Computational complexity, undergraduate)
[pdf]
-
cs530 Spring 06 (Analysis of algorithms, with convex
programming, graduate)
[pdf]
-
cs535 Fall 04 (Computational complexity, graduate)
[pdf]
-
cs537 Spring 07 (Probability in computing, graduate)
[pdf]
-
Approximation algorithms, Fall 06
[pdf]
-
On lossless expanders (Results by Capalbo, Reingold,
Vadhan, Wigderson)
[pdf]
-
The ergodic theorem and algorithmic randomness (V'yugin's results)
[pdf]
Software