Ming Li

Orcid: 0000-0002-2157-2775

Affiliations:
  • University of Waterloo, ON, Canada
  • Cornell University, Ithaca, NY, USA (former)
  • York University, Toronto, Canada (former)
  • Harvard University, Cambridge, MA, USA (former)


According to our database1, Ming Li authored at least 248 papers between 1985 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Understanding is Compression.
CoRR, 2024

2023
Mitigating the missing-fragmentation problem in de novo peptide sequencing with a two-stage graph-based deep learning model.
Nat. Mac. Intell., October, 2023

Approximating Human-Like Few-shot Learning with GPT-based Compression.
CoRR, 2023

2022
A tale of solving two computational challenges in protein science: neoantigen prediction and protein structure prediction.
Briefings Bioinform., 2022

Few-Shot Non-Parametric Learning with Deep Latent Variable Model.
Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

2021
ChimST: An Efficient Spectral Library Search Tool for Peptide Identification from Chimeric Spectra in Data-Dependent Acquisition.
IEEE ACM Trans. Comput. Biol. Bioinform., 2021

Computationally instrument-resolution-independent de novo peptide sequencing for high-resolution devices.
Nat. Mach. Intell., 2021

Multi-Task Dense Retrieval via Model Uncertainty Fusion for Open-Domain Question Answering.
Proceedings of the Findings of the Association for Computational Linguistics: EMNLP 2021, 2021

Unsupervised Chunking as Syntactic Structure Induction with a Knowledge-Transfer Approach.
Proceedings of the Findings of the Association for Computational Linguistics: EMNLP 2021, 2021

Don't Change Me! User-Controllable Selective Paraphrase Generation.
Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume, 2021

Semantics of the Unwritten: The Effect of End of Paragraph and Sequence Tokens on Text Generation with GPT2.
Proceedings of the ACL-IJCNLP 2021 Student Research Workshop, 2021

Segatron: Segment-Aware Transformer for Language Modeling and Understanding.
Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, 2021

2020
Personalized deep learning of individual immunopeptidomes to identify neoantigens for cancer vaccines.
Nat. Mach. Intell., 2020

Latte-Mix: Measuring Sentence Semantic Similarity with Latent Categorical Mixtures.
CoRR, 2020

To Paraphrase or Not To Paraphrase: User-Controllable Selective Paraphrase Generation.
CoRR, 2020

SegaBERT: Pre-training of Segment-aware BERT for Language Understanding.
CoRR, 2020

Semantics of the Unwritten.
CoRR, 2020

Distant Supervision for Multi-Stage Fine-Tuning in Retrieval-Based Question Answering.
Proceedings of the WWW '20: The Web Conference 2020, Taipei, Taiwan, April 20-24, 2020, 2020

Approximate Nearest Neighbor Search and Lightweight Dense Vector Reranking in Multi-Stage Retrieval Architectures.
Proceedings of the ICTIR '20: The 2020 ACM SIGIR International Conference on the Theory of Information Retrieval, 2020

Two Birds, One Stone: A Simple, Unified Model for Text Generation from Structured and Unstructured Data.
Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, 2020

2019
An Introduction to Kolmogorov Complexity and Its Applications, 4th Edition
Texts in Computer Science, Springer, ISBN: 978-3-030-11297-4, 2019

Deep Learning Deciphers Protein<i>-</i>RNA Interaction.
Genom. Proteom. Bioinform., 2019

DeepNovoV2: Better de novo peptide sequencing with deep learning.
CoRR, 2019

Data Augmentation for BERT Fine-Tuning in Open-Domain Question Answering.
CoRR, 2019

End-to-End Open-Domain Question Answering with BERTserini.
Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, 2019

Detecting Customer Complaint Escalation with Recurrent Neural Networks and Manually-Engineered Features.
Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, 2019

2018
Challenges from Cancer Immunotherapy.
Proceedings of the Computing and Combinatorics - 24th International Conference, 2018

2017
Enhanced question understanding with dynamic memory networks for textual question answering.
Expert Syst. Appl., 2017

2016
Closest String and Substring Problems.
Encyclopedia of Algorithms, 2016

Nearest Neighbor Interchange and Related Distances.
Encyclopedia of Algorithms, 2016

Neural Contextual Conversation Learning with Labeled Question-Answering Pairs.
CoRR, 2016

UWNLP at the NTCIR-12 Short Text Conversation Task.
Proceedings of the 12th NTCIR Conference on Evaluation of Information Access Technologies, 2016

2015
John Wooley and JBCB.
J. Bioinform. Comput. Biol., 2015

