Paul M. B. Vitányi

According to our database1, Paul M. B. Vitányi authored at least 236 papers between 1974 and 2018.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2018
On the average-case complexity of Shellsort.
Random Struct. Algorithms, 2018

2017
Exact Expression For Information Distance.
IEEE Trans. Information Theory, 2017

On the rate of decrease in logical depth.
Theor. Comput. Sci., 2017

Identification of Probabilities.
CoRR, 2017

2016
Registers.
Encyclopedia of Algorithms, 2016

2015
Normalized Compression Distance of Multisets with Applications.
IEEE Trans. Pattern Anal. Mach. Intell., 2015

On The Average-Case Complexity of Shellsort.
CoRR, 2015

Web Similarity.
CoRR, 2015

2014
Exact Expression For Information Distance.
CoRR, 2014

A Fast Quartet Tree Heuristic for Hierarchical Clustering.
CoRR, 2014

2013
Language Learning From Positive Evidence, Reconsidered: A Simplicity-Based Approach.
topiCS, 2013

Conditional Kolmogorov complexity and universal probability.
Theor. Comput. Sci., 2013

On the logical depth function
CoRR, 2013

Language learning from positive evidence, reconsidered: A simplicity-based approach
CoRR, 2013

Algorithmic Identification of Probabilities.
CoRR, 2013

Normalized Google Distance of Multisets with Applications.
CoRR, 2013

On Logical Depth and the Running Time of Shortest Programs.
CoRR, 2013

2012
Approximating Rate-Distortion Graphs of Individual Data: Experiments in Lossy Compression and Denoising.
IEEE Trans. Computers, 2012

Normalized Compression Distance of Multiples
CoRR, 2012

Conditional Kolmogorov Complexity and Universal Probability
CoRR, 2012

Turing Machines and Understanding Computational Complexity
CoRR, 2012

Information Distance: New Developments
CoRR, 2012

2011
Information Distance in Multiples.
IEEE Trans. Information Theory, 2011

A Fast Quartet tree heuristic for hierarchical clustering.
Pattern Recognition, 2011

Nonapproximability of the normalized information distance.
J. Comput. Syst. Sci., 2011

Compression-based Similarity
CoRR, 2011

On Empirical Entropy
CoRR, 2011

Compression-Based Similarity.
Proceedings of the First International Conference on Data Compression, 2011

2010
Normalized Web Distance and Word Similarity.
Proceedings of the Handbook of Natural Language Processing, Second Edition., 2010

Rate distortion and denoising of individual data using Kolmogorov complexity.
IEEE Trans. Information Theory, 2010

Information Distance
CoRR, 2010

Normalized Information Distance is Not Semicomputable
CoRR, 2010

The probabilistic analysis of language acquisition: Theoretical, computational, and experimental analysis
CoRR, 2010

Ray Solomonoff, Founding Father of Algorithmic Information Theory.
Algorithms, 2010

2009
Approximation of the Two-Part MDL Code.
IEEE Trans. Information Theory, 2009

Turing machine.
Scholarpedia, 2009

Depth as Randomness Deficiency.
Theory Comput. Syst., 2009

Time-bounded incompressibility of compressible strings and sequences.
Inf. Process. Lett., 2009

Nonapproximablity of the Normalized Information Distance
CoRR, 2009

Distributed elections in an Archimedean ring of processors
CoRR, 2009

Analysis of Sorting Algorithms by Kolmogorov Complexity (A Survey)
CoRR, 2009

Normalized Web Distance and Word Similarity
CoRR, 2009

Information Distance in Multiples
CoRR, 2009

2008
An Introduction to Kolmogorov Complexity and Its Applications, Third Edition.
Texts in Computer Science, Springer, ISBN: 978-0-387-49820-1, 2008

Registers.
Proceedings of the Encyclopedia of Algorithms, 2008

On Time-Bounded Incompressibility of Compressible Strings
CoRR, 2008

Algorithmic information theory
CoRR, 2008

Normalized Information Distance
CoRR, 2008

Depth as Randomness Deficiency
CoRR, 2008

2007
The Google Similarity Distance.
IEEE Trans. Knowl. Data Eng., 2007

Andrey Nikolaevich Kolmogorov.
Scholarpedia, 2007

Applications of algorithmic information theory.
Scholarpedia, 2007

