Paul M. B. Vitányi

From MaRDI portal
Person:354146

Available identifiers

zbMath Open vitanyi.paul-m-bWikidataQ7154167 ScholiaQ7154167MaRDI QIDQ354146

List of research outcomes

PublicationDate of PublicationType
Algorithmic arguments in physics of computation2022-12-16Paper
Average-case analysis via incompressibility2022-12-09Paper
Randomized two-process wait-free test-and-set2020-12-03Paper
https://portal.mardi4nfdi.de/entity/Q51373522020-12-02Paper
Philosophical issues in Kolmogorov complexity2019-12-04Paper
Logical depth for reversible Turing machines with an application to the rate of decrease in logical depth for general Turing machines2019-06-06Paper
Corrigendum to: ``On the rate of decrease in logical depth by by L. F. Antunes, A. Souto, and P. M. B. Vitányi2019-05-02Paper
An introduction to Kolmogorov complexity and its applications2019-02-15Paper
Obituary: Ray Solomonoff, founding father of algorithmic information theory2018-08-20Paper
On the average‐case complexity of Shellsort2018-06-07Paper
On the rate of decrease in logical depth2017-11-06Paper
Exact Expression For Information Distance2017-10-19Paper
Approximation of the Two-Part MDL Code2017-08-08Paper
Information Distance in Multiples2017-07-27Paper
Rate Distortion and Denoising of Individual Data Using Kolmogorov Complexity2017-07-27Paper
Approximating Rate-Distortion Graphs of Individual Data: Experiments in Lossy Compression and Denoising2017-07-12Paper
Identification of probabilities2017-02-28Paper
Similarity and denoising2017-01-13Paper
Two heads are better than two tapes2016-09-01Paper
Bounded concurrent timestamp systems using vector clocks2015-10-30Paper
A lower bound on the average-case complexity of shellsort2015-09-19Paper
Optimal routing tables2015-09-11Paper
Thermodynamics of computation and information distance2015-05-07Paper
Conditional Kolmogorov complexity and universal probability2014-01-10Paper
Tolstoy's mathematics in ``War and peace2013-07-18Paper
Identification of Probabilities of Languages2012-08-24Paper
Nonapproximability of the normalized information distance2011-04-28Paper
A fast quartet tree heuristic for hierarchical clustering2011-01-31Paper
Time-bounded incompressibility of compressible strings and sequences2010-08-20Paper
Physics and the new computation2010-06-17Paper
Genetic fitness optimization using rapidly mixing Markov chains2010-04-27Paper
Depth as randomness deficiency2009-10-19Paper
Sharpening Occam's razor2009-03-23Paper
Normalized Information Distance2009-03-12Paper
Clustering by Compression2008-12-21Paper
The Similarity Metric2008-12-21Paper
Kolmogorov's Structure Functions and Model Selection2008-12-21Paper
Meaningful Information2008-12-21Paper
https://portal.mardi4nfdi.de/entity/Q35080212008-06-27Paper
An introduction to Kolmogorov complexity and its applications2008-06-04Paper
STACS 20042007-10-01Paper
`Ideal learning' of natural language: positive results about learning from positive evidence2007-10-01Paper
Individual communication complexity2007-08-23Paper
Theory and Applications of Models of Computation2007-04-30Paper
Correction to "CDMA systems in fading channels: admissibility, network capacity, and power control"2005-05-11Paper
Correction to "Algorithmic statistics"2005-05-11Paper
Mutual search2005-01-25Paper
https://portal.mardi4nfdi.de/entity/Q48086622004-08-12Paper
https://portal.mardi4nfdi.de/entity/Q44732302004-08-04Paper
https://portal.mardi4nfdi.de/entity/Q44719622004-08-03Paper
https://portal.mardi4nfdi.de/entity/Q44713842004-07-28Paper
https://portal.mardi4nfdi.de/entity/Q44371182003-12-07Paper
https://portal.mardi4nfdi.de/entity/Q44278792003-09-14Paper
Kolmogorov complexity and information theory. With an interpretation in terms of questions and answers2003-09-01Paper
The generalized universal law of generalization.2003-08-25Paper
https://portal.mardi4nfdi.de/entity/Q47807932002-11-21Paper
The average‐case area of Heilbronn‐type triangles*2002-08-08Paper
Algorithmic statistics2002-08-04Paper
Quantum Kolmogorov complexity based on classical descriptions2002-08-04Paper
https://portal.mardi4nfdi.de/entity/Q45350802002-06-12Paper
On the simulation of many storage heads by one2002-05-13Paper
https://portal.mardi4nfdi.de/entity/Q27668682002-01-28Paper
Time and space bounds for reversible simulation2002-01-27Paper
https://portal.mardi4nfdi.de/entity/Q49411652002-01-24Paper
https://portal.mardi4nfdi.de/entity/Q45256872001-01-24Paper
Applying MDL to learn best model granularity2000-10-26Paper
Minimum description length induction, Bayesianism, and Kolmogorov complexity2000-09-07Paper
A discipline of evolutionary programming2000-08-21Paper
New applications of the incompressibility method. II2000-06-04Paper
https://portal.mardi4nfdi.de/entity/Q49386272000-04-25Paper
The miraculous universal distribution2000-04-02Paper
Kolmogorov Random Graphs and the Incompressibility Method2000-03-19Paper
New Applications of the Incompressibility Method2000-01-17Paper
Average-case analysis of algorithms using Kolmogorov complexity2000-01-01Paper
Information distance1999-11-21Paper
Space-efficient Routing Tables for Almost All Networks and the Incompressibility Method1999-10-28Paper
https://portal.mardi4nfdi.de/entity/Q42502161999-06-17Paper
https://portal.mardi4nfdi.de/entity/Q43855091998-05-04Paper
Two heads are better than two tapes1998-02-17Paper
How to share concurrent wait-free variables1998-01-22Paper
https://portal.mardi4nfdi.de/entity/Q43370211997-05-19Paper
https://portal.mardi4nfdi.de/entity/Q43362711997-05-12Paper
Reversibility and adiabatic computation: trading time and space for energy1997-03-23Paper
https://portal.mardi4nfdi.de/entity/Q48656431996-06-26Paper
https://portal.mardi4nfdi.de/entity/Q48528851996-03-14Paper
Erratum to: Kolmogorov complexity arguments in combinatorics1995-06-30Paper
A New Approach to Formal Language Theory by Kolmogorov Complexity1995-05-30Paper
https://portal.mardi4nfdi.de/entity/Q43273181995-04-03Paper
Kolmogorov complexity arguments in combinatorics1995-01-12Paper
Statistical properties of finite sequences with high Kolmogorov complexity1994-08-10Paper
https://portal.mardi4nfdi.de/entity/Q40353221993-05-18Paper
https://portal.mardi4nfdi.de/entity/Q40233581993-01-23Paper
Optimality of wait-free atomic multiwriter variables1993-01-17Paper
Average case complexity under the universal distribution equals worst- case complexity1993-01-16Paper
The Power of the Queue1992-12-14Paper
Inductive reasoning and Kolmogorov complexity1992-09-27Paper
https://portal.mardi4nfdi.de/entity/Q40135571992-09-27Paper
A note on weighted distributed match-making1992-09-26Paper
Learning Simple Concepts under Simple Distributions1992-06-26Paper
https://portal.mardi4nfdi.de/entity/Q47321311989-01-01Paper
Distributed match-making1988-01-01Paper
Tape versus queue and stacks: The lower bounds1988-01-01Paper
https://portal.mardi4nfdi.de/entity/Q37840211988-01-01Paper
https://portal.mardi4nfdi.de/entity/Q37967181988-01-01Paper
Locality, Communication, and Interconnect Length in Multicomputers1988-01-01Paper
Counting is easy1988-01-01Paper
https://portal.mardi4nfdi.de/entity/Q38155111988-01-01Paper
https://portal.mardi4nfdi.de/entity/Q38231291988-01-01Paper
https://portal.mardi4nfdi.de/entity/Q37036911986-01-01Paper
https://portal.mardi4nfdi.de/entity/Q37273881986-01-01Paper
https://portal.mardi4nfdi.de/entity/Q37510111986-01-01Paper
https://portal.mardi4nfdi.de/entity/Q37599231986-01-01Paper
Square time is optimal for simulation of one pushdown store or one queue by an oblivious one-head tape unit1985-01-01Paper
An \(n^{1.618}\) lower bound on the time to simulate one queue or two pushdown stores by one tape1985-01-01Paper
An Optimal Simulation of Counter Machines1985-01-01Paper
An Optimal Simulation of Counter Machines: The ACM Case1985-01-01Paper
On the power of real-time two-way multihead finite automata with jumps1984-01-01Paper
On two-tape real-time computation and queues1984-01-01Paper
https://portal.mardi4nfdi.de/entity/Q37144631984-01-01Paper
https://portal.mardi4nfdi.de/entity/Q37329611984-01-01Paper
https://portal.mardi4nfdi.de/entity/Q36705641983-01-01Paper
On efficient simulations of multicounter machines1982-01-01Paper
https://portal.mardi4nfdi.de/entity/Q39337431982-01-01Paper
https://portal.mardi4nfdi.de/entity/Q39337441982-01-01Paper
https://portal.mardi4nfdi.de/entity/Q39423991982-01-01Paper
How well can a graph be n-colored?1981-01-01Paper
A note on dpda transductions of {0,1}and inverse dpda transductions of the dyck set1981-01-01Paper
https://portal.mardi4nfdi.de/entity/Q39040511981-01-01Paper
Achievable high scores of \(\varepsilon\)-moves and running times in DPDA computations1980-01-01Paper
https://portal.mardi4nfdi.de/entity/Q38561011980-01-01Paper
https://portal.mardi4nfdi.de/entity/Q38561021980-01-01Paper
https://portal.mardi4nfdi.de/entity/Q38703141980-01-01Paper
https://portal.mardi4nfdi.de/entity/Q38703151980-01-01Paper
https://portal.mardi4nfdi.de/entity/Q38802941980-01-01Paper
https://portal.mardi4nfdi.de/entity/Q38868651980-01-01Paper
https://portal.mardi4nfdi.de/entity/Q38901131980-01-01Paper
https://portal.mardi4nfdi.de/entity/Q38933041980-01-01Paper
https://portal.mardi4nfdi.de/entity/Q30513751979-01-01Paper
https://portal.mardi4nfdi.de/entity/Q32063171979-01-01Paper
A note on the recursive enumerability of some classes of recursively enumerable languages1978-01-01Paper
On inverse deterministic pushdown transductions1978-01-01Paper
Stable string languages of lindenmayer systems1978-01-01Paper
https://portal.mardi4nfdi.de/entity/Q41243361977-01-01Paper
Context sensitive table linden mayer languages and a relation to the LBA problem1977-01-01Paper
On a problem in the collective behavior of automata1976-01-01Paper
Deterministic Lindenmayer languages, nonterminals and homomorphisms1976-01-01Paper
Growth Functions Associated with Biological Development1976-01-01Paper
https://portal.mardi4nfdi.de/entity/Q40456701974-01-01Paper
https://portal.mardi4nfdi.de/entity/Q40546781974-01-01Paper
https://portal.mardi4nfdi.de/entity/Q47686421973-01-01Paper
Sexually reproducing cellular automata1973-01-01Paper
https://portal.mardi4nfdi.de/entity/Q56661781972-01-01Paper

Research outcomes over time


Doctoral students

No records found.


Known relations from the MaRDI Knowledge Graph

PropertyValue
MaRDI profile typeMaRDI person profile
instance ofhuman


This page was built for person: Paul M. B. Vitányi