Question Classification by Approximating Semantics.
Proceedings of the 24th International Conference on World Wide Web Companion, 2015

2014
Estimating feature ratings through an effective review selection approach.
Knowl. Inf. Syst., 2014

Merge-Weighted Dynamic Time Warping for Speech Recognition.
J. Comput. Sci. Technol., 2014

JBCB, the first decade.
J. Bioinform. Comput. Biol., 2014

Fingerprinting protein structures effectively and efficiently.
Bioinform., 2014

Formal Models and Computability.
Proceedings of the Computing Handbook, 2014

2013
LoopWeaver: Loop Modeling by the Weighted Scaling of Verified Proteins.
J. Comput. Biol., 2013

Determining Protein Structures from NOESY Distance Constraints by Semidefinite Programming.
J. Comput. Biol., 2013

Information distance between what I said and what it heard.
Commun. ACM, 2013

Protein Structure Idealization: How accurately is it possible to model protein structures with dihedral angles?
Algorithms Mol. Biol., 2013

Towards Reliable Automatic Protein Structure Alignment.
Proceedings of the Algorithms in Bioinformatics - 13th International Workshop, 2013

2012
Clustering 100, 000 Protein Structure Decoys in Minutes.
IEEE ACM Trans. Comput. Biol. Bioinform., 2012

Residues with Similar Hexagon Neighborhoods Share Similar Side-Chain Conformations.
IEEE ACM Trans. Comput. Biol. Bioinform., 2012

Combining automated peak tracking in SAR by NMR with structure-based backbone assignment from <sup>15</sup>N-NOESY.
BMC Bioinform., 2012

How Accurately Can We Model Protein Structures with Dihedral Angles?
Proceedings of the Algorithms in Bioinformatics - 12th International Workshop, 2012

Protein Structure by Semidefinite Facial Reduction.
Proceedings of the Research in Computational Molecular Biology, 2012

Classifying Stem Cell Differentiation Images by Information Distance.
Proceedings of the Machine Learning and Knowledge Discovery in Databases, 2012

(2) Protein structure determination on demand.
Proceedings of the 2012 IEEE International Conference on Bioinformatics and Biomedicine, 2012

2011
A New Multiword Expression Metric and Its Applications.
J. Comput. Sci. Technol., 2011

Finding Nearly Optimal GDT Scores.
J. Comput. Biol., 2011

Towards Fully Automated Structure-Based NMR Resonance Assignment of <sup>15</sup>N-Labeled Proteins From Automatically Picked Peaks.
J. Comput. Biol., 2011

Error Tolerant NMR Backbone Resonance Assignment and Automated Structure Generation.
J. Bioinform. Comput. Biol., 2011

Partial Match Distance - In Memoriam Ray Solomonoff 1926-2009.
Proceedings of the Algorithmic Probability and Friends. Bayesian Prediction and Artificial Intelligence, 2011

Combining ambiguous chemical shift mapping with structure-based backbone and NOE assignment from <sup>15</sup>N-NOESY.
Proceedings of the ACM International Conference on Bioinformatics, 2011

Information Distance and Its Extensions.
Proceedings of the Algorithmic Learning Theory - 22nd International Conference, 2011

2010
A New Approach for Multi-Document Update Summarization.
J. Comput. Sci. Technol., 2010

Protein Secondary Structure Prediction Using NMR Chemical Shift Data.
J. Bioinform. Comput. Biol., 2010

Towards Automated Structure-Based NMR Resonance Assignment.
Proceedings of the Research in Computational Molecular Biology, 2010

Measuring the Non-compositionality of Multiword Expressions.
Proceedings of the COLING 2010, 2010

2009
On two open problems of 2-interval patterns.
Theor. Comput. Sci., 2009

Finding compact structural motifs.
Theor. Comput. Sci., 2009

Preface.
J. Comput. Sci. Technol., 2009

Can We Determine a Protein Structure Quickly?
J. Comput. Sci. Technol., 2009

Predicting Local Quality of a Sequence-Structure Alignment.
J. Bioinform. Comput. Biol., 2009

PICKY: a novel SVD-based NMR spectra peak picking method.
Bioinform., 2009

Specialized Review Selection for Feature Rating Estimation.
Proceedings of the 2009 IEEE/WIC/ACM International Conference on Web Intelligence, 2009

Multi-document Summarization by Information Distance.
Proceedings of the ICDM 2009, 2009

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

Nearest Neighbor Interchange and Related Distances.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

New Information Distance Measure and Its Application in Question Answering System.
J. Comput. Sci. Technol., 2008

Mango: Multiple Alignment with n Gapped Oligos.
J. Bioinform. Comput. Biol., 2008