Algorithmic probability.
Scholarpedia, 2007

Individual communication complexity.
J. Comput. Syst. Sci., 2007

The Power and Perils of MDL.
Proceedings of the IEEE International Symposium on Information Theory, 2007

2006
Meaningful Information.
IEEE Trans. Information Theory, 2006

On the importance of having an identity or, is consensus really universal?.
Distributed Computing, 2006

Clustering fetal heart rate tracings by compression
CoRR, 2006

Tales of Huffman
CoRR, 2006

The Power and Perils of MDL
CoRR, 2006

About the Lifespan of Peer to Peer Networks
CoRR, 2006

Registers
CoRR, 2006

Approximating Rate-Distortion Graphs of Individual Data: Experiments in Lossy Compression and Denoising
CoRR, 2006

A New Quartet Tree Heuristic for Hierarchical Clustering
CoRR, 2006

Similarity of Objects and the Meaning of Words
CoRR, 2006

Similarity of Objects and the Meaning of Words.
Proceedings of the Theory and Applications of Models of Computation, 2006

About the Lifespan of Peer to Peer Networks, .
Proceedings of the Principles of Distributed Systems, 10th International Conference, 2006

06051 Abstracts Collection -- Kolmogorov Complexity and Applications.
Proceedings of the Kolmogorov Complexity and Applications, 29.01. - 03.02.2006, 2006

Automatic Meaning Discovery Using Google.
Proceedings of the Kolmogorov Complexity and Applications, 29.01. - 03.02.2006, 2006

A New Quartet Tree Heuristic for Hierarchical Clustering.
Proceedings of the Theory of Evolutionary Algorithms, 05.02. - 10.02.2006, 2006

Clustering Fetal Heart Rate Tracings by Compression.
Proceedings of the 19th IEEE International Symposium on Computer-Based Medical Systems (CBMS 2006), 2006

2005
Clustering by compression.
IEEE Trans. Information Theory, 2005

Universal Similarity
CoRR, 2005

Time, Space, and Energy in Reversible Computing
CoRR, 2005

Time, space, and energy in reversible computing.
Proceedings of the Second Conference on Computing Frontiers, 2005

2004
Kolmogorov's structure functions and model selection.
IEEE Trans. Information Theory, 2004

The similarity metric.
IEEE Trans. Information Theory, 2004

A Theory of Lossy Compression for Individual Data
CoRR, 2004

Shannon Information and Kolmogorov Complexity
CoRR, 2004

The Google Similarity Distance
CoRR, 2004

Algorithmic Clustering of Music Based on String Compression.
Computer Music Journal, 2004

Algorithmic Clustering of Music.
Proceedings of the 4th International Conference on WEB Delivering of Music (WEDELMUSIC 2004), 2004

Individual Communication Complexity: Extended Abstract.
Proceedings of the STACS 2004, 2004

2003
Kolmogorov Complexity and Information Theory. With an Interpretation in Terms of Questions and Answers.
Journal of Logic, Language and Information, 2003

Sharpening Occam's razor.
Inf. Process. Lett., 2003

Algorithmic Chaos
CoRR, 2003

Algorithmic Clustering of Music
CoRR, 2003

Clustering by compression
CoRR, 2003

Individual Communication Complexity
CoRR, 2003

The similarity metric.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

2002
Correction to "Quantum Kolmogorov complexity based on classical descriptions".
IEEE Trans. Information Theory, 2002

Correction to "Algorithmic statistics".
IEEE Trans. Information Theory, 2002

The average-case area of Heilbronn-type triangles.
Random Struct. Algorithms, 2002

Bounded concurrent timestamp systems using vector clocks.
J. ACM, 2002

Randomized two-process wait-free test-and-set.
Distributed Computing, 2002

Sharpening Occam's Razor
CoRR, 2002

Simple Wait-free Multireader Registers
CoRR, 2002

On the Importance of Having an Identity or, is Consensus really Universal?
CoRR, 2002

Kolmogorov's Structure Functions with an Application to the Foundations of Model Selection
CoRR, 2002

Simple Wait-Free Multireader Registers.
Proceedings of the Distributed Computing, 16th International Conference, 2002

A Protocol for Randomized Anonymous Two-process Wait-free Test-and-Set with Finite-state Verification.
Proceedings of the SIROCCO 9, 2002

