Online publications
- 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 (231 pages)
[pdf]
A corrected and strengthened version of the 2001 paper in Journal of Statistical Physics.
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].
Talks
-
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].
Lectures
-
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],
Software