Normalized Information Distance
CoRR, 2008

ZOOM! Zillions of oligos mapped.
Bioinform., 2008

Rapid and Accurate Protein Side Chain Prediction with Local Backbone Information.
Proceedings of the Research in Computational Molecular Biology, 2008

Designing succinct structural alphabets.
Proceedings of the Proceedings 16th International Conference on Intelligent Systems for Molecular Biology (ISMB), 2008

Finding Largest Well-Predicted Subset of Protein Structure Models.
Proceedings of the Combinatorial Pattern Matching, 19th Annual Symposium, 2008

Information shared by many objects.
Proceedings of the 17th ACM Conference on Information and Knowledge Management, 2008

2007
Applications of algorithmic information theory.
Scholarpedia, 2007

Near optimal multiple alignment within a band in polynomial time.
J. Comput. Syst. Sci., 2007

On the complexity of the spaced seeds.
J. Comput. Syst. Sci., 2007

Average-case analysis of QuickSort and Binary Insertion Tree height using incompressibility.
Inf. Process. Lett., 2007

Information Distance and its Applications.
Int. J. Found. Comput. Sci., 2007

Computing exact <i>P</i>-values for DNA motifs.
Bioinform., 2007

Information distance from a question to an answer.
Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2007

Homology search for genes.
Proceedings of the Proceedings 15th International Conference on Intelligent Systems for Molecular Biology (ISMB) & 6th European Conference on Computational Biology (ECCB), 2007

Invited Talk: Modern Homology Search.
Proceedings of the Bioinformatics Research and Applications, Third International Symposium, 2007

Computing Exact p-Value for Structured Motif.
Proceedings of the Combinatorial Pattern Matching, 18th Annual Symposium, 2007

Information Distance from a Question to an Answer.
Proceedings of the Computing and Combinatorics, 13th Annual International Conference, 2007

2006
Optimizing Multiple Spaced Seeds for Homology Search.
J. Comput. Biol., 2006

Prima: Peptide Robust Identification from Ms/ms Spectra.
J. Bioinform. Comput. Biol., 2006

A hybrid method for relation extraction from biomedical literature.
Int. J. Medical Informatics, 2006

On the Complexity of the Crossing Contact Map Pattern Matching Problem.
Proceedings of the Algorithms in Bioinformatics, 6th International Workshop, 2006

Superiority and complexity of the spaced seeds.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

From Three Ideas in TCS to Three Applications in Bioinformatics.
Proceedings of the Mathematical Foundations of Computer Science 2006, 2006

Information distance.
Proceedings of the 2006 IEEE International Conference on Granular Computing, 2006

ONBRIRES: Ontology-Based Biological Relation Extraction System.
Proceedings of 4th Asia-Pacific Bioinformatics Conference. 13-16 February 2006, 2006

2005
Finding Cancer Biomarkers from Mass Spectrometry Data by Decision Lists.
J. Comput. Biol., 2005

tPatternHunter: gapped, fast and sensitive translated homology search .
Bioinform., 2005

Discovering patterns to extract protein-protein interactions from the literature: Part II.
Bioinform., 2005

Discovering Sequence-Structure Motifs from Protein Segments and Two Applications.
Proceedings of the Biocomputing 2005, 2005

ExonHunter: a comprehensive approach to gene finding.
Proceedings of the Proceedings Thirteenth International Conference on Intelligent Systems for Molecular Biology 2005, 2005

A New Algorithm for Pattern Optimization in Protein-Protein Interaction Extraction System.
Proceedings of the Pattern Recognition and Image Analysis, Second Iberian Conference, 2005

Consensus fold recognition by predicted model quality.
Proceedings of 3rd Asia-Pacific Bioinformatics Conference, 17-21 January 2005, Singapore, 2005

PRIME: Peptide robust identification from MS/MS spectra.
Proceedings of 3rd Asia-Pacific Bioinformatics Conference, 17-21 January 2005, Singapore, 2005

2004
The similarity metric.
IEEE Trans. Inf. Theory, 2004

Shared information and program plagiarism detection.
IEEE Trans. Inf. Theory, 2004

A Note on the Single Genotype Resolution Problem.
J. Comput. Sci. Technol., 2004

Protein Threading by Linear Programming: Theoretical Analysis and Computational Results.
J. Comb. Optim., 2004

Patternhunter Ii: Highly Sensitive and Fast Homology Search.
J. Bioinform. Comput. Biol., 2004

A Tutorial of Recent Developments in the Seeding of Local Alignment.
J. Bioinform. Comput. Biol., 2004

Selecting the branches for an evolutionary tree.: A polynomial time approximation scheme.
J. Algorithms, 2004

On spaced seeds for similarity search.
Discret. Appl. Math., 2004

Discovering patterns to extract protein-protein interactions from full texts.
Bioinform., 2004

Discovering Patterns to Extract Protein-Protein Interactions from Full Biomedical Texts.
Proceedings of the International Joint Workshop on Natural Language Processing in Biomedicine and its Applications, 2004

PathwayFinder: Paving the Way Towards Automatic Pathway Extraction.
Proceedings of the Second Asia-Pacific Bioinformatics Conference (APBC 2004), 2004

2003
Raptor: Optimal Protein Threading by Linear Programming.
J. Bioinform. Comput. Biol., 2003

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

Distinguishing string selection problems.
Inf. Comput., 2003

MOLVIE: an interactive visualization environment for molecular structures.
Comput. Methods Programs Biomed., 2003

Protein Threading by Linear Programming.
Proceedings of the 8th Pacific Symposium on Biocomputing, 2003

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

Finding Similar Regions in Many Sequences.
J. Comput. Syst. Sci., 2002

On the closest string and substring problems.
J. ACM, 2002

PatternHunter: faster and more sensitive homology search.
Bioinform., 2002

DNACompress: fast and effective DNA sequence compression.
Bioinform., 2002

2001
Selected papers from ALT 1997 - Foreword.
Theor. Comput. Sci., 2001

An information-based sequence distance and its application to whole mitochondrial genome phylogeny.
Bioinform., 2001

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

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

From Gene Trees to Species Trees.
SIAM J. Comput., 2000

A Polynomial Time Approximation Scheme for Inferring Evolutionary Trees from Quartet Topologies and Its Application.
SIAM J. Comput., 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

Fixed topology alignment with recombination.
Discret. Appl. Math., 2000

Applying MDL to Learning Best Model Granularity
CoRR, 2000

Applying MDL to learn best model granularity.
Artif. Intell., 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

Estimating DNA sequence entropy.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Computing the quartet distance between evolutionary trees.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

A practical algorithm for recovering the best supported edges of an evolutionary tree (extended abstract).
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

A compression algorithm for DNA sequences and its applications in genome comparison.
Proceedings of the Fourth Annual International Conference on Computational Molecular Biology, 2000

1999
Some open problems in computational molecular biology.
SIGACT News, 1999

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

Twist-Rotation Transformations of Binary Trees and Arithmetic Expressions.
J. Algorithms, 1999

Approximation Algorithms for Directed Steiner Problems.
J. Algorithms, 1999

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

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

On the Linear-Cost Subtree-Transfer Distance between Phylogenetic Trees.
Algorithmica, 1999

Finding Similar Regions in Many Strings.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Recovering Branches on the Tree of Life: An Approximation Algorithm.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

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

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

Quartet Cleaning: Improved Algorithms and Simulations.
Proceedings of the Algorithms, 1999

On computing the nearest neighbor interchange distance.
Proceedings of the Discrete Mathematical Problems with Medical Applications, 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

Formal Grammars and Languages.
Proceedings of the Algorithms and Theory of Computation Handbook., 1999

Computability.
Proceedings of the Algorithms and Theory of Computation Handbook., 1999

Basic Notions in Computational Complexity.
Proceedings of the Algorithms and Theory of Computation Handbook., 1999

1998
Information Distance.
IEEE Trans. Inf. Theory, 1998

Addition in log<sub>2</sub>n + O(1) Steps on Average: A Simple Analysis.
Theor. Comput. Sci., 1998

On the Complexity and Approximation of Syntenic Distance.
Discret. Appl. Math., 1998

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

On reconstructing species trees from gene trees in term of duplications and losses.
Proceedings of the Second Annual International Conference on Research in Computational Molecular Biology, 1998

Orchestrating Quartets: Approximation and Data Correction.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

Better Approximation of Diagonal-Flip Transformation and Rotation Transformation.
Proceedings of the Computing and Combinatorics, 4th Annual International Conference, 1998

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

1997
Inferring a DNA Sequence from Erroneous Copies.
Theor. Comput. Sci., 1997