Meaningful Information.
Proceedings of the Algorithms and Computation, 13th International Symposium, 2002

Kolmogorov's Structure Functions with an Application to the Foundations of Model Selection.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

Sharpening Occam's Razor.
Proceedings of the Computing and Combinatorics, 8th Annual International Conference, 2002

2001
Quantum Kolmogorov complexity based on classical descriptions.
IEEE Trans. Information Theory, 2001

Algorithmic statistics.
IEEE Trans. Information Theory, 2001

Quantum Kolmogorov Complexity Based on Classical Descriptions
CoRR, 2001

Time and Space Bounds for Reversible Simulation
CoRR, 2001

Randomness
CoRR, 2001

Bounded Concurrent Timestamp Systems Using Vector Clocks
CoRR, 2001

Randomized Two-Process Wait-Free Test-and-Set
CoRR, 2001

The Generalized Universal Law of Generalization
CoRR, 2001

The similarity metric
CoRR, 2001

Meaningful Information
CoRR, 2001

A New Approach to Formal Language Theory by Kolmogorov Complexity
CoRR, 2001

Two heads are better than two tapes
CoRR, 2001

Counting is Easy
CoRR, 2001

On a Generalized Ruin Problem.
Proceedings of the Approximation, 2001

Time and Space Bounds for Reversible Simulation.
Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

The Quantum Computing Challenge.
Proceedings of the Informatics - 10 Years Back. 10 Years Ahead., 2001

2000
Minimum description length induction, Bayesianism, and Kolmogorov complexity.
IEEE Trans. Information Theory, 2000

A discipline of evolutionary programming.
Theor. Comput. Sci., 2000

New applications of the incompressibility method: Part II.
Theor. Comput. Sci., 2000

Average-Case Analysis of Algorithms Using Kolmogorov Complexity.
J. Comput. Sci. Technol., 2000

A lower bound on the average-case complexity of shellsort.
J. ACM, 2000

Applying MDL to Learning Best Model Granularity
CoRR, 2000

Algorithmic Statistics
CoRR, 2000

Applying MDL to learn best model granularity.
Artif. Intell., 2000

On the Importance of Having an Identity or is Consensus Really Universal?
Proceedings of the Distributed Computing, 14th International Conference, 2000

The Incompressibility Method.
Proceedings of the SOFSEM 2000: Theory and Practice of Informatics, 27th Conference on Current Trends in Theory and Practice of Informatics, Milovy, Czech Republic, November 25, 2000

Three Approaches to the Quantitative Definition of Information in an Individual Pure Quantum State.
Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000

Towards an Algorithmic Statistics.
Proceedings of the Algorithmic Learning Theory, 11th International Conference, 2000

1999
Kolmogorov Random Graphs and the Incompressibility Method.
SIAM J. Comput., 1999

Space-efficient Routing Tables for Almost All Networks and the Incompressibility Method.
SIAM J. Comput., 1999

Mutual Search.
J. ACM, 1999

The Average-Case Area of Heilbronn-Type Triangles
CoRR, 1999

A Discipline of Evolutionary Programming
CoRR, 1999

Minimum Description Length Induction, Bayesianism, and Kolmogorov Complexity
CoRR, 1999

Mutual Search
CoRR, 1999

Average-Case Complexity of Shellsort
CoRR, 1999

Space-Efficient Routing Tables for Almost All Networks and the Incompressibility Method
CoRR, 1999

Average-Case Complexity of Shellsort (Preliminary version)
CoRR, 1999

New Applications of the Incompressibility Method.
Comput. J., 1999

Average-Case Complexity of Shellsort.
Proceedings of the Automata, 1999

New Applications of the Incompressibility Method.
Proceedings of the Automata, 1999

The Expected Size of Heilbronn's Triangles.
Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

Some Examples of Average-case Analysis by the Imcompressibility Method.
Proceedings of the Jewels are Forever, 1999

1998
Information Distance.
IEEE Trans. Information Theory, 1998

Randomized Naming Using Wait-Free Shared Variables.
Distributed Computing, 1998

New Applications of the Incompressibility Method: Part I
CoRR, 1998

New Applications of the Incompressibility Method: Part II
CoRR, 1998

Mutual Search (Extended Abstract).
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

