| Publication | Date of Publication | Type |
|---|
Some notes on the nearest neighbour interchange distance
Lecture Notes in Computer Science | 2024-01-29 | Paper |
Approximating shortest superstrings with constraints
Lecture Notes in Computer Science | 2023-01-18 | Paper |
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 |
Philosophical issues in Kolmogorov complexity
Automata, Languages and Programming | 2019-12-04 | Paper |
On the approximation of shortest common supersequences and longest common subsequences
Automata, Languages and Programming | 2019-04-29 | Paper |
An introduction to Kolmogorov complexity and its applications
Texts in Computer Science | 2019-02-15 | Paper |
Lower bounds on learning decision lists and trees
STACS 95 | 2017-12-04 | Paper |
Finding similar regions in many strings
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
On the closest string and substring problems
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 |
| scientific article; zbMATH DE number 6472618 (Why is no real title available?) | 2015-08-14 | 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 |
<i>k</i> one-way heads cannot do string-matching
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 | 2015-05-07 | Paper |
Near optimal multiple alignment within a band in polynomial time
Proceedings of the thirty-second annual ACM symposium on Theory of computing | 2014-09-26 | Paper |
Wavelet frame based algorithm for 3D reconstruction in electron microscopy
SIAM Journal on Scientific Computing | 2014-05-26 | Paper |
| scientific article; zbMATH DE number 6019543 (Why is no real title available?) | 2012-03-29 | Paper |
Superiority and complexity of the spaced seeds
Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 | 2010-08-16 | Paper |
Average-case analysis of quicksort and binary insertion tree height using incompressibility
Information Processing Letters | 2010-03-24 | Paper |
Finding compact structural motifs
Theoretical Computer Science | 2009-08-07 | Paper |
On two open problems of 2-interval patterns
Theoretical Computer Science | 2009-06-04 | Paper |
Sharpening Occam's razor
Information Processing Letters | 2009-03-23 | Paper |
Normalized Information Distance
Information Theory and Statistical Learning | 2009-03-12 | Paper |
The Similarity Metric
IEEE Transactions on Information Theory | 2008-12-21 | Paper |
Shared Information and Program Plagiarism Detection
IEEE Transactions on Information Theory | 2008-12-21 | Paper |
Finding Largest Well-Predicted Subset of Protein Structure Models
Combinatorial Pattern Matching | 2008-06-17 | Paper |
Finding Compact Structural Motifs
Combinatorial Pattern Matching | 2008-06-17 | Paper |
Computing Exact p-Value for Structured Motif
Combinatorial Pattern Matching | 2008-06-17 | Paper |
An introduction to Kolmogorov complexity and its applications
Texts in Computer Science | 2008-06-04 | Paper |
INFORMATION DISTANCE AND ITS APPLICATIONS
International Journal of Foundations of Computer Science | 2008-05-20 | Paper |
| On computing the nearest neighbor interchange distance | 2008-04-14 | Paper |
| Protein threading by linear programming | 2008-04-14 | Paper |
Information Distance and Its Applications
Implementation and Application of Automata | 2007-09-06 | Paper |
On the complexity of the spaced seeds
Journal of Computer and System Sciences | 2007-08-27 | Paper |
Near optimal multiple alignment within a band in polynomial time
Journal of Computer and System Sciences | 2007-08-23 | Paper |
DNA sequencing and string learning
Mathematical Systems Theory | 2007-06-11 | Paper |
Combinatorial Pattern Matching
Lecture Notes in Computer Science | 2005-09-07 | Paper |
Combinatorial Pattern Matching
Lecture Notes in Computer Science | 2005-09-07 | Paper |
Protein threading by linear programming: theoretical analysis and computational results
Journal of Combinatorial Optimization | 2005-05-13 | Paper |
Selecting the branches for an evolutionary tree.
Journal of Algorithms | 2004-10-01 | Paper |
| scientific article; zbMATH DE number 2089996 (Why is no real title available?) | 2004-08-12 | Paper |
On spaced seeds for similarity search
Discrete Applied Mathematics | 2004-08-06 | 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 |
Distinguishing string selection problems.
Information and Computation | 2004-03-14 | Paper |
Finding similar regions in many sequences
Journal of Computer and System Sciences | 2003-05-04 | Paper |
The average‐case area of Heilbronn‐type triangles*
Random Structures & Algorithms | 2002-08-08 | Paper |
| scientific article; zbMATH DE number 1408350 (Why is no real title available?) | 2002-01-24 | Paper |
A polynomial time approximation scheme for inferring evolutionary trees from quartet topologies and its application
SIAM Journal on Computing | 2001-06-21 | Paper |
On the linear-cost subtree-transfer distance between phylogenetic trees
Algorithmica | 2001-01-14 | Paper |
| scientific article; zbMATH DE number 1541304 (Why is no real title available?) | 2000-12-07 | Paper |
Fixed topology alignment with recombination
Discrete Applied Mathematics | 2000-11-06 | Paper |
Applying MDL to learn best model granularity
Artificial Intelligence | 2000-10-26 | Paper |
From Gene Trees to Species Trees
SIAM Journal on Computing | 2000-10-18 | Paper |
| scientific article; zbMATH DE number 1405796 (Why is no real title available?) | 2000-09-10 | Paper |
Minimum description length induction, Bayesianism, and Kolmogorov complexity
IEEE Transactions on Information Theory | 2000-09-07 | Paper |
New applications of the incompressibility method. II
Theoretical Computer Science | 2000-06-04 | Paper |
Approximation Algorithms for Directed Steiner Problems
Journal of Algorithms | 2000-05-28 | Paper |
| scientific article; zbMATH DE number 1445329 (Why is no real title available?) | 2000-05-10 | Paper |
| scientific article; zbMATH DE number 1445316 (Why is no real title available?) | 2000-05-10 | Paper |
| scientific article; zbMATH DE number 1405647 (Why is no real title available?) | 2000-04-25 | Paper |
| scientific article; zbMATH DE number 1302179 (Why is no real title available?) | 2000-04-17 | 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 |
Twist–Rotation Transformations of Binary Trees and Arithmetic Expressions
Journal of Algorithms | 1999-11-23 | Paper |
Information distance
IEEE Transactions on Information Theory | 1999-11-21 | Paper |
| scientific article; zbMATH DE number 1305446 (Why is no real title available?) | 1999-11-01 | Paper |
| scientific article; zbMATH DE number 1305456 (Why is no real title available?) | 1999-09-15 | Paper |
On the complexity and approximation of syntenic distance
Discrete Applied Mathematics | 1999-06-20 | Paper |
| scientific article; zbMATH DE number 1303557 (Why is no real title available?) | 1999-06-17 | Paper |
| scientific article; zbMATH DE number 1222822 (Why is no real title available?) | 1999-02-14 | Paper |
Addition in \(\log_{2} n+O(1)\) steps on average. A simple analysis
Theoretical Computer Science | 1998-08-13 | Paper |
Inferring a DNA sequence from erroneous copies
Theoretical Computer Science | 1998-07-22 | Paper |
| scientific article; zbMATH DE number 1142293 (Why is no real title available?) | 1998-05-04 | 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 |
\(k\) one-way heads cannot do string-matching
Journal of Computer and System Sciences | 1997-11-18 | 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 |
Iterative belief revision in extended logic programming
Theoretical Computer Science | 1997-02-27 | Paper |
On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
SIAM Journal on Computing | 1997-01-02 | Paper |
Lower bounds on learning decision lists and trees
Information and Computation | 1996-07-03 | Paper |
Approximating shortest superstrings with constraints
Theoretical Computer Science | 1996-04-01 | Paper |
| scientific article; zbMATH DE number 776086 (Why is no real title available?) | 1995-09-27 | 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 |
Learning Boolean formulas
Journal of the ACM | 1995-04-10 | 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 |
Three one-way heads cannot do string matching
Journal of Computer and System Sciences | 1994-12-11 | Paper |
Linear approximation of shortest superstrings
Journal of the ACM | 1994-11-03 | Paper |
Statistical properties of finite sequences with high Kolmogorov complexity
Mathematical Systems Theory | 1994-08-10 | Paper |
On the complexity of learning strings and sequences
Theoretical Computer Science | 1993-11-28 | Paper |
Learning in the Presence of Malicious Errors
SIAM Journal on Computing | 1993-10-10 | Paper |
Bounded time-stamps
Distributed Computing | 1993-09-16 | Paper |
| scientific article; zbMATH DE number 176218 (Why is no real title available?) | 1993-05-18 | Paper |
A note on shortest superstrings with flipping
Information Processing Letters | 1993-05-16 | Paper |
| scientific article; zbMATH DE number 107774 (Why is no real title available?) | 1993-01-23 | Paper |
Theory and algorithms for plan merging
Artificial Intelligence | 1993-01-17 | 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 |
Learning Simple Concepts under Simple Distributions
SIAM Journal on Computing | 1992-06-26 | Paper |
New lower bounds for parallel computation
Journal of the ACM | 1992-06-25 | Paper |
Resource bounds for parallel computation of threshold and symmetric functions
Journal of Computer and System Sciences | 1991-01-01 | Paper |
| scientific article; zbMATH DE number 4117885 (Why is no real title available?) | 1989-01-01 | Paper |
| scientific article; zbMATH DE number 4166891 (Why is no real title available?) | 1989-01-01 | Paper |
On the power of concurrent-write PRAMs with read-only memory
Information and Computation | 1989-01-01 | Paper |
Geometric optimization and \(D^ P\)-completeness
Discrete & Computational Geometry | 1989-01-01 | Paper |
| scientific article; zbMATH DE number 4086981 (Why is no real title available?) | 1988-01-01 | Paper |
Tape versus queue and stacks: The lower bounds
Information and Computation | 1988-01-01 | Paper |
k\(+1\) heads are better than k for PDAs
Journal of Computer and System Sciences | 1988-01-01 | Paper |
Simulating two pushdown stores by one tape in \(O(n^{1.5}\,\sqrt{\log \,n})\) time
Journal of Computer and System Sciences | 1988-01-01 | Paper |
A separator theorem for one-dimensional graphs under linear mapping
Information Processing Letters | 1988-01-01 | Paper |
| scientific article; zbMATH DE number 4047091 (Why is no real title available?) | 1987-01-01 | Paper |
Separation and lower bounds for ROM and nondeterministic models of parallel computation
Information and Computation | 1987-01-01 | Paper |
| scientific article; zbMATH DE number 4068281 (Why is no real title available?) | 1986-01-01 | Paper |
| scientific article; zbMATH DE number 3988713 (Why is no real title available?) | 1986-01-01 | Paper |
String-matching cannot be done by a two-head one-way deterministic finite automaton
Information Processing Letters | 1986-01-01 | Paper |
| scientific article; zbMATH DE number 3913680 (Why is no real title available?) | 1985-01-01 | Paper |
Normalized quadtrees with respect to translations
Computer Graphics and Image Processing | 1982-01-01 | Paper |