Foreword (COCOON'95).
Theor. Comput. Sci., 1997

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

Reversible Simulation of Irreversible Computation by Pebble Games
CoRR, 1997

On Distances between Phylogenetic Trees (Extended Abstract).
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

Kolmogorov random graphs.
Proceedings of the Compression and Complexity of SEQUENCES 1997, 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

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

Shortest common superstrings.
Proceedings of the Pattern Matching Algorithms, 1997

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

Formal Models and Computability.
Proceedings of the Computer Science and Engineering Handbook, 1997

1996
Iterative Belief Revision in Extended Logic Programming.
Theor. Comput. Sci., 1996

DNA Sequencing and String Learning.
Math. Syst. Theory, 1996

K One-Way Heads Cannot Do String-Matching.
J. Comput. Syst. Sci., 1996

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

Lower Bounds on Learning Decision Lists and Trees.
Inf. Comput., 1996

Some Notes on the Nearest Neighbour Interchange Distance.
Proceedings of the Computing and Combinatorics, Second Annual International Conference, 1996

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

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

On the Approximation of Shortest Common Supersequences and Longest Common Subsequences.
SIAM J. Comput., 1995

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

Lower Bounds on Learning Decision Lists and Trees (Extended Abstract).
Proceedings of the STACS 95, 1995

Inferring a DNA Sequence from Erroneous Copies (Abstract).
Proceedings of the Algorithmic Learning Theory, 6th International Conference, 1995

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

1994
Approximating Shortest Superstrings with Constraints.
Theor. Comput. Sci., 1994

Wait-Free Consensus Using Asynchronous Hardware.
SIAM J. Comput., 1994

Statistical Properties of Finite Sequences with High Kolmogorov Complexity.
Math. Syst. Theory, 1994

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

Three One-Way Heads Cannot Do String Matching.
J. Comput. Syst. Sci., 1994

Learning Boolean Formulas.
J. ACM, 1994

Linear Approximation of Shortest Superstrings.
J. ACM, 1994

1993
On the Complexity of Learning Strings and Sequences.
Theor. Comput. Sci., 1993

Learning in the Presence of Malicious Errors.
SIAM J. Comput., 1993

Bonded Time-Stamps.
Distributed Comput., 1993

Approximating Shortest Superstrings with Constraints (Extended Abstract).
Proceedings of the Algorithms and Data Structures, Third Workshop, 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

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

A Note on Shortest Superstrings with Flipping.
Inf. Process. Lett., 1992

Theory and Algorithms for Plan Merging.
Artif. Intell., 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

Resource Bounds for Parallel Computation of Threshold and Symmetric Functions.
J. Comput. Syst. Sci., 1991

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

A Quantitative Theory for Plan Merging.
Proceedings of the 9th National Conference on Artificial Intelligence, 1991

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

1990
Towards a DNA Sequencing Theory (Learning a String) (Preliminary Version)
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Kolmogorov Complexity and its Applications.
Proceedings of the Handbook of Theoretical Computer Science, 1990

1989
On the Power of Concurrent-Write PRAMs With Read-Only Memory
Inf. Comput., November, 1989

New lower bounds for parallel computation.
J. ACM, 1989

Geometric Optimization and D<sup>p</sup> - Completeness.
Discret. Comput. Geom., 1989

The Minimum Description Length Principle and Its Application to Online Learning of Handprinted Characters.
Proceedings of the 11th International Joint Conference on Artificial Intelligence. Detroit, 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

Simulating Two Pushdown Stores by One Tape in O(n^1.5 sqrt(log n)) Time.
J. Comput. Syst. Sci., 1988

k+1 Heads Are Better than k for PDAs.
J. Comput. Syst. Sci., 1988

A Separator Theorem for One-Dimensional Graphs Under Linear Mapping.
Inf. Process. Lett., 1988

Learning in the Presence of Malicious Errors (Extended Abstract)
Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988

On the Learnability of Finite Automata.
Proceedings of the First Annual Workshop on Computational Learning Theory, 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

1987
Separation and Lower Bounds for ROM and Nondeterministic Models of Parallel Computation
Inf. Comput., May, 1987

On the Learnability of Boolean Formulae
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

On Processor Coordination Using Asynchronous Hardware.
Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, 1987

The Probabilistic and Deterministic Parallel Complexity of Symmetric Functions.
Proceedings of the Automata, Languages and Programming, 14th International Colloquium, 1987

Bounded Time-Stamps (Extended Abstract)
Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987

1986
String-Matching Cannot be Done by a Two-Head One-Way Deterministic Finite Automation.
Inf. Process. Lett., 1986

Containment, Separation, Complete Sets, and Immunity of Complexity Classes.
Proceedings of the Automata, Languages and Programming, 13th International Colloquium, 1986

k+1 Heads Are Better than k for PDA's
Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

1985
Lower Bounds in Computational Complexity.
PhD thesis, 1985

Lower Bounds by Kolmogorov-Complexity (Extended Abstract).
Proceedings of the Automata, 1985


  Loading...