| Publication | Date of Publication | Type |
|---|
Algorithmic arguments in physics of computation
Lecture Notes in Computer Science | 2022-12-16 | Paper |
Average-case analysis via incompressibility
Fundamentals of Computation Theory | 2022-12-09 | Paper |
Randomized two-process wait-free test-and-set
Distributed Computing | 2020-12-03 | Paper |
| Randomized naming using wait-free shared variables | 2020-12-02 | Paper |
Philosophical issues in Kolmogorov complexity
Automata, Languages and Programming | 2019-12-04 | Paper |
Logical depth for reversible Turing machines with an application to the rate of decrease in logical depth for general Turing machines
Theoretical Computer Science | 2019-06-06 | Paper |
Logical depth for reversible Turing machines with an application to the rate of decrease in logical depth for general Turing machines
Theoretical Computer Science | 2019-06-06 | Paper |
Corrigendum to: ``On the rate of decrease in logical depth'' by by L. F. Antunes, A. Souto, and P. M. B. Vitányi
Theoretical Computer Science | 2019-05-02 | Paper |
An introduction to Kolmogorov complexity and its applications
Texts in Computer Science | 2019-02-15 | Paper |
Obituary: Ray Solomonoff, founding father of algorithmic information theory
Algorithms | 2018-08-20 | Paper |
On the average-case complexity of Shellsort
Random Structures & Algorithms | 2018-06-07 | Paper |
On the average-case complexity of Shellsort
Random Structures & Algorithms | 2018-06-07 | Paper |
On the rate of decrease in logical depth
Theoretical Computer Science | 2017-11-06 | Paper |
Exact Expression For Information Distance
IEEE Transactions on Information Theory | 2017-10-19 | Paper |
Approximation of the Two-Part MDL Code
IEEE Transactions on Information Theory | 2017-08-08 | Paper |
Information Distance in Multiples
IEEE Transactions on Information Theory | 2017-07-27 | Paper |
Rate Distortion and Denoising of Individual Data Using Kolmogorov Complexity
IEEE Transactions on Information Theory | 2017-07-27 | Paper |
Approximating Rate-Distortion Graphs of Individual Data: Experiments in Lossy Compression and Denoising
IEEE Transactions on Computers | 2017-07-12 | Paper |
Identification of probabilities
Journal of Mathematical Psychology | 2017-02-28 | Paper |
Similarity and denoising
Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences | 2017-01-13 | Paper |
Two heads are better than two tapes
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 | 2016-09-01 | Paper |
Bounded concurrent timestamp systems using vector clocks
Journal of the ACM | 2015-10-30 | Paper |
A lower bound on the average-case complexity of shellsort
Journal of the ACM | 2015-09-19 | Paper |
Optimal routing tables
Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing - PODC '96 | 2015-09-11 | Paper |
Thermodynamics of computation and information distance
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 | 2015-05-07 | Paper |
Conditional Kolmogorov complexity and universal probability
Theoretical Computer Science | 2014-01-10 | Paper |
Tolstoy's mathematics in ``War and peace''
The Mathematical Intelligencer | 2013-07-18 | Paper |
| Identification of Probabilities of Languages | 2012-08-24 | Paper |
Nonapproximability of the normalized information distance
Journal of Computer and System Sciences | 2011-04-28 | Paper |
A fast quartet tree heuristic for hierarchical clustering
Pattern Recognition | 2011-01-31 | Paper |
A fast quartet tree heuristic for hierarchical clustering
Pattern Recognition | 2011-01-31 | Paper |
Time-bounded incompressibility of compressible strings and sequences
Information Processing Letters | 2010-08-20 | Paper |
Physics and the new computation
Lecture Notes in Computer Science | 2010-06-17 | Paper |
Genetic fitness optimization using rapidly mixing Markov chains
Lecture Notes in Computer Science | 2010-04-27 | Paper |
Depth as randomness deficiency
Theory of Computing Systems | 2009-10-19 | Paper |
Sharpening Occam's razor
Information Processing Letters | 2009-03-23 | Paper |
Normalized Information Distance
Information Theory and Statistical Learning | 2009-03-12 | Paper |
Clustering by Compression
IEEE Transactions on Information Theory | 2008-12-21 | Paper |
The Similarity Metric
IEEE Transactions on Information Theory | 2008-12-21 | Paper |
Kolmogorov's Structure Functions and Model Selection
IEEE Transactions on Information Theory | 2008-12-21 | Paper |
Meaningful Information
IEEE Transactions on Information Theory | 2008-12-21 | Paper |
| Algorithmic chaos and the incompressibility method | 2008-06-27 | Paper |
An introduction to Kolmogorov complexity and its applications
Texts in Computer Science | 2008-06-04 | Paper |
`Ideal learning' of natural language: positive results about learning from positive evidence
Journal of Mathematical Psychology | 2007-10-01 | Paper |
STACS 2004
Lecture Notes in Computer Science | 2007-10-01 | Paper |
Individual communication complexity
Journal of Computer and System Sciences | 2007-08-23 | Paper |
Theory and Applications of Models of Computation
Lecture Notes in Computer Science | 2007-04-30 | Paper |
Correction to "CDMA systems in fading channels: admissibility, network capacity, and power control"
IEEE Transactions on Information Theory | 2005-05-11 | Paper |
Correction to "Algorithmic statistics"
IEEE Transactions on Information Theory | 2005-05-11 | Paper |
Mutual search
Journal of the ACM | 2005-01-25 | Paper |
| scientific article; zbMATH DE number 2089996 (Why is no real title available?) | 2004-08-12 | Paper |
| scientific article; zbMATH DE number 2080439 (Why is no real title available?) | 2004-08-04 | Paper |
| scientific article; zbMATH DE number 2079851 (Why is no real title available?) | 2004-08-03 | Paper |
| scientific article; zbMATH DE number 2079424 (Why is no real title available?) | 2004-07-28 | Paper |
| scientific article; zbMATH DE number 2013826 (Why is no real title available?) | 2003-12-07 | Paper |
| scientific article; zbMATH DE number 1979532 (Why is no real title available?) | 2003-09-14 | Paper |
Kolmogorov complexity and information theory. With an interpretation in terms of questions and answers
Journal of Logic, Language and Information | 2003-09-01 | Paper |
The generalized universal law of generalization.
Journal of Mathematical Psychology | 2003-08-25 | Paper |
| scientific article; zbMATH DE number 1833412 (Why is no real title available?) | 2002-11-21 | Paper |
The average‐case area of Heilbronn‐type triangles*
Random Structures & Algorithms | 2002-08-08 | Paper |
Algorithmic statistics
IEEE Transactions on Information Theory | 2002-08-04 | Paper |
Quantum Kolmogorov complexity based on classical descriptions
IEEE Transactions on Information Theory | 2002-08-04 | Paper |
Quantum Kolmogorov complexity based on classical descriptions
IEEE Transactions on Information Theory | 2002-08-04 | Paper |
| scientific article; zbMATH DE number 1754652 (Why is no real title available?) | 2002-06-12 | Paper |
On the simulation of many storage heads by one
Theoretical Computer Science | 2002-05-13 | Paper |
| scientific article; zbMATH DE number 1696671 (Why is no real title available?) | 2002-01-28 | Paper |
Time and space bounds for reversible simulation
Journal of Physics A: Mathematical and General | 2002-01-27 | Paper |
| scientific article; zbMATH DE number 1408350 (Why is no real title available?) | 2002-01-24 | Paper |
| scientific article; zbMATH DE number 1555924 (Why is no real title available?) | 2001-01-24 | Paper |
Applying MDL to learn best model granularity
Artificial Intelligence | 2000-10-26 | Paper |
Minimum description length induction, Bayesianism, and Kolmogorov complexity
IEEE Transactions on Information Theory | 2000-09-07 | Paper |
A discipline of evolutionary programming
Theoretical Computer Science | 2000-08-21 | Paper |
New applications of the incompressibility method. II
Theoretical Computer Science | 2000-06-04 | Paper |
| scientific article; zbMATH DE number 1405647 (Why is no real title available?) | 2000-04-25 | Paper |
The miraculous universal distribution
The Mathematical Intelligencer | 2000-04-02 | Paper |
Kolmogorov Random Graphs and the Incompressibility Method
SIAM Journal on Computing | 2000-03-19 | Paper |
New Applications of the Incompressibility Method
The Computer Journal | 2000-01-17 | Paper |
Average-case analysis of algorithms using Kolmogorov complexity
Journal of Computer Science and Technology | 2000-01-01 | Paper |
Information distance
IEEE Transactions on Information Theory | 1999-11-21 | Paper |
Space-efficient Routing Tables for Almost All Networks and the Incompressibility Method
SIAM Journal on Computing | 1999-10-28 | Paper |
| scientific article; zbMATH DE number 1303590 (Why is no real title available?) | 1999-06-17 | Paper |
| scientific article; zbMATH DE number 1142293 (Why is no real title available?) | 1998-05-04 | Paper |
Two heads are better than two tapes
Journal of the ACM | 1998-02-17 | Paper |
Two heads are better than two tapes
Journal of the ACM | 1998-02-17 | Paper |
How to share concurrent wait-free variables
Journal of the ACM | 1998-01-22 | Paper |
How to share concurrent wait-free variables
Journal of the ACM | 1998-01-22 | Paper |
| scientific article; zbMATH DE number 1010621 (Why is no real title available?) | 1997-05-19 | Paper |
| scientific article; zbMATH DE number 1008511 (Why is no real title available?) | 1997-05-12 | Paper |
Reversibility and adiabatic computation: trading time and space for energy
Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences | 1997-03-23 | Paper |
| scientific article; zbMATH DE number 845624 (Why is no real title available?) | 1996-06-26 | Paper |
| scientific article; zbMATH DE number 809134 (Why is no real title available?) | 1996-03-14 | Paper |
Erratum to: Kolmogorov complexity arguments in combinatorics
Journal of Combinatorial Theory. Series A | 1995-06-30 | Paper |
A New Approach to Formal Language Theory by Kolmogorov Complexity
SIAM Journal on Computing | 1995-05-30 | Paper |
| scientific article; zbMATH DE number 740676 (Why is no real title available?) | 1995-04-03 | Paper |
Kolmogorov complexity arguments in combinatorics
Journal of Combinatorial Theory. Series A | 1995-01-12 | Paper |
Statistical properties of finite sequences with high Kolmogorov complexity
Mathematical Systems Theory | 1994-08-10 | Paper |
| scientific article; zbMATH DE number 176218 (Why is no real title available?) | 1993-05-18 | Paper |
| scientific article; zbMATH DE number 107774 (Why is no real title available?) | 1993-01-23 | Paper |
Optimality of wait-free atomic multiwriter variables
Information Processing Letters | 1993-01-17 | Paper |
Average case complexity under the universal distribution equals worst- case complexity
Information Processing Letters | 1993-01-16 | Paper |
The Power of the Queue
SIAM Journal on Computing | 1992-12-14 | Paper |
| scientific article; zbMATH DE number 67636 (Why is no real title available?) | 1992-09-27 | Paper |
Inductive reasoning and Kolmogorov complexity
Journal of Computer and System Sciences | 1992-09-27 | Paper |
A note on weighted distributed match-making
Mathematical Systems Theory | 1992-09-26 | Paper |
Learning Simple Concepts under Simple Distributions
SIAM Journal on Computing | 1992-06-26 | Paper |
| scientific article; zbMATH DE number 4117885 (Why is no real title available?) | 1989-01-01 | Paper |
| scientific article; zbMATH DE number 4096767 (Why is no real title available?) | 1988-01-01 | Paper |
| scientific article; zbMATH DE number 4086981 (Why is no real title available?) | 1988-01-01 | Paper |
| scientific article; zbMATH DE number 4062556 (Why is no real title available?) | 1988-01-01 | Paper |
| scientific article; zbMATH DE number 4047662 (Why is no real title available?) | 1988-01-01 | Paper |
Distributed match-making
Algorithmica | 1988-01-01 | Paper |
Tape versus queue and stacks: The lower bounds
Information and Computation | 1988-01-01 | Paper |
Counting is easy
Journal of the ACM | 1988-01-01 | Paper |
Locality, Communication, and Interconnect Length in Multicomputers
SIAM Journal on Computing | 1988-01-01 | Paper |
| scientific article; zbMATH DE number 3988713 (Why is no real title available?) | 1986-01-01 | Paper |
| scientific article; zbMATH DE number 3958735 (Why is no real title available?) | 1986-01-01 | Paper |
| scientific article; zbMATH DE number 4009785 (Why is no real title available?) | 1986-01-01 | Paper |
| scientific article; zbMATH DE number 3928765 (Why is no real title available?) | 1986-01-01 | Paper |
An Optimal Simulation of Counter Machines
SIAM Journal on Computing | 1985-01-01 | Paper |
An Optimal Simulation of Counter Machines: The ACM Case
SIAM Journal on Computing | 1985-01-01 | Paper |
Square time is optimal for simulation of one pushdown store or one queue by an oblivious one-head tape unit
Information Processing Letters | 1985-01-01 | Paper |
An \(n^{1.618}\) lower bound on the time to simulate one queue or two pushdown stores by one tape
Information Processing Letters | 1985-01-01 | Paper |
| scientific article; zbMATH DE number 3965440 (Why is no real title available?) | 1984-01-01 | Paper |
| scientific article; zbMATH DE number 3943032 (Why is no real title available?) | 1984-01-01 | Paper |
On the power of real-time two-way multihead finite automata with jumps
Information Processing Letters | 1984-01-01 | Paper |
On two-tape real-time computation and queues
Journal of Computer and System Sciences | 1984-01-01 | Paper |
| scientific article; zbMATH DE number 3825170 (Why is no real title available?) | 1983-01-01 | Paper |
| scientific article; zbMATH DE number 3750291 (Why is no real title available?) | 1982-01-01 | Paper |
| scientific article; zbMATH DE number 3750292 (Why is no real title available?) | 1982-01-01 | Paper |
| scientific article; zbMATH DE number 3759551 (Why is no real title available?) | 1982-01-01 | Paper |
On efficient simulations of multicounter machines
Information and Control | 1982-01-01 | Paper |
| scientific article; zbMATH DE number 3713185 (Why is no real title available?) | 1981-01-01 | Paper |
A note on dpda transductions of {0,1}<sup>∗</sup>and inverse dpda transductions of the dyck set
International Journal of Computer Mathematics | 1981-01-01 | Paper |
How well can a graph be n-colored?
Discrete Mathematics | 1981-01-01 | Paper |
| scientific article; zbMATH DE number 3692651 (Why is no real title available?) | 1980-01-01 | Paper |
| scientific article; zbMATH DE number 3684912 (Why is no real title available?) | 1980-01-01 | Paper |
| scientific article; zbMATH DE number 3657127 (Why is no real title available?) | 1980-01-01 | Paper |
| scientific article; zbMATH DE number 3657128 (Why is no real title available?) | 1980-01-01 | Paper |
| scientific article; zbMATH DE number 3673532 (Why is no real title available?) | 1980-01-01 | Paper |
| scientific article; zbMATH DE number 3673533 (Why is no real title available?) | 1980-01-01 | Paper |
| scientific article; zbMATH DE number 3696502 (Why is no real title available?) | 1980-01-01 | Paper |
| scientific article; zbMATH DE number 3700206 (Why is no real title available?) | 1980-01-01 | Paper |
Achievable high scores of \(\varepsilon\)-moves and running times in DPDA computations
Information Processing Letters | 1980-01-01 | Paper |
| scientific article; zbMATH DE number 3646279 (Why is no real title available?) | 1979-01-01 | Paper |
| scientific article; zbMATH DE number 3648124 (Why is no real title available?) | 1979-01-01 | Paper |
Stable string languages of lindenmayer systems
Information and Control | 1978-01-01 | Paper |
A note on the recursive enumerability of some classes of recursively enumerable languages
Information Sciences | 1978-01-01 | Paper |
On inverse deterministic pushdown transductions
Journal of Computer and System Sciences | 1978-01-01 | Paper |
| scientific article; zbMATH DE number 3550189 (Why is no real title available?) | 1977-01-01 | Paper |
Context sensitive table linden mayer languages and a relation to the LBA problem
Information and Control | 1977-01-01 | Paper |
Growth Functions Associated with Biological Development
The American Mathematical Monthly | 1976-01-01 | Paper |
On a problem in the collective behavior of automata
Discrete Mathematics | 1976-01-01 | Paper |
Deterministic Lindenmayer languages, nonterminals and homomorphisms
Theoretical Computer Science | 1976-01-01 | Paper |
| scientific article; zbMATH DE number 3459899 (Why is no real title available?) | 1974-01-01 | Paper |
| scientific article; zbMATH DE number 3470029 (Why is no real title available?) | 1974-01-01 | Paper |
| scientific article; zbMATH DE number 3443190 (Why is no real title available?) | 1973-01-01 | Paper |
Sexually reproducing cellular automata
Mathematical Biosciences | 1973-01-01 | Paper |
| scientific article; zbMATH DE number 3398797 (Why is no real title available?) | 1972-01-01 | Paper |