Average-Case Analysis Using Kolgomorov Complexity (Abstract).
Proceedings of Computing: The Fourth Australasian Theory Symposium (CATS'98), 1998

1997
Erratum: "Two heads are better that two tapes".
J. ACM, 1997

Two heads are better than two tapes.
J. ACM, 1997

Reversibility and Adiabatic Computation: Trading Time and Space for Energy
CoRR, 1997

Reversible Simulation of Irreversible Computation by Pebble Games
CoRR, 1997

Average-Case Analysis via Incompressibility.
Proceedings of the Fundamentals of Computation Theory, 11th International Symposium, 1997

On Prediction by Data Compression.
Proceedings of the Machine Learning: ECML-97, 1997

Mutual Search (abstract).
Proceedings of the Computing and Combinatorics, Third Annual International Conference, 1997

Average-Case Analysis Using Kolmogorov Complexity.
Proceedings of the Advances in Algorithms, Languages, and Complexity, 1997

An introduction to Kolmogorov complexity and its applications, Second Edition.
Graduate Texts in Computer Science, Springer, ISBN: 978-1-4757-2606-0, 1997

1996
How to Share Concurrent Wait-Free Variables.
J. ACM, 1996

Optimal Routing Tables.
Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, 1996

Reversible Simulation of Irreversible Computation.
Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996

Genetic Fitness Optimization Using Rapidly Mixing Markov Chains.
Proceedings of the Algorithmic Learning Theory, 7th International Workshop, 1996

1995
A New Approach to Formal Language Theory by Kolmogorov Complexity.
SIAM J. Comput., 1995

Algorithmic Arguments in Physics of Computation.
Proceedings of the Algorithms and Data Structures, 4th International Workshop, 1995

Physics and the New Computation.
Proceedings of the Mathematical Foundations of Computer Science 1995, 1995

Computational Machine Learning in Theory and Praxis.
Proceedings of the Computer Science Today: Recent Trends and Developments, 1995

1994
Statistical Properties of Finite Sequences with High Kolmogorov Complexity.
Mathematical Systems Theory, 1994

Kolmogorov Complexity Arguments in Combinatorics.
J. Comb. Theory, Ser. A, 1994

Two heads are better than two tapes.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Randomized Wait-Free Naming.
Proceedings of the Algorithms and Computation, 5th International Symposium, 1994

Model selection for neural networks: comparing MDL and NIC.
Proceedings of the ESANN 1994, 1994

1993
Thermodynamics of computation and information distance.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

An introduction to Kolmogorov complexity and its applications.
Texts and Monographs in Computer Science, Springer, ISBN: 978-1-4757-3860-5, 1993

1992
The Power of the Queue.
SIAM J. Comput., 1992

A Note on Weighted Distributed Match-Making.
Mathematical Systems Theory, 1992

Inductive Reasoning and Kolmogorov Complexity.
J. Comput. Syst. Sci., 1992

Optimality of Wait-Free Atomic Multiwriter Variables.
Inf. Process. Lett., 1992

Average Case Complexity Under the Universal Distribution Equals Worst-Case Complexity.
Inf. Process. Lett., 1992

Wait-free Test-and-Set (Extended Abstract).
Proceedings of the Distributed Algorithms, 6th International Workshop, 1992

Philosophical Issues in Kolmogorov Complexity.
Proceedings of the Automata, Languages and Programming, 19th International Colloquium, 1992

Inductive reasoning.
Proceedings of the Language Computations, 1992

1991
Learning Simple Concept Under Simple Distributions.
SIAM J. Comput., 1991

Combinatorics and Kolmogorov Complexity.
Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30, 1991

An introduction to Kolmogorov - complexity and its applications ; part 1: theory.
CWI, 1991

1990
Kolmogorov Complexity and its Applications.
Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A), 1990

1989
A New Approach to Formal Language Theory by Kolmogorov Complexity (Preliminary Version).
Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

How to Share Concurrent Asynchronous Wait-Free Varaibles (Preliminary Version).
Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

A Theory of Learning Simple Concepts Under Simple Distributions and Average Case Complexity for the Universal Distribution (Extended Abstract)
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

Inductive Reasoning and Komogorov Complexity.
Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989

1988
Tape versus Queue and Stacks: The Lower Bounds
Inf. Comput., July, 1988

Locality, Communication, and Interconnect Length in Multicomputers.
SIAM J. Comput., 1988

Counting is easy.
J. ACM, 1988

Distributed Match-Making.
Algorithmica, 1988

A Proof Technique for Register Automicity.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1988

Two decades of applied Kolmogorov complexity: in memoriam Andrei Nikolaevich Kolmogorov 1903-87.
Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988

Weighted Distributed Match-Making.
Proceedings of the VLSI Algorithms and Architectures, 3rd Aegean Workshop on Computing, 1988

1987
Atomic Multireader Register.
Proceedings of the Distributed Algorithms, 1987

Errata to "Atomic Shared Register Access by Asynchronous Hardware"
Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987

1986
Distributed Match-Making for Processes in Computer Networks (Preliminary Version).
Operating Systems Review, 1986

Atomic Shared Register Access by Asynchronous Hardware (Detailed Abstract)
Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

The Power of the Queue.
Proceedings of the Structure in Complexity Theory, 1986

Nonsequentail Computation and Laws of Nature.
Proceedings of the VLSI Algorithms and Architectures, 1986

1985
An Optimal Simulation of Counter Machines: The ACM Case.
SIAM J. Comput., 1985

An Optimal Simulation of Counter Machines.
SIAM J. Comput., 1985

An n1.618 Lower Bound on the Time to Simulate One Queue or Two Pushdown Stores by One Tape.
Inf. Process. Lett., 1985

Square Time is Optimal for Simulation of One Pushdown Store or One Queue by an Oblivious One-Head Tape Unit.
Inf. Process. Lett., 1985

Logarithmic signal propagation delay and the efficiency of VLSI circuits.
Bulletin of the EATCS, 1985

Distributed Match-Making for Processes in Computer Networks (Preliminary Version).
Proceedings of the Fourth Annual ACM Symposium on Principles of Distributed Computing, 1985

Area Penalty for Sublinear Signal Propagation Delay on Chip (Preliminary Version)
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

1984
On the Simulation of Many Storage Heads by One.
Theor. Comput. Sci., 1984

On Two-Tape Real-Time Computation and Queues.
J. Comput. Syst. Sci., 1984

On the Power of Real-Time Two-Way Multihead Finite Automata With Jumps.
Inf. Process. Lett., 1984

Big omega versus the wild functions.
Bulletin of the EATCS, 1984

Distributed Elections in an Archimedean Ring of Processors (Preliminary Version)
Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

The Simple Roots of Real-Time Computation Hierarchies (Preliminary Version).
Proceedings of the Automata, 1984

1983
On the Simulation of Many Storage Heads by a Single One (Extended Abstract).
Proceedings of the Automata, 1983

1982
On Efficient Simulations of Multicounter Machines
Information and Control, 1982

Real-Time Simulation of Multicounters by Oblivious One-Tape Turing Machines
Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982

Efficient Simulations of Multicounter Machines.
Proceedings of the Automata, 1982

1981
How well can a graph be n-colored?
Discrete Mathematics, 1981

1980
Achievable High Scores of epsilon-Moves and Running Times in DPDA Computations.
Inf. Process. Lett., 1980

Relativized Obliviousness.
Proceedings of the Mathematical Foundations of Computer Science 1980 (MFCS'80), 1980

On the Power of Real-Time Machines Under Varying Specifications (Extended Abstract).
Proceedings of the Automata, 1980

1978
Stable String Languages of Lindenmayer Systems
Information and Control, May, 1978

On Inverse Deterministic Pushdown Transductions.
J. Comput. Syst. Sci., 1978

A note on the recursive enumerability of some classes of recursively enumerable languages.
Inf. Sci., 1978

1977
Context Sensitive Table Lindenmayer Languages and a Relation to the LBA Problem
Information and Control, March, 1977

Linear Time Simulation of Multihead Turing Machines with Head-to-Head Jumps.
Proceedings of the Automata, 1977

1976
Deterministic Lindenmayer Languages, Nonterminals and Homomorphisms.
Theor. Comput. Sci., 1976

On a problem in the collective behavior of automata.
Discrete Mathematics, 1976

1974
Growth of Strings in Context Dependent Lindenmayer Systems.
Proceedings of the L Systems, 1974

On the Size of D0L Languages.
Proceedings of the L Systems, 1974


  Loading...