- Probabilistic cellular automata with Andrei Toom (26 pages) [arXiv].
- A reliable Turing machine (with Çapuni) (82 pages) [pdf].
- Inequalities for space-bounded Kolmogorov complexity (with Romashchenko and Shen) (15 pages) [arXiv].
- Stable multi-level monotonic eroders (with Törmä) (32 pages) [arXiv].
- Clairvoyant embedding in one dimension (49 pages) [arXiv].
- A Turing machine resisting isolated bursts of faults (with Çapuni) (46 pages) [pdf].
- Algorithmic tests and randomness with respect to a class of measures (with Bienvenu, Hoyrup, Rojas and Shen) (89 pages) [pdf].
- A constructive law of large numbers (17 pages) [pdf],
- Raymond J. Solomonoff, 1926-2009 (with Vitányi) (17 pages) [pdf].
- Randomness on computable probability spaces - a dynamical point of view (with Hoyrup, Rojas) (18 pages) [pdf].
- 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
(181 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 (88 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]. - 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) [pdf].
- A New Version of Toom's Proof (13 pages) [arXiv].
- 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].
- Review of Chaitin's "Algorithmic information theory"(4 pages) [pdf].
- On Playing "Twenty Questions" with a Liar (with Dhagat, Spencer, Winkler) (11 pages) [pdf]. [talk].
- Self-Correcting Two-Dimensional Arrays (52 pages) [pdf].
- A Simple Three-Dimensional Real-Time Reliable Cellular Array (23 pages)
[pdf].

The note above: "A New Version of Toom's Proof", gives also a simpler proof of a stronger version of this result. - Reliable Computation with Cellular Automata (64 pages) [pdf].
- Every Sequence is Reducible to a Random One (7 pages) [pdf].
- On the Relation Between Descriptional Complexity and Algorithmic
Probability (23 pages)
[pdf].

Adam Day's improved version of the main result of the above paper, in my exposition (27 pages) [pdf].

Slides of a talk [pdf]. - Causal Nets (with Levin) (11 pages) [pdf].
- Exact Expressions for Some Randomness Tests (10 pages) [pdf].
- One-dimensional uniform arrays that wash out finite islands (with Kurdyumov and Levin) (4 pages) [pdf].
- Some remarks on generalized spectra (with Lovász) (8 pages) [pdf].
- Komplexität und Zufälligkeit (thesis, 40 pages) [pdf].
- Spreading of Sets in Product Spaces and Hypercontraction of the Markov-Operator (with Ahlswede) (15 pages) [pdf].
- On a problem of Cox concerning point processes in R^k of "controlled variability" (with Szász) (12 pages) [pdf].
- Bounds on Conditional Probabilities with Applications in Multi-User Communication (with Ahlswede and Körner) (22 pages) [pdf]. [correction].
- Common Information is Far Less than Mutual Information (with Körner) (14 pages) [pdf].
- On the symmetry of algorithmic information (4 pages) [pdf].
- Packing of convex sets in the plane with a great number of neighbors (6 pages) [pdf].

- A constructive law of large numbers [pdf].
- Reliably computing cellular automata [pdf].
- 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].
- Clairvoyant embedding in one dimension [pdf].
- Eroders [pdf].
- A popular talk on algorithmic information [pdf].

- cs131 Fall 2008 (Combinatorial Structures) [pdf].
- cs235 Fall 2005 (Algebraic algorithms) [pdf].
- cs237 Spring 2016 (Probability in computer science) [pdf].
- cs330 (Algorithms, undergraduate) Fall 2010, Spring 2020,
- cs332 Spring 2013 (Computational complexity, undergraduate) [pdf],
- cs530 Spring 2018 (Analysis of algorithms, with linear programming, graduate) [pdf],
- cs535 Fall 2019 (Computational complexity, graduate) [pdf],
- cs537 Fall 2017 (Probability in computing, graduate) [pdf],
- Approximation algorithms, Fall 2006 [pdf],
- On lossless expanders (Results by Capalbo, Reingold, Vadhan, Wigderson) [pdf],
- The ergodic theorem and algorithmic randomness (V'yugin's results) [pdf],