Paul Vitányi | Academic Influence

Paul Vitányi's AcademicInfluence.com Rankings

Paul Vitányi

Computer Science

#1824

World Rank

#1892

Historical Rank

Theoretical Computer Science

#46

World Rank

#46

Historical Rank

computer-science Degrees

Paul Vitányi

Mathematics

#4517

World Rank

#6401

Historical Rank

Measure Theory

#617

World Rank

#850

Historical Rank

mathematics Degrees

Download Badge

Computer Science
Mathematics

Paul Vitányi's Degrees

PhD Mathematics University of Amsterdam

Why Is Paul Vitányi Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Paul Michael Béla Vitányi is a Dutch computer scientist, Professor of Computer Science at the University of Amsterdam and researcher at the Dutch Centrum Wiskunde & Informatica. Biography Vitányi was born in Budapest to a Dutch mother and a Hungarian father. He received his degree of mathematical engineer from Delft University of Technology in 1971 and his Ph.D. from the Free University of Amsterdam in 1978.

(See a Problem?)

Paul Vitányi's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

An Introduction to Kolmogorov Complexity and Its Applications (1993) (3447)
The Google Similarity Distance (2004) (1882)
The similarity metric (2001) (1228)
Clustering by compression (2003) (1032)
An Introduction to Kolmogorov Complexity and Its Applications (1997) (635)
An Introduction to Kolmogorov Complexity and Its Applications (1997) (543)
Theories of learning (1993) (505)
Information distance (1998) (483)
Simplicity: a unifying principle in cognitive science? (2003) (392)
Minimum description length induction, Bayesianism, and Kolmogorov complexity (1999) (264)
Algorithmic Clustering of Music Based on String Compression (2004) (261)
Clustering by compression (2003) (225)
Kolmogorov Complexity and its Applications (1991) (223)
Atomic shared register access by asynchronous hardware (1986) (196)
An Introduction to Kolmogorov Complexity (2008) (174)
Shannon Information and Kolmogorov Complexity (2004) (170)
Kolmogorov's structure functions and model selection (2002) (163)
Automatic Meaning Discovery Using Google (2006) (150)
Algorithmic statistics (2000) (144)
Randomness (2001) (124)
Inductive reasoning and Kolmogorov complexity (1989) (119)
‘Ideal learning’ of natural language: Positive results about learning from positive evidence (2007) (114)
Normalized Information Distance (2008) (94)
The miraculous universal distribution (1997) (92)
The Generalized Universal Law of Generalization (2001) (84)
Locality, Communication, and Interconnect Length in Multicomputers (1988) (84)
Learning Simple Concept Under Simple Distributions (1991) (83)
Meaningful Information (2001) (81)
Quantum Kolmogorov complexity based on classical descriptions (2001) (79)
Kolmogorov Complexity and Information Theory. With an Interpretation in Terms of Questions and Answers (2003) (76)
Time and Space Bounds for Reversible Simulation (2001) (75)
Algorithmic clustering of music (2003) (74)
Average Case Complexity Under the Universal Distribution Equals Worst-Case Complexity (1992) (67)
Reversibility and adiabatic computation: trading time and space for energy (1996) (64)
How to share concurrent wait-free variables (1996) (64)
Clustering Fetal Heart Rate Tracings by Compression (2006) (62)
The probabilistic analysis of language acquisition: Theoretical, computational, and experimental analysis (2010) (60)
Distributed elections in an archimedean ring of processors (1984) (60)
Two decades of applied Kolmogorov complexity: in memoriam Andrei Nikolaevich Kolmogorov 1903-87 (1988) (59)
Atomic Multireader Register (1987) (58)
Kolmogorov's structure functions with an application to the foundations of model selection (2002) (49)
Wait-free Test-and-Set (Extended Abstract) (1992) (48)
Time, space, and energy in reversible computing (2005) (48)
Three approaches to the quantitative definition of information in an individual pure quantum state (1999) (48)
How well can a graph be n-colored? (1981) (45)
Kolmogorov Random Graphs and the Incompressibility Method (1999) (44)
Universal similarity (2005) (43)
Nonapproximability of the normalized information distance (2009) (42)
Tape versus Queue and Stacks: The Lower Bounds (1988) (41)
Thermodynamics of computation and information distance (1993) (41)
On the importance of having an identity or, is consensus really universal? (2000) (40)
Bounded concurrent timestamp systems using vector clocks (2001) (39)
A Fast Quartet tree heuristic for hierarchical clustering (2011) (39)
Randomized naming using wait-free shared variables (1998) (39)
Information Distance in Multiples (2009) (38)
Distributed match-making (1988) (37)
Minimum Description Length Model Selection - Problems and Extensions (2001) (36)
Rate Distortion and Denoising of Individual Data Using Kolmogorov Complexity (2004) (35)
Normalized Compression Distance of Multisets with Applications (2012) (35)
Reversible simulation of irreversible computation (1996) (35)
A theory of learning simple concepts under simple distributions and average case complexity for the universal distribution (1989) (35)
Applying MDL to learn best model granularity (2000) (35)
A New Approach to Formal Language Theory by Kolmogorov Complexity (1989) (34)
Sexually reproducing cellular automata (1973) (34)
Similarity of Objects and the Meaning of Words (2006) (34)
Automatic Extraction of Meaning from the Web (2006) (30)
The Power and Perils of MDL (2006) (30)
Proceedings of the Second European Conference on Computational Learning Theory (1995) (30)
Normalized Web Distance and Word Similarity (2009) (30)
Identification of probabilities (2017) (27)
Distributed match-making for processes in computer networks (1986) (26)
The Power of the Queue (1986) (26)
Language Learning From Positive Evidence, Reconsidered: A Simplicity-Based Approach (2013) (26)
Applications of Kolmogorov Complexity in the Theory of Computation (1990) (24)
Lindenmayer systems: structure, languages, and growth functions (1978) (24)
On Prediction by Data Compression (1997) (23)
Reversible Simulation of Irreversible Computation by Pebble Games (1997) (23)
A discipline of evolutionary programming (1999) (23)
A Proof Technique for Register Automicity (1988) (22)
Sharpening Occam's razor (2002) (22)
Approximating Rate-Distortion Graphs of Individual Data: Experiments in Lossy Compression and Denoising (2006) (22)
Structure of growth in Lindenmayer systems (1973) (22)
A New Quartet Tree Heuristic for Hierarchical Clustering (2006) (22)
Ideal MDL and Its Relation To Bayesianism (1996) (21)
Algorithmic information theory (2008) (20)
Algorithmic probability (2007) (20)
Optimality of Wait-Free Atomic Multiwriter Variables (1992) (19)
Combinatorics and Kolmogorov complexity (1991) (19)
New applications of the incompressibility method: Part II (1998) (19)
How to Share Concurrent Asynchronous Wait-Free Varaibles (Preliminary Version) (1989) (18)
The average‐case area of Heilbronn‐type triangles * (1999) (18)
A lower bound on the average-case complexity of shellsort (1999) (17)
Optimal routing tables (1996) (17)
New Applications of the Incompressibility Method (1999) (17)
Randomized two-process wait-free test-and-set (2001) (17)
On the Size of D0L Languages (1974) (17)
Space-efficient Routing Tables for Almost All Networks and the Incompressibility Method (1999) (17)
Kolmogorov Complexity Arguments in Combinatorics (1994) (16)
Physics and the New Computation (1995) (16)
Mutual search (1999) (16)
Similarity and denoising (2013) (16)
Algorithmic statistics and Kolmogorov’s Structure Functions (2005) (16)
Philosophical Issues in Kolmogorov Complexity (1992) (15)
Nonsequentail Computation and Laws of Nature (1986) (15)
Depth as Randomness Deficiency (2008) (15)
On proving register atomicity (1987) (14)
How Incomputable Is Kolmogorov Complexity? (2020) (14)
Atomic Shared Register Access by Asynchronous Hardware (Detailed Abstract) (1986) (14)
Analysis of Sorting Algorithms by Kolmogorov Complexity (A Survey) (2009) (14)
An n1.618 Lower Bound on the Time to Simulate One Queue or Two Pushdown Stores by One Tape (1985) (14)
Distributed match-making for processes in computer networks (preliminary version) (1985) (13)
Approximation of the Two-Part MDL Code (2006) (13)
Growth of Strings in Context Dependent Lindenmayer Systems (1974) (12)
A very simple construction for atomic multiwriter register (1987) (12)
On the Simulation of Many Storage Heads by One (1984) (12)
Registers (2006) (12)
Computational Machine Learning in Theory and Praxis (1995) (12)
Area penalty for sublinear signal propagation delay on chip (1985) (12)
An Optimal Simulation of Counter Machines (1985) (11)
Two heads are better than two tapes (1994) (11)
Simplicity, information, Kolmogorov complexity and prediction (2002) (11)
Theory Of Thermodynamics Of Computation (1992) (11)
Average-case analysis of algorithms using Kolmogorov complexity (2000) (11)
Applying MDL to Learning Best Model Granularity (2000) (11)
Square Time is Optimal for Simulation of One Pushdown Store or One Queue by an Oblivious One-Head Tape Unit (1985) (10)
On Two-Tape Real-Time Computation and Queues (1984) (10)
Time-driven algorithms for distributed control (1985) (10)
Algorithmic rate-distortion theory (2004) (10)
Multiprocessor architectures and physical law (1994) (10)
On the power of real-time turing machines under varying specifications (1980) (10)
Mathematical theory of thermodynamics of computation (1992) (9)
Big omega versus the wild functions (1985) (9)
Randomized wait-free test-and-set (1991) (8)
Model selection for neural networks: comparing MDL and NIC (1994) (8)
Deterministic Lindenmayer Languages, Nonterminals and Homomorphisms (1976) (8)
Growth Functions Associated with Biological Development. (1976) (8)
Statistical properties of finite sequences with high Kolmogorov complexity (1994) (8)
One queue or two pushdown stores take square time on a one-head tape unit (1984) (8)
Compression-Based Similarity (2011) (8)
Real-Time Simulation of Multicounters by Oblivious One-Tape Turing Machines (1982) (7)
Conditional Kolmogorov complexity and universal probability (2012) (7)
Individual communication complexity (2003) (7)
Average-Case Complexity of Shellsort (1999) (7)
Stable String Languages of Lindenmayer Systems (1978) (7)
On Algorithmic Rate-Distortion Function (2006) (6)
Normalized Google Distance of Multisets with Applications (2013) (6)
Exact Expression For Information Distance (2014) (6)
An Optimal Simulation of Counter Machines: The ACM Case (1985) (6)
Errata to "Atomic Shared Register Access by Asynchronous Hardware" (1987) (6)
Linear Time Simulation of Multihead Turing Machines with Head-to-Head Jumps (1977) (6)
Development, growth and time (1985) (6)
The expected size of Heilbronn's triangles (1999) (6)
Proceedings of the 8th International Workshop on Distributed Algorithms (1994) (6)
Two heads are better than two tapes (1997) (6)
Simple Wait-Free Multireader Registers (2002) (5)
On a problem in the collective behavior of automata (1976) (5)
Algorithm Clustering of Music (2003) (5)
A Modest Proposal for Communication Costs in Multicomputers (1988) (5)
Drug output of unvented jet nebulizers as a function of time. (2003) (5)
Tolstoy’s Mathematics in War and Peace (2001) (4)
Square time is optimal for simulation of one pushdown store by an oblivious one-head tape unit (1984) (4)
About the Lifespan of Peer to Peer Networks, (2006) (4)
Normalized Information Distance and Whole Mitochondrial Genome Phylogeny Analysis (2001) (4)
Randomized Wait-Free Naming (1994) (4)
Andrei Nikolaevich Klomogorov (1988) (4)
Raymond J. Solomonoff 1926-2009 (2011) (4)
On a Generalized Ruin Problem (2001) (4)
Applications of algorithmic information theory (2007) (4)
Genetic Fitness Optimization Using Rapidly Mixing Markov Chains (1996) (4)
Simple multireader registers using time-stamp schemes (1987) (3)
The Quantum Computing Challenge (2001) (3)
Google Teaches Computer the Meaning of Words (2005) (3)
Counting is easy (1988) (3)
On Empirical Entropy (2011) (3)
Context-variable Lindenmayer systems and some simple regenerative structures (1972) (3)
Kolmogorov Complexity and Applications (2006) (3)
Computational Learning Theory, Second European Conference, EuroCOLT '95, Barcelona, Spain, March 13-15, 1995, Proceedings (1995) (3)
Algorithms and Complexity (2000) (3)
On the Power of Real-Time Two-Way Multihead Finite Automata With Jumps (1984) (3)
Normalized Information Distance is Not Semicomputable (2010) (3)
On Inverse Deterministic Pushdown Transductions (1978) (3)
Individual Communication Complexity: Extended Abstract (2004) (3)
Computing the perimeter of a set of rectangles : (preprint) (1979) (3)
Universal generalization and universal inter-item confusability (2001) (3)
Fast Whole-Genome Phylogeny of the COVID-19 Virus SARS-CoV-2 by Compression (2020) (3)
Information Distance: New Developments (2012) (3)
Average-Case Complexity of Shellsort (Preliminary version) (1999) (3)
Weighted Distributed Match-Making (1988) (3)
On the average‐case complexity of Shellsort (1999) (2)
Multihead and multitape real-time turing machines : (preprint) (1979) (2)
A note on the recursive enumerability of some classes of recursively enumerable languages (1978) (2)
On the size of dol languages : (prepublication) (1974) (2)
Andrey Nikolaevich Kolmogorov (2007) (2)
Dol-languages and a feasible solution for a word problem (1972) (2)
Rate Distortion Theory for Individual Data (2004) (2)
Context Sensitive Table Lindenmayer Languages and a Relation to the LBA Problem (1977) (2)
Signal propagation delay, wire length distribution and the efficiency of VLSI circuits (1984) (2)
Average-Case Analysis Using Kolmogorov Complexity (1997) (2)
Natural Halting Probabilities , Partial Randomness , and Zeta Functions (2006) (2)
Non-sequential computation and laws of nature (1986) (2)
On Logical Depth and the Running Time of Shortest Programs (2013) (2)
A Protocol for Randomized Anonymous Two-process Wait-free Test-and-Set with Finite-state Verification (2002) (2)
On Efficient Simulations of Multicounter Machines (1982) (2)
Algorithmic Chaos (2003) (2)
Fast Whole-Genome Phylogeny by Compression: the COVID-19 case (2021) (2)
Two-tape real-time computation : (preprint) (1980) (2)
Distributed control in computer networks and cross-sections of colored multidimensional bodies (1986) (1)
A note on weighted distributed match-making (2008) (1)
Towards an algorithmic statistics (extended abstract) (2000) (1)
Algorithmic Identification of Probabilities (2013) (1)
A note on dpda transductions of {0,1}∗ and inverse dpda transductions of the dyck set (1981) (1)
Relativized Obliviousness (1980) (1)
The Simple Roots of Real-Time Computation Hierarchies (Preliminary Version) (1984) (1)
Computational Depth of Infinite Strings Revisited (2007) (1)
Corrigendum to "On the rate of decrease in logical depth" [Theor. Comput. Sci. 702 (2017) 60-64] by L.F. Antunes, A. Souto, and P.M.B. Vitányi (2019) (1)
Remembering Kolmogorov (2011) (1)
Real-time simulation of multicounters by oblivious one-tape turing machines (Preliminary Draft) (1982) (1)
Distributed elections in a ring of processors using Archimedean time (1984) (1)
Randomized Wait-Free Distributed Naming (1994) (1)
Correction to "Algorithmic statistics" (2002) (1)
Ray Solomonoff, Founding Father of Algorithmic Information Theory (2010) (1)
Algorithmic Arguments in Physics of Computation (1995) (1)
Inductive reasoning (1992) (1)
Distributed Algorithms: 8th International Workshop, Wdag'1994 Terschelling, the Netherlands September 29-October 1, 1994 : Proceedings (1994) (1)
On Time-Bounded Incompressibility of Compressible Strings (2008) (1)
Web Similarity (2015) (1)
On the rate of decrease in logical depth (2017) (1)
Towards an Algorithmic Statistics (2000) (1)
Circuit topology, signal propagation delay and the efficiency of VLSI circuits (1984) (1)
A Randomized Algorithm for Two-Process Wait-Free Test-and-Set (1991) (1)
Asshuku ni Motozuita Hanyou na Ruijido Sokuteihou (2006) (1)
A Theory of Lossy Compression for Individual Data (2004) (1)
Web Similarity in Sets of Search Terms Using Database Queries (2015) (1)
Fast Phylogeny of SARS-CoV-2 by Compression (2022) (1)
The Incompressibility Method (2000) (0)
On Lossy Compression ( Extended Abstract ) (2005) (0)
On the Power of Real-Time Machines Under Varying Specifications (Extended Abstract) (1980) (0)
Algorithmic Prefix Complexity (2019) (0)
Mutual Search (abstract) (1997) (0)
Digraphs Associated with DOL Systems (1975) (0)
A note on nonrecursive and deterministic lindenmayer languages : (prepublication) (1973) (0)
06051 Abstracts Collection -- Kolmogorov Complexity and Applications (2006) (0)
Correction to "Quantum Kolmogorov complexity based on classical descriptions" (2002) (0)
Physics of computation and the quantum computing challenge (1997) (0)
Kolmogorov Complexity and Applications, 29.01. - 03.02.2006 (2006) (0)
Logarithmic signal propagation delay and the efficiency of VLSI circuits (1985) (0)
Collection Kolmogorov Complexity and Applications — Dagstuhl Seminar — (2006) (0)
C C ] 2 7 A ug 2 00 2 Meaningful Information ⋆ ( Extended Abstract ) (2002) (0)
A Tour of Algorithmics (1996) (0)
Algorithmics and complexity theory (2001) (0)
THE SIMPLE ROOTS OF REAL-TIME COMPUTATION IDERARClllES* (Preliminary (2006) (0)
Simple Optimal Wait-free Multireader Registers (2002) (0)
Identification of Probabilities of Languages (2012) (0)
Achievable High Scores of epsilon-Moves and Running Times in DPDA Computations (1980) (0)
Achievable high scores of -moves and running times in dpda computation : (prepublication) (1976) (0)
Efficient implementations of multicounter machines on oblivious turing machines, acyclic logic networks, and vlsi : (preprint) (1981) (0)
Physical time growth functions associated with developmental models operating in physiological time : (preprint) (1978) (0)
Randomized Wait-free Naming Randomized Wait-free Naming (1994) (0)
Kolmogorov random graphs (1997) (0)
Tales of Huffman (2006) (0)
erratum: “ Two heads are better that two tapes” (1997) (0)
Description Complexity and Applications (1998) (0)
On the Simulation of Many Storage Heads by a Single One (Extended Abstract) (1983) (0)
Average-Case Analysis Using Kolgomorov Complexity (Abstract) (1998) (0)
Kolynogorov's structure functions, nonprobabilistic statistics, and the foundations of model selection (2003) (0)
Minimum Description Length Inductin, Bayesianism (1998) (0)
PUSHDOWN STORES BY ONE TAPE (2006) (0)
Growth functions associated with biological development : (prepublication) (1974) (0)
Optimizing Quartet Trees Through Monte Carlo Methods (2007) (0)
Randomness as Unpredictability 3 Randomness in Terms of Expectations 4 Randomness as Incompressibility (2006) (0)
The erdős graph and the beast (1999) (0)
Automatentheorie, complexiteit en algoritmen [Automata theory, complexity and algorithms] (1983) (0)
MDL induction, Bayesianism, and Kolmogorov complexity (1998) (0)
A great mind (2008) (0)
Combinatorial algorithms in bioinformatics (2004) (0)
Average-case complexity of Stacksort and Queuesort (2000) (0)
Corrigendum to “On the rate of decrease in logical depth” [Theoret. Comput. Sci. 702 (2017) 60–64] (2018) (0)
Jan Karel, The Decider (2011) (0)
Algorithmic statistics-Information Theory, IEEE Transactions on (2001) (0)
The Search for Meaning (2020) (0)
H O ] 1 8 O ct 2 00 1 Tolstoy ’ s Mathematics in “ War and Peace ” (2001) (0)
Algorithmic statistics in bio-informatics (2004) (0)
On the length of the Monopolist Game (2000) (0)
Córdoba, Argentina September 20–24, 2004 (2005) (0)
Automatic Semantics Using Google (2004) (0)
Correction to: Kolmogorov complexity arguments in Combinatorics (1995) (0)
6 IS MATHEMATICS INVADING HUMAN CELLS? IMPRESSIONS FROM A COLLABORATION WITH DIABETES DOCTORS / Bernhelm (2013) (0)
Mutual Search (Extended Abstract) (1998) (0)
Products of Interest (2004) (0)
Tolstoy’s Mathematics in War and Peace (2012) (0)
Turing Machines and Understanding Computational Complexity (2012) (0)
Digraphs associated with dol systems : (prepublication) (1975) (0)
N ov 2 00 5 Algorithmic Rate-Distortion Theory (2004) (0)
How good can a graph be n-colored? : (preprint) (1977) (0)
Space-Energy Trade-off in Reversible Simulations (1996) (0)
4 F eb 2 00 2 Optimal Wait-free Multireader Registers ∗ (2002) (0)
Real-time simulation of multicounters by oblivious one-tape turing machines : (preprint) (1982) (0)
Time-bounded incompressibility of compressible strings and sequences (2008) (0)
Efficient simulations of multicounter machines (preliminary version) : (preprint) (1982) (0)
Universal similarity based on compression (2006) (0)
Stable string languages of lindenmayer systems : (prepublication) (1974) (0)
Meaningful information: (Extended abstract) (2002) (0)
Algorithmic Identiﬁcation of Probabilities (2014) (0)
Some Examples of Average-case Analysis by the Imcompressibility Method (1999) (0)
Algorithmic chaos and the incompressibility method (2007) (0)
Physics and Computation (1993) (0)
The Beatles Eleanor Rigby Michelle Eric Clapton Cocaine Layla (2004) (0)
New applications of the incompressibility method (extended abstract) (1999) (0)
Physics, Information, and Computation (2019) (0)
On inverse deterministic pushdown transductions : (prepublication) (1976) (0)
Distortion-rate theory for individual data (2005) (0)
Resource-Bounded Complexity (2019) (0)
A tribute to referees (2004) (0)
The 4 th International Conference on Web-based Learning (ICWL2005) Presentation Schedule (2005) (0)
Structure of growth in lindenmayer systems : (proceedings knaw series a, _7_6 (1973), nr 3, indagationes mathematicae, _3_5 (1973), p 247-253) (1973) (0)
Algorithmic Statistics (Monographs in Computer Science) (2005) (0)
Review of Expressions For Information Distance (2014) (0)
Algorithmic Complexity (2019) (0)
Quantum Computing Moore's Law (0)
Normalized Compression Distance of Multiples (2012) (0)
Time and Space Bounds for Reversible Simulation ? (Extended Abstract) (2001) (0)
Relativized obliviousness : (preprint) (1980) (0)
The home of the Big Whopper (1985) (0)
Centennial Seminar on Kolmogorov Complexity and Applications (Dagstuhl Seminar 03181) (2021) (0)
Real-time turing machines under varying specifications, 2 : (preprint) (1980) (0)
Optimal Wait-free Multireader Registers (2002) (0)
On the logical depth function (2013) (0)
PROBLEMS IN THE PRODUCTION AND DEGASSING OF VANADIUM. (1969) (0)
Logical depth for reversible Turing machines with an application to the rate of decrease in logical depth for general Turing machines (2019) (0)
Combinatoriële algoritmen in de bioinformatica (2004) (0)
Average-Case Analysis via Incompressibility (1997) (0)
Genetics of reproducing automata : (prepublication) (1974) (0)

This paper list is powered by the following services:

Other Resources About Paul Vitányi

en.wikipedia.org

What Schools Are Affiliated With Paul Vitányi?

Paul Vitányi is affiliated with the following schools:

Image Attributions

Image Source for Paul Vitányi