Most real-world problems that machine learning algorithms are expected to solve face the situation with (1) unknown data distribution; (2) little domain-specific knowledge; and (3) datasets with limited annotation. We propose Non-Parametric learning by Compression with Latent Variables (NPC-LV), a learning framework for any dataset with abundant unlabeled data but very few labeled ones. By only training a generative model in an unsupervised way, the framework utilizes the data distribution to build a compressor. Using a compressor-based distance metric derived from Kolmogorov complexity, together with few labeled data, NPC-LV classifies without further training. We show that NPC-LV outperforms supervised methods on all three datasets on image classification in the low data regime and even outperforms semi-supervised learning methods on CIFAR-10. We demonstrate how and when negative evidence lowerbound (nELBO) can be used as an approximate compressed length for classification. By revealing the correlation between compression rate and classification accuracy, we illustrate that under NPC-LV how the improvement of generative models can enhance downstream classification accuracy.

In this article, we review two challenging computational questions in protein science: neoantigen prediction and protein structure prediction. Both topics have seen significant leaps forward by deep learning within the past five years, which immediately unlocked new developments of drugs and immunotherapies. We show that deep learning models offer unique advantages, such as representation learning and multi-layer architecture, which make them an ideal choice to leverage a huge amount of protein sequence and structure data to address those two problems. We also discuss the impact and future possibilities enabled by those two applications, especially how the data-driven approach by deep learning shall accelerate the progress towards personalized biomedicine.

Transformers are powerful for sequence modeling. Nearly all state-of-the-art language models and pre-trained language models are based on the Transformer architecture. However, it distinguishes sequential tokens only with the token position index. We hypothesize that better contextual representations can be generated from the Transformer with richer positional information. To verify this, we propose a segment-aware Transformer (Segatron), by replacing the original token position encoding with a combined position encoding of paragraph, sentence, and token. We first introduce the segment-aware mechanism to Transformer-XL, which is a popular Transformer-based language model with memory extension and relative position encoding. We find that our method can further improve the Transformer-XL base model and large model, achieving 17.1 perplexity on the WikiText-103 dataset. We further investigate the pre-training masked language modeling task with Segatron. Experimental results show that BERT pre-trained with Segatron (SegaBERT) can outperform BERT with vanilla Transformer on various NLP tasks, and outperforms RoBERTa on zero-shot sentence representation learning. Our code is available on GitHub.

Mohan Zhang, Luchen Tan, Zihang Fu, Kun Xiong, Jimmy Lin, Ming Li, Zhengkai Tu. Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume. 2021.

Accurate and sensitive identification of peptides from MS/MS spectra is a very challenging problem in computational shotgun proteomics. To tackle this problem, spectral library search has been one of the competitive solutions. However, most existing library search tools were developed on the basis of one peptide per spectrum, which prevents them from working properly on chimeric spectra where two or more peptides are co-fragmented. In this work, we present a new library search tool called ChimST, which is particularly capable of reliably identifying multiple peptides from a chimeric spectrum. It starts with associating each query MS/MS spectrum with MS precursor features. For each precursor feature, there is a list of peptide candidates extracted from an input spectral library. Then, it takes one peptide candidate from each associated feature and scores how well they could collectively interpret the query spectrum. The highest-scoring set of peptide candidates are finally reported as the identification of the query spectrum. Our experimental tests show that ChimST could significantly outperform the three state-of-the-art library search tools, SpectraST, reSpect, and MSPLIT, in terms of the numbers of both peptide-spectrum matches and unique peptides, especially when the acquisition isolation window is broad.

A number of researchers have recently questioned the necessity of increasingly complex neural network (NN) architectures.In particular, several recent papers have shown that simpler, properly tuned models are at least competitive across several NLP tasks.In this work, we show that this is also the case for text generation from structured and unstructured data.We consider neural tableto-text generation and neural question generation (NQG) tasks for text generation from structured and unstructured data, respectively.Table -to-text generation aims to generate a description based on a given table, and NQG is the task of generating a question from a given passage where the generated question can be answered by a certain sub-span of the passage using NN models.Experimental results demonstrate that a basic attentionbased seq2seq model trained with the exponential moving average technique achieves the state of the art in both tasks.Code is available at https://github.com/h-shahidi/ 2birds-gen.

We tackle the problem of question answering directly on a large document collection, combining simple “bag of words” passage retrieval with a BERT-based reader for extracting answer spans. In the context of this architecture, we present a data augmentation technique using distant supervision to automatically annotate paragraphs as either positive or negative examples to supplement existing training data, which are then used together to fine-tune BERT. We explore a number of details that are critical to achieving high accuracy in this setup: the proper sequencing of different datasets during fine-tuning, the balance between “difficult” vs. “easy” examples, and different approaches to gathering negative examples. Experimental results show that, with the appropriate settings, we can achieve large gains in effectiveness on two English and two Chinese QA datasets. We are able to achieve results at or near the state of the art without any modeling advances, which once again affirms the cliché “there’s no data like more data”.

MOTIVATION: One common task in structural biology is to assess the similarities and differences among protein structures. A variety of structure alignment algorithms and programs has been designed and implemented for this purpose. A major drawback with existing structure alignment programs is that they require a large amount of computational time, rendering them infeasible for pairwise alignments on large collections of structures. To overcome this drawback, a fragment alphabet learned from known structures has been introduced. The method, however, considers local similarity only, and therefore occasionally assigns high scores to structures that are similar only in local fragments. METHOD: We propose a novel approach that eliminates false positives, through the comparison of both local and remote similarity, with little compromise in speed. Two kinds of contact libraries (ContactLib) are introduced to fingerprint protein structures effectively and efficiently. Each contact group of the contact library consists of one local or two remote fragments and is represented by a concise vector. These vectors are then indexed and used to calculate a new combined hit-rate score to identify similar protein structures effectively and efficiently. RESULTS: We tested our method on the high-quality protein structure subset of SCOP30 containing 3297 protein structures. For each protein structure of the subset, we retrieved its neighbor protein structures from the rest of the subset. The best area under the Receiver-Operating Characteristic curve, archived by ContactLib, is as high as 0.960. This is a significant improvement compared with 0.747, the best result achieved by FragBag. We also demonstrated that incorporating remote contact information is critical to consistently retrieve accurate neighbor protein structures for all- query protein structures. AVAILABILITY AND IMPLEMENTATION: https://cs.uwaterloo.ca/∼xfcui/contactlib/.

Language-independent embedded speech recognition is a necessary and important application. Considering personal privacy, collection difficulty of all the reference words, and limited storage space of mobile devices, language-independent (LI) embedded speech recognition should be classified into lightweight speaker-dependent (SD) cases. Dynamic time warping (DTW) is the state-of-the-art algorithm for small foot-print SD automatic speech recognition. To decrease the high computational complexity of DTW, and to avoid constraints-induced coarse approximation and inaccuracy problems, we introduce a novel confidence index dynamic time warping (CIDTW) approach. CIDTW defines a new cost function, called the confidence index cost function (CICF), to measure the similarity between merged speech training and testing data, while follows the same DTW process. With extensive experiments on three representative SD datasets, CIDTW achieves better accuracy and overall six times faster speeds compared with DTW.

Protein structure prediction by computers at best may serve as a screening method, and the current high-throughput protein structure determination methods are costly and will never exhaust all proteins. A complementary approach is "protein structure determination on demand", say in a week. We will discuss two approaches that would realize this goal: automatic protein structure determination using NMR data and mass spectrometry data.

BACKGROUND: Chemical shift mapping is an important technique in NMR-based drug screening for identifying the atoms of a target protein that potentially bind to a drug molecule upon the molecule's introduction in increasing concentrations. The goal is to obtain a mapping of peaks with known residue assignment from the reference spectrum of the unbound protein to peaks with unknown assignment in the target spectrum of the bound protein. Although a series of perturbed spectra help to trace a path from reference peaks to target peaks, a one-to-one mapping generally is not possible, especially for large proteins, due to errors, such as noise peaks, missing peaks, missing but then reappearing, overlapped, and new peaks not associated with any peaks in the reference. Due to these difficulties, the mapping is typically done manually or semi-automatically, which is not efficient for high-throughput drug screening. RESULTS: We present PeakWalker, a novel peak walking algorithm for fast-exchange systems that models the errors explicitly and performs many-to-one mapping. On the proteins: hBclXL, UbcH5B, and histone H1, it achieves an average accuracy of over 95% with less than 1.5 residues predicted per target peak. Given these mappings as input, we present PeakAssigner, a novel combined structure-based backbone resonance and NOE assignment algorithm that uses just ¹⁵N-NOESY, while avoiding TOCSY experiments and ¹³C-labeling, to resolve the ambiguities for a one-to-one mapping. On the three proteins, it achieves an average accuracy of 94% or better. CONCLUSIONS: Our mathematical programming approach for modeling chemical shift mapping as a graph problem, while modeling the errors directly, is potentially a time- and cost-effective first step for high-throughput drug screening based on limited NMR data and homologous 3D structures.

We present in this study a new approach to code protein side-chain conformations into hexagon substructures. Classical side-chain packing methods consist of two steps: first, side-chain conformations, known as rotamers, are extracted from known protein structures as candidates for each residue; second, a searching method along with an energy function is used to resolve conflicts among residues and to optimize the combinations of side chain conformations for all residues. These methods benefit from the fact that the number of possible side-chain conformations is limited, and the rotamer candidates are readily extracted; however, these methods also suffer from the inaccuracy of energy functions. Inspired by threading and Ab Initio approaches to protein structure prediction, we propose to use hexagon substructures to implicitly capture subtle issues of energy functions. Our initial results indicate that even without guidance from an energy function, hexagon structures alone can capture side-chain conformations at an accuracy of 83.8 percent, higher than 82.6 percent by the state-of-art side-chain packing methods.

Ab initio protein structure prediction methods first generate large sets of structural conformations as candidates (called decoys), and then select the most representative decoys through clustering techniques. Classical clustering methods are inefficient due to the pairwise distance calculation, and thus become infeasible when the number of decoys is large. In addition, the existing clustering approaches suffer from the arbitrariness in determining a distance threshold for proteins within a cluster: a small distance threshold leads to many small clusters, while a large distance threshold results in the merging of several independent clusters into one cluster. In this paper, we propose an efficient clustering method through fast estimating cluster centroids and efficient pruning rotation spaces. The number of clusters is automatically detected by information distance criteria. A package named ONION, which can be downloaded freely, is implemented accordingly. Experimental results on benchmark data sets suggest that ONION is 14 times faster than existing tools, and ONION obtains better selections for 31 targets, and worse selection for 19 targets compared to SPICKER’s selections. On an average PC, ONION can cluster 100,000 decoys in around 12 minutes.

Fast changing knowledge on the Internet can be acquired more efficiently with the help of automatic document summarization and updating techniques. This paper described a novel approach for multi-document update summarization. The best summary is defined to be the one which has the minimum information distance to the entire document set. The best update summary has the minimum conditional information distance to a document cluster given that a prior document cluster has already been read. Experiments on the DUC 2007 dataset and the TAC 2008 dataset have proved that our method closely correlates with the human summaries and outperforms other programs such as LexRank in many categories under the ROUGE evaluation criterion.

On participatory Websites, users provide opinions about products, with both overall ratings and textual reviews. In this paper, we propose an approach to accurately estimate feature ratings of the products. This approach selects user reviews that extensively discuss specific features of the products (called specialized reviews), using information distance of reviews on the features. Experiments on real data show that overall ratings of the specialized reviews can be used to represent their feature ratings. The average of these overall ratings can be used by recommender systems to provide feature specific recommendations that better help users make purchasing decisions.

MOTIVATION: Picking peaks from experimental NMR spectra is a key unsolved problem for automated NMR protein structure determination. Such a process is a prerequisite for resonance assignment, nuclear overhauser enhancement (NOE) distance restraint assignment, and structure calculation tasks. Manual or semi-automatic peak picking, which is currently the prominent way used in NMR labs, is tedious, time consuming and costly. RESULTS: We introduce new ideas, including noise-level estimation, component forming and sub-division, singular value decomposition (SVD)-based peak picking and peak pruning and refinement. PICKY is developed as an automated peak picking method. Different from the previous research on peak picking, we provide a systematic study of the proposed method. PICKY is tested on 32 real 2D and 3D spectra of eight target proteins, and achieves an average of 88% recall and 74% precision. PICKY is efficient. It takes PICKY on average 15.7 s to process an NMR spectrum. More important than these numbers, PICKY actually works in practice. We feed peak lists generated by PICKY to IPASS for resonance assignment, feed IPASS assignment to SPARTA for fragments generation, and feed SPARTA fragments to FALCON for structure calculation. This results in high-resolution structures of several proteins, for example, TM1112, at 1.25 A. AVAILABILITY: PICKY is available upon request. The peak lists of PICKY can be easily loaded by SPARKY to enable a better interactive strategy for rapid peak picking.

If Kolmogorov complexity [25] measures information in one object and Information Distance measures information shared by two objects, how do we measure information shared by many objects? This paper provides an initial pragmatic study of this fundamental data mining question. Firstly, Em(x1,x2,...,xn) is defined to be the minimum amount of thermodynamic energy needed to convert from any xi to any xj. With this definition several theoretical problems have been solved. Second, our newly proposed theory is applied to select a comprehensive review and a specialized review from many reviews: (1) Core feature words, expanded words and dependent words are extracted respectively. (2) Comprehensive and specialized reviews are selected according to the information among them. This method of selecting a single review can be extended to select multiple reviews as well. Finally, experiments show that this comprehensive and specialized review mining method based on our new theory can do the job efficiently.

MOTIVATION: The 3D structure of a protein sequence can be assembled from the substructures corresponding to small segments of this sequence. For each small sequence segment, there are only a few more likely substructures. We call them the 'structural alphabet' for this segment. Classical approaches such as ROSETTA used sequence profile and secondary structure information, to predict structural fragments. In contrast, we utilize more structural information, such as solvent accessibility and contact capacity, for finding structural fragments. RESULTS: Integer linear programming technique is applied to derive the best combination of these sequence and structural information items. This approach generates significantly more accurate and succinct structural alphabets with more than 50% improvement over the previous accuracies. With these novel structural alphabets, we are able to construct more accurate protein structures than the state-of-art ab initio protein structure prediction programs such as ROSETTA. We are also able to reduce the Kolodny's library size by a factor of 8, at the same accuracy. AVAILABILITY: The online FRazor server is under construction.

MOTIVATION: The next generation sequencing technologies are generating billions of short reads daily. Resequencing and personalized medicine need much faster software to map these deep sequencing reads to a reference genome, to identify SNPs or rare transcripts. RESULTS: We present a framework for how full sensitivity mapping can be done in the most efficient way, via spaced seeds. Using the framework, we have developed software called ZOOM, which is able to map the Illumina/Solexa reads of 15x coverage of a human genome to the reference human genome in one CPU-day, allowing two mismatches, at full sensitivity. AVAILABILITY: ZOOM is freely available to non-commercial users at http://www.bioinfor.com/zoom

We provide three key missing pieces of a general theory of information distance [3, 23, 24]. We take bold steps in formulating a revised theory to avoid some pitfalls in practical applications. The new theory is then used to construct a question answering system. Extensive experiments are conducted to justify the new theory.

MOTIVATION: Many heuristic algorithms have been designed to approximate P-values of DNA motifs described by position weight matrices, for evaluating their statistical significance. They often significantly deviate from the true P-value by orders of magnitude. Exact P-value computation is needed for ranking the motifs. Furthermore, surprisingly, the complexity of the problem is unknown. RESULTS: We show the problem to be NP-hard, and present MotifRank, software based on dynamic programming, to calculate exact P-values of motifs. We define the exact P-value on a general and more precise model. Asymptotically, MotifRank is faster than the best exact P-value computing algorithm, and is in fact practical. Our experiments clearly demonstrate that MotifRank significantly improves the accuracy of existing approximation algorithms. AVAILABILITY: MotifRank is available from http://bio.dlg.cn. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: An enormous number of protein-protein interaction relationships are buried in millions of research articles published over the years, and the number is growing. Rediscovering them automatically is a challenging bioinformatics task. Solutions to this problem also reach far beyond bioinformatics. RESULTS: We study a new approach that involves automatically discovering English expression patterns, optimizing them and using them to extract protein-protein interactions. In a sister paper, we described how to generate English expression patterns related to protein-protein interactions, and this approach alone has already achieved precision and recall rates significantly higher than those of other automatic systems. This paper continues to present our theory, focusing on how to improve the patterns. A minimum description length (MDL)-based pattern-optimization algorithm is designed to reduce and merge patterns. This has significantly increased generalization power, and hence the recall and precision rates, as confirmed by our experiments. AVAILABILITY: http://spies.cs.tsinghua.edu.cn.

UNLABELLED: New ideas, spaced seeds and gapped alignment before 6-frame translation are implemented for translated homology search in tPatternHunter. The new software compares favorably with tBLASTx. AVAILABILITY: The software is free to academics at http://www.bioinformaticssolutions.com/downloads/ph-academic/ CONTACT: [email protected].

MOTIVATION: Although there are several databases storing protein-protein interactions, most such data still exist only in the scientific literature. They are scattered in scientific literature written in natural languages, defying data mining efforts. Much time and labor have to be spent on extracting protein pathways from literature. Our aim is to develop a robust and powerful methodology to mine protein-protein interactions from biomedical texts. RESULTS: We present a novel and robust approach for extracting protein-protein interactions from literature. Our method uses a dynamic programming algorithm to compute distinguishing patterns by aligning relevant sentences and key verbs that describe protein interactions. A matching algorithm is designed to extract the interactions between proteins. Equipped only with a dictionary of protein names, our system achieves a recall rate of 80.0% and precision rate of 80.5%. AVAILABILITY: The program is available on request from the authors.

A fundamental question in information theory and in computer science is how to measure similarity or the amount of shared information between two sequences. We have proposed a metric, based on Kolmogorov complexity, to answer this question and have proven it to be universal. We apply this metric in measuring the amount of shared information between two computer programs, to enable plagiarism detection. We have designed and implemented a practical system SID (Software Integrity Diagnosis system) that approximates this metric by a heuristic compression algorithm. Experimental results demonstrate that SID has clear advantages over other plagiarism detection systems. SID system server is online at http://software.bioinformatics.uwaterloo.ca/SID/.

A new class of distances appropriate for measuring similarity relations between sequences, say one type of similarity per distance, is studied. We propose a new "normalized information distance," based on the noncomputable notion of Kolmogorov complexity, and show that it is in this class and it minorizes every computable distance in the class (that is, it is universal in that it discovers all computable similarities). We demonstrate that it is a metric and call it the similarity metric . This theory forms the foundation for a new practical tool. To evidence generality and robustness, we give two distinctive applications in widely divergent areas using standard compression programs like gzip and GenCompress. First, we compare whole mitochondrial genomes and infer their evolutionary history. This results in a first completely automatic computed whole mitochondrial phylogeny tree. Secondly, we fully automatically compute the language tree of 52 different languages.

Abstract Summary: While achieving the best compression ratios for DNA sequences, our new DNACompress program significantly improves the running time of all previous DNA compression programs. Availability: http://dna.cs.ucsb.edu/DNACompress Contact: [email protected]@cs.ucsb.edu * To whom correspondence should be addressed.

MOTIVATION: Genomics and proteomics studies routinely depend on homology searches based on the strategy of finding short seed matches which are then extended. The exploding genomic data growth presents a dilemma for DNA homology search techniques: increasing seed size decreases sensitivity whereas decreasing seed size slows down computation. RESULTS: We present a new homology search algorithm 'PatternHunter' that uses a novel seed model for increased sensitivity and new hit-processing techniques for significantly increased speed. At Blast levels of sensitivity, PatternHunter is able to find homologies between sequences as large as human chromosomes, in mere hours on a desktop. AVAILABILITY: PatternHunter is available at http://www.bioinformaticssolutions.com, as a commercial package. It runs on all platforms that support Java. PatternHunter technology is being patented; commercial use requires a license from BSI, while non-commercial use will be free.

The problem of finding a center string that is "close" to every given string arises in computational molecular biology and coding theory. This problem has two versions: the Closest String problem and the Closest Substring problem. Given a set of strings S = { s 1 , s 2 , ..., s n }, each of length m , the Closest String problem is to find the smallest d and a string s of length m which is within Hamming distance d to each s i ε S . This problem comes from coding theory when we are looking for a code not too far away from a given set of codes. Closest Substring problem, with an additional input integer L , asks for the smallest d and a string s , of length L , which is within Hamming distance d away from a substring, of length L , of each si. This problem is much more elusive than the Closest String problem. The Closest Substring problem is formulated from applications in finding conserved regions, identifying genetic drug targets and generating genetic probes in molecular biology. Whether there are efficient approximation algorithms for both problems are major open questions in this area. We present two polynomial-time approximation algorithms with approximation ratio 1 + ε for any small ε to settle both questions.

MOTIVATION: Traditional sequence distances require an alignment and therefore are not directly applicable to the problem of whole genome phylogeny where events such as rearrangements make full length alignments impossible. We present a sequence distance that works on unaligned sequences using the information theoretical concept of Kolmogorov complexity and a program to estimate this distance. RESULTS: We establish the mathematical foundations of our distance and illustrate its use by constructing a phylogeny of the Eutherian orders using complete unaligned mitochondrial genomes. This phylogeny is consistent with the commonly accepted one for the Eutherians. A second, larger mammalian dataset is also analyzed, yielding a phylogeny generally consistent with the commonly accepted one for the mammals. AVAILABILITY: The program to estimate our sequence distance, is available at http://www.cs.cityu.edu.hk/~cssamk/gencomp/GenCompress1.htm. The distance matrices used to generate our phylogenies are available at http://www.math.uwaterloo.ca/~mli/distance.html.

We present a lossless compression algorithm, Gen-Compress, for DNA sequences, based on searching for approximate repeats. Our algorithm achieves the best compression ratios for benchmark DNA sequences, comparing to other DNA compression programs [3, 7]. Significantly better compression results show that the approximate repeats are one of the main hidden regularities in DNA sequences.

Multiple sequence alignment is one of the most important problems in computational biology.Because of its notorious difficulties, aligning sequences within a constant band is a popular practice in bioinformatics with good results [17; 13; 14; 15; 1; 3; 6; 20; 18].However, the problem is still NP-hard for multiple sequences.In this paper, we present polynomial time approximation schemes (PTAS) for multiple sequence alignment within a constant band, tinder standard models of SP alignment and consensus (star) alignment.The algorithms work for very general score schemes.In order to prove our main results, we also present a PTAS for SP alignment and a PTAS for consensus alignment, allowing only constant number of insertion and deletion gaps (of arbitrary length) per sequence on the average.

We demonstrate an Ω( pn 1+1/ p ) lower bound on the average-case running time (uniform distribution) of p -pass Shellsort. This is the first nontrivial general lower bound for average-case Shellsort.

Inferring evolutionary trees has long been a challenging problem for both biologists and computer scientists. In recent years research has concentrated on the quartet method paradigm for inferring evolutionary trees. Quartet methods proceed by first inferring the evolutionary history for every set of four species (resulting in a set Q of inferred quartet topologies) and then recombining these inferred quartet topologies to form an evolutionary tree. This paper presents two results on the quartet method paradigm. The first is a polynomial time approximation scheme (PTAS) for recombining the inferred quartet topologies optimally. This is an important result since, to date, there have been no polynomial time algorithms with performance guarantees for quartet methods. To achieve this result the natural denseness of the set Q is exploited. The second result is a new technique, called quartet cleaning, that detects and corrects errors in the set Q with performance guarantees. This result has particular significance since quartet methods are usually very sensitive to errors in the data. It is shown how quartet cleaning can dramatically increase the accuracy of quartet methods.

This paper studies various algorithmic issues in reconstructing a species tree from gene trees under the duplication and the mutation costmodel. This is a fundamental problem in computational molecular biology. Our main results are as follows. A linear time algorithm is presented for computing all the losses in duplications associated with the least common ancestor mapping from a gene tree to a species tree. This answers a problem raised recently by Eulenstein, Mirkin, and Vingron [J. Comput. Bio., 5 (1998), pp. 135--148]. The complexity of finding an optimal species tree from gene trees is studied. The problem is proved to be NP-hard for the duplication cost and for the mutation cost. Further, the concept of reconciled trees was introduced by Goodman et al. and formalized by Page for visualizing the relationship between gene and species trees. We show that constructing an optimal reconciled tree for gene trees is also NP-hard. Finally, we consider a general reconstruction problem and show it to be NP-hard even for the well-known nearest neighbor interchange distance. A new and efficiently computable metric is defined based on the duplication cost. We show that the problem of finding an optimal species tree from gene trees is NP-hard under this new metric but it can be approximated within factor 2 in polynomial time. Using this approximation result, we propose a heuristic method for finding a species tree from gene trees with uniquely labeled leaves under the duplication cost. Our experimental tests demonstrate that when the number of species is larger than 15 and gene trees are close to each other, our heuristic method is significantly better than the existing program in Page's GeneTree 1.0 that starts the search from a random tree.

The relationship between the Bayesian approach and the minimum description length approach is established. We sharpen and clarify the general modeling principles minimum description length (MDL) and minimum message length (MML), abstracted as the ideal MDL principle and defined from Bayes's rule by means of Kolmogorov complexity. The basic condition under which the ideal principle should be applied is encapsulated as the fundamental inequality, which in broad terms states that the principle is valid when the data are random, relative to every contemplated hypothesis and also these hypotheses are random relative to the (universal) prior. The ideal principle states that the prior probability associated with the hypothesis should be given by the algorithmic universal probability, and the sum of the log universal probability of the model plus the log of the probability of the data given the model should be minimized. If we restrict the model class to finite sets then application of the ideal principle turns into Kolmogorov's minimal sufficient statistic. In general, we show that data compression is almost always the best strategy, both in model selection and prediction.

Heilbronn's triangle problem asks for the least /spl Delta/ such that n points lying in the unit disc necessarily contain a triangle of area at most /spl Delta/. Heilbronn initially conjectured /spl Delta/=O(1/n/sup 2/). As a result of concerted mathematical effort it is currently known that there are positive constants c and C such that c log n/n/sup 2//spl les//spl Delta//spl les/C/n/sup 8/7-/spl epsiv// for every constant /spl epsiv/>0. We resolve Heilbronn's problem in the expected case: If we uniformly at random put n points in the unit disc then (i) the area of the smallest triangle has expectation /spl Theta/(1/n/sup 3/); and (ii) the smallest triangle has area /spl Theta/(1/n/sup 3/) with probability almost one. Our proof uses the incompressibility method based on Kolmogorov complexity.

Algorithms for finding similar, or highly conserved, regions in a group of sequences are at the core of many molecular biology problems.We solve three main open questions in this area.Assume that we are given n DNA sequences 81,., an.The Consensus Patterns problem, which has been widely studied in bioinformatics research [26,16,12,25,4, 6, 15, 22, 24, 271, in its simplest form, asks for a region of length L in each ai, and a median string s of length L so that the total Hamming distance from B to these regions is minimized.We show the problem is NPhard and give a polynomial time approximation scheme (PTAS) for it.We also give a PTAS for the problem under the original measure of [26,16,12, 251.As an interesting application of OUT analysis, we further obtain a PTAS for a restricted (but still NP-hard) version of the important star alignment problem allowing at most constant number of gaps, each of arbitrary length, in each sequence.The Closest String problem [Z, 3, 7, 9, 181 asks for the smallest d and a string d which is within Hamming distance d to each a;.The problem is NP-hard [7, 181.[3] gives a polynomial time algorithm for constant d.For super-logarithmic d, [Z, 91 give efficient approximation algorithms using linear program relaxation techniques.The best polynomial time approximation has ratio $ for all d, given by [18] ([9] also independently claimed the $ ratio but only for super-logarithmic d).We settle the problem with a PTAS.We then give the fist nontrivial better-than-2 approximation with ratio 2 -& for the more eluive Closest Substring problem [IS]: find a string d of length L such that, for each i, s is within Hamming distance d from home substring, of length L, of si.

The incompressibility method is an elementary yet powerful proof technique. It has been used successfully in many areas. To further demonstrate its power and elegance we exhibit new simple proofs using the incompressibility method.

We investigate topological, combinatorial, statistical, and enumeration properties of finite graphs with high Kolmogorov complexity (almost all graphs) using the novel incompressibility method. Example results are (i) the mean and variance of the number of (possibly overlapping) ordered labeled subgraphs of a labeled graph as a function of its randomness deficiency (how far it falls short of the maximum possible Kolmogorov complexity) and (ii) a new elementary proof for the number of unlabeled graphs.

Inferring evolutionary trees has long been a challenging problem both for biologists and computer scientists. In recent years research has concentrated on the quartet method paradigm for inferring evolutionary trees. Quartet methods proceed by first inferring the evolutionary history for every set of four species (resulting in a set Q of inferred quarter topologies) and then recombining these inferred quarter topologies to form an evolutionary tree. This paper presents two results on the quartet method paradigm. The first is a polynomial time approximation scheme (PTAS) for recombining the inferred quartet topologies optimally. This is an important result since, to date, there have been no polynomial time algorithms with performance guarantees for quartet methods. In fact, this is the first known PTAS for inferring evolutionary trees under any paradigm. To achieve this result the natural denseness of the set Q is exploited. The second result is a new technique, called quartet cleaning, that detects and corrects errors in the set Q with performance guarantees. This result has particular significance since quartet methods are usually very sensitive to errors in the data. It is shown how quartet cleaning can dramatically increase the accuracy of quartet methods.

and Losses Bin Ma: Ming Lif and

The paper studies the computational complexity and approximation algorithms for a new evolutionary distance between multi-chromosomal genomes introduced recently by Ferretti, Nadeau and Sankoff. Here, a chromosome is represented as a set of genes and a genome is a collections of chromosomes. The syntenic distance between two genomes is defined as the minimum number of translocations, fusions and fissions required to transform one genome into the other. We prove that computing the syntenic distance is NP-hard and give a simple approximation algorithm with performance ratio 2. For the case when an upper bound d on the syntenic distance is known, we show that an optimal syntenic sequence can be found in O(nk + 2o(d2)) time, where n and k are the number of chromosomes in the two given genomes. Next, we show that if the set of operations for transforming a genome is significantly restricted, we can nevertheless find a solution that performs at most O(log d) additional moves, where d is the number of moves performed by the unrestricted optimum. This result should help in the design of approximation algorithms. Finally, we investigate the median problem: Given three genomes, construct a genome minimizing the total syntenic distance to the three given genomes and compute the corresponding median distance. The problem has application in the inference of phytogenies based on the syntenic distance. We prove that the problem is NP-hard and design a polynomial time approximation algorithm with a performance ratio of 4+ε for any constant ε > 0.

We demonstrate the use of Kolmogorov complexity in average case analysis of algorithms through a classical example: adding two n-bit numbers in [log2 n] + 2 steps on average. We simplify the analysis of Burks et al. (1961) and (in more complete forms) Briley (1973) and Schay (1995).

While Kolmogorov (1965) complexity is the accepted absolute measure of information content in an individual finite object, a similarly absolute notion is needed for the information distance between two individual objects, for example, two pictures. We give several natural definitions of a universal information metric, based on length of shortest programs for either ordinary computations or reversible (dissipationless) computations. It turns out that these definitions are equivalent up to an additive logarithmic term. We show that the information distance is a universal cognitive similarity distance. We investigate the maximal correlation of the shortest programs involved, the maximal uncorrelation of programs (a generalization of the Slepian-Wolf theorem of classical information theory), and the density properties of the discrete metric spaces induced by the information distances. A related distance measures the amount of nonreversibility of a computation. Using the physical theory of reversible computation, we give an appropriate (universal, antisymmetric, and transitive) measure of the thermodynamic work required to transform one object in another object by the most efficient process. Information distance between individual objects is needed in pattern recognition where one wants to express effective notions of "pattern similarity" or "cognitive similarity" between individual objects and in thermodynamics of computation where one wants to analyze the energy dissipation of a computation from a particular input to a particular output.

Article Free Access Share on On the complexity and approximation of syntenic distance Authors: B. DasGupta Department of Computer Science, Rutgers University, Camden, NJ Department of Computer Science, Rutgers University, Camden, NJView Profile , T. Jiang Department of Computer Science, McMaster University, Hamilton, Ontario L8S 4K1, Canada Department of Computer Science, McMaster University, Hamilton, Ontario L8S 4K1, CanadaView Profile , S. Kannan Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PAView Profile , M. Li Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong Department of Computer Science, City University of Hong Kong, Kowloon, Hong KongView Profile , Z. Sweedyk Department of Computer and Information Sciences, University of Pennsylvania, Philadelphia, PA Department of Computer and Information Sciences, University of Pennsylvania, Philadelphia, PAView Profile Authors Info & Claims RECOMB '97: Proceedings of the first annual international conference on Computational molecular biologyJanuary 1997 Pages 99–108https://doi.org/10.1145/267521.267536Published:19 January 1997Publication History 6citation243DownloadsMetricsTotal Citations6Total Downloads243Last 12 Months11Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Reversible simulation of irreversible algorithms is analysed in the stylized form of a "reversible" pebble game. While such simulations incur little overhead in additional computation time, they use a large amount of additional memory space during the computation. We show that among all simulations which can be modelled by the pebble game, Bennett's simulation is optimal in that it uses the least auxiliary space for the greatest number of simulated steps. We give a trade-off of storage space versus irreversible erasure. Examples of reversible algorithms are algorithms for quantum computers.

Sharing data between multiple asynchronous users—each of which can atomically read and write the data—is a feature that may help to increase the amount of parallelism in distributed systems. An algorithm implementing this feature is presented. The main construction of an n -user atomic variable directly from single-writer, single-reader atomic variables uses O(n) control bits and O(n) accesses per Read/Write running in O(1) parallel time.

The problems of finding shortest common supersequences (SCS) and longest common subsequences (LCS) are two well-known ${\textbf NP}$-hard problems that have applications in many areas, including computational molecular biology, data compression, robot motion planning, and scheduling, text editing, etc. A lot of fruitless effort has been spent in searching for good approximation algorithms for these problems. In this paper, we show that these problems are inherently hard to approximate in the worst case. In particular, we prove that (i) SCS does not have a polynomial-time linear approximation algorithm unless $\textbf{P} = \textbf{NP}$; (ii) There exists a constant $\delta > 0$ such that, if SCS has a polynomial-time approximation algorithm with ratio $\log^{\delta} n$, where n is the number of input sequences, then ${\textbf NP}$ is contained in $\textbf{DTIME}(2^{\operatorname{polylog} n})$; (iii) There exists a constant $\delta > 0$ such that, if LCS has apolynomial-time approximation algorithm with performance ratio $n^{\delta}$, then $\textbf{P} = \textbf{NP}$. The proofs utilize the recent results of Arora et al. [Proc. 23rd IEEE Symposium on Foundations of Computer Science, 1992, pp. 14–23] on the complexity of approximation problems. In the second part of the paper, we introduce a new method for analyzing the average-case performance of algorithms for sequences, based on Kolmogorov complexity. Despite the above nonapproximability results, we show that near optimal solutions for both SCS and LCS can be found on the average. More precisely, consider a fixed alphabet $\Sigma$ and suppose that the input sequences are generated randomly according to the uniform probability distribution and are of the same length n. Moreover, assume that the number of input sequences is polynomial in n. Then, there are simple greedy algorithms which approximate SCS and LCS with expected additive errors $O(n^{0.707})$ and $O(n^{1/2+\epsilon})$ for any $\epsilon > 0$, respectively. Incidentally, our analyses also provide tight upper and lower bounds on the expected LCS and SCS lengths for a set of random sequences solving a generalization of another well-known open question on the expected LCS length for two random sequences [K. Alexander, The rate of convergence of the mean length of the longest common subsequence,1992, manuscript], [V. Chvatal and D. Sankoff, J. Appl. Probab., 12 (1975), pp. 306–315], [D. Sankoff and J. Kruskall, eds., Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison, Addison-Wesley, Reading, MA, 1983].

We present a new approach to formal language theory by using Kolmogorov complexity. The main results presented here are an alternative for pumping lemma(s), a new characterization for regular languages, and a new method to separate deterministic context-free languages and nondeterministic context-free languages. The use of the “incompressibility arguments” is illustrated by many examples. The approach is also successful at the high end of the Chomsky hierarchy since one can quantify nonrecursiveness in terms of Kolmogorov complexity.

We consider the following problem: given a collection of strings s 1 ,…, s m , find the shortest string s such that each s i appears as a substring (a consecutive block) of s . Although this problem is known to be NP-hard, a simple greedy procedure appears to do quite well and is routinely used in DNA sequencing and data compression practice, namely: repeatedly merge the pair of (distinct) strings with maximum overlap until only one string remains. Let n denote the length of the optimal superstring. A common conjecture states that the above greedy procedure produces a superstring of length O(n) (in fact, 2 n ), yet the only previous nontrivial bound known for any polynomial-time algorithm is a recent O(n log n ) result. We show that the greedy algorithm does in fact achieve a constant factor approximation, proving an upper bound of 4 n . Furthermore, we present a simple modified version of the greedy algorithm that we show produces a superstring of length at most 3 n . We also show the superstring problem to be MAXSNP-hard, which implies that a polynomial-time approximation scheme for this problem is unlikely.

Efficient distribution-free learning of Boolean formulas from positive and negative examples is considered. It is shown that classes of formulas that are efficiently learnable from only positive examples or only negative examples have certain closure properties. A new substitution technique is used to show that in the distribution-free case learning DNF (disjunctive normal form formulas) is no harder than learning monotone DNF. We prove that monomials cannot be efficiently learned from negative examples alone, even if the negative examples are uniformly distributed. It is also shown that, if the examples are drawn from uniform distributions, then the class of DNF in which each variable occurs at most once is efficiently weakly learnable (i.e., individual examples are correctly classified with a probability larger than 1/2 + 1/ p , where p is a polynomial in the relevant parameters of the learning problem). We then show an equivalence between the notion of weak learning and the notion of group learning , where a group of examples of polynomial size, either all positive or all negative, must be correctly classified with high probability.

This paper studies the wait-free consensus problem in the asynchronous shared memory model. In this model, processors communicate by shared registers that allow atomic read and write operations (but do not support atomic test-and-set). It is known that the wait-free consensus problem cannot be solved by deterministic protocols. A randomized solution is presented. This protocol is simple, constructive, tolerates up to $n - 1$ processors crashes (where n is the number of processors), and its expected run-time is $O(n^2 )$.

Applying the tools of algorithmic information theory, we compare several candidates for an asymptotically machine-independent. absolute measure of the informational or ``cognitive`` distance between discrete objects x and y. The maximum of the conditional Kolmogorov complexities max{l_brace}K(y{vert_bar}z) K(m{vert_bar}y){r_brace}, is shown to be optimal, in the sense of being minimal within an additive constant among semicomputable, symmetric, positive semidefinite functions of z and y satisfying a reasonable normalization condition and obeying the triangle intequality. The optimal metric, in turn, differs by at most an additive logarithmic term from the size of the smallest program for a universal reversible computer to transform x into y. This program functions in a `catalytic`` capacity, being retained in the computer before, during, and after the computation. Similarly, the sum of the conditional complexities. K(y{vert_bar}x) + K(x{vert_bar}y), is shown to be equal within a logarithmic term to the minimal amount Of information flowing out and in during a reversible computation in which the program is not retained. Finally. using the physical theory of reversible computation, it is shown that the simple difference K(x) - K(y) is an appropriate (ie universal, antisymmetric, and transitive) measure of the amount of thermodynamic work required to transform string x into string y by the most efficient process.

Article k one-way heads cannot do string-matching Share on Authors: Tao Jiang View Profile , Ming Li View Profile Authors Info & Claims STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of ComputingJune 1993 Pages 62–70https://doi.org/10.1145/167088.167111Online:01 June 1993Publication History 5citation253DownloadsMetricsTotal Citations5Total Downloads253Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

In this paper an extension of the distribution-free model of learning introduced by Valiant [Comm. ACM, 27(1984), pp. 1134–1142] that allows the presence of malicious errors in the examples given to a learning algorithm is studied. Such errors are generated by an adversary with unbounded computational power and access to the entire history of the learning algorithm’s computation. Thus, a worst-case model of errors is studied. The results of this research include general methods for bounding the rate of error tolerable by any learning algorithm, efficient algorithms tolerating nontrivial rates of malicious errors, and equivalences between problems of learning with errors and standard combinatorial optimization problems.

Queues, stacks, and tapes are basic concepts that have direct applications in compiler design and the general design of algorithms. Whereas stacks (pushdown store or last-in–first-out storage) have been thoroughly investigated and are well understood, this is much less the case for queues (first-in-first-out storage). In this paper a comprehensive study comparing queues to stacks and tapes (off-line and with a one-way input tape) is presented. The techniques used rely on Kolmogorov complexity. In particular, one queue and one tape (or stack) are incomparable: (1) Simulating one stack (and hence one tape) by one queue requires $\Omega (n^{4/3} /\log n)$ time in both the deterministic and the nondeterministic cases. A corollary of this lower bound states that for this model of one-queue machines, nondeterministic linear time is not closed under complement. (2) Simulating one queue by one tape requires $\Omega (n^2 )$ time in the deterministic case and requires $\Omega (n^{4/3}/(\log n)^{2/3} )$ in the nondeterministic case. The paper further compares the relative power between different numbers of queues: (3) Simulating two queues (or two tapes) by one queue requires $\Omega (n^2 )$ time in the deterministic case, and $\Omega (n^2 /(\log ^2 n\log \log n))$ in the nondeterministic case. The deterministic bound is tight. The nondeterministic one is almost tight. The upper bounds for queues are also obtained.

Article Free Access Share on Linear approximation of shortest superstrings Authors: Avrim Blum Massachusetts Institute of Technology, Cambridge, MA Massachusetts Institute of Technology, Cambridge, MAView Profile , Tao Jiang McMaster Univ., Hamilton, Ontario, CANADA McMaster Univ., Hamilton, Ontario, CANADAView Profile , Ming Li Univ. of Waterloo, Ontario, CANADA Univ. of Waterloo, Ontario, CANADAView Profile , John Tromp CWI, Amsterdam, The Netherlands CWI, Amsterdam, The NetherlandsView Profile , Mihalis Yannakakis AT&T Bell Labs. Murray Hill, NJ AT&T Bell Labs. Murray Hill, NJView Profile Authors Info & Claims STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of ComputingJanuary 1991 Pages 328–336https://doi.org/10.1145/103418.103455Published:03 January 1991Publication History 37citation440DownloadsMetricsTotal Citations37Total Downloads440Last 12 Months21Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

This paper aims at developing a learning theory where “simple” concepts are easily learnable. In Valiant’s learning model, many concepts turn out to be too hard (like NP hard) to learn. Relatively few concept classes were shown to be learnable polynomially. In daily life, it seems that things we care to learn are usually learnable. To model the intuitive notion of learning more closely, it is not required that the learning algorithm learn (polynomially) under all distributions, but only under all simple distributions. A distribution is simple if it is dominated by an enumerable distribution. All distributions with computable parameters that are used in statistics are simple. Simple distributions are complete in the sense that a concept class is learnable under all simple distributions if and only if it is learnable under a fixed “universal” simple distribution. This holds both for polynomial learning in the discrete case (under a modified model), and for non-time-restricted learning in the continuous case (under the usual model). This completeness result is used to obtain new learning algorithms and several quite general new learnable classes. These include a discrete class that is known to be not polynomial learnable under Valiant’s model, unless RP = NP, and a continuous class that is not learnable in Valiant’s model. The results here allow that for each concept class from a wide range of concept classes, for each underlying distribution from a wide range of distributions, the learning algorithm uses a single fixed procedure to draw examples by a single algorithmic process using a random number generator. The “universal” simple distribution is not computable. To make the theory feasible, a polynomial-time version is developed for it. All results derived for discrete sample spaces hold mutatis mutandis for the polynomial-time versions, including versions of completeness, the new learning algorithms, and the new learnable classes.

Mathematical frameworks suitable for massive automated DNA sequencing and for analyzing DNA sequencing algorithms are studied under plausible assumptions. The DNA sequencing problem is modeled as learning a superstring from its randomly drawn substrings. Under certain restrictions, this may be viewed as learning a superstring in L.G. Valiant's (1984) learning model, and in this case the author gives an efficient algorithm for learning a superstring and a quantitative bound on how many samples suffice. A major obstacle to the approach turns out to be a quite well-known open question on how to approximate the shortest common superstring of a set of strings. The author presents the first provably good algorithm that approximates the shortest superstring of length n by a superstring of length O(n log n).>

It is pointed out that in L.G. Valiant's learning model (Commun. ACM, vol.27, p.1134-42, 1984) many concepts turn out to be too hard to learn, whereas in practice, almost nothing we care to learn appears to be not learnable. To model the intuitive notion of learning more closely, it is assumed that learning happens under an arbitrary distribution, rather than under an arbitrary simple distribution, as assumed by Valiant. A distribution is called simple if it is dominated by a semicomputable distribution. A general theory of learning under simple distributions is developed. In particular, it is shown that one can learn under all simple distributions if one can learn under one fixed simple distribution, called the universal distribution. Interesting learning algorithms and several quite general new learnable classes are presented. It is shown that for essentially all algorithms, if the inputs are distributed according to the universal distribution, then the average-case complexity is of the same order of magnitude as the worst-case complexity.>

Lower bounds are proven on the parallel-time complexity of several basic functions on the most powerful concurrent-read concurrent-write PRAM with unlimited shared memory and unlimited power of individual processors (denoted by PRIORITY(∞)): It is proved that with a number of processors polynomial in n , Ω (log n ) time is needed for addition, multiplication or bitwise OR of n numbers, when each number has n ' bits. Hence even the bit complexity (i.e., the time complexity as a function of the total number of bits in the input) is logarithmic in this case. This improves a beautiful result of Meyer auf der Heide and Wigderson [22]. They proved a log n lower bound using Ramsey-type techniques. Using Ramsey theory, it is possible to get an upper bound on the number of bits in the inputs used. However, for the case of polynomially many processors, this upper bound is more than a polynomial in n . An Ω (log n ) lower bound is given for PRIORITY(∞) with n o(1) processors on a function with inputs from {0, 1}, namely for the function ƒ( x 1 , … , x n ,) = Σ n l - 1 x l a i where a is fixed and x i ε {0, 1}. Finally, by a new efficient simulation of PRIORITY(∞) by unbounded fan-in circuits, that with less than exponential number of processors, it is proven a PRIORITY(∞) cannot compute PARITY in constant time, and with n O(1) processors Ω(√log n ) time is needed. The simulation technique is of independent interest since it can serve as a general tool to translate circuit lower bounds into PRAM lower bounds. Further, the lower bounds in (1) and (2) remain valid for probabilistic or nondeterministic concurrent-read concurrent-write PRAMS.

Article Free Access Share on Learning in the presence of malicious errors Authors: Michael Kearns Harvard University Harvard UniversityView Profile , Ming Li Harvard University Harvard UniversityView Profile Authors Info & Claims STOC '88: Proceedings of the twentieth annual ACM symposium on Theory of computingJanuary 1988 Pages 267–280https://doi.org/10.1145/62212.62238Online:01 January 1988Publication History 62citation618DownloadsMetricsTotal Citations62Total Downloads618Last 12 Months31Last 6 weeks9 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Time-stamps are numerical labels which enable a system to keep track of temporal precedence relation among its data elements. Traditionally time-stamps are used as unbounded numbers and inevitable overflows cause a loss of this precedence relation. In this paper we develop a complete theory of bounded time-stamps. Time-stamp systems are defined and the complexity of their implementation is fully analyzed. This theory gives a very general tool for converting timestamp based protocols to bounded protocols. The generality of this theory is demonstrated by novel, conceptually simple, protocols for a multiuser atomic registers, as well as by proving for the first time a non-trivial lower bound for such a register.

We investigate an asynchronous model of concurrent computations, where processors communicate by shared registers that allow atomic read and write operations (but do not support atomic test-and-set).For this model, we define a general notion of processor coordination, and study the possibility and complexity of achieving coordination.Our definition includes, as special cases, mutual exclusion and asynchronous agreement.It is shown that the coordination problem cannot be solved by means of a deterministic protocol even if the system consists of only two processors.This impossibility result holds for the most powerful type of shared atomic registers and does not assume symmetric protocols.The impossibility result is contrasted by a variety of eficient randomized protocols, that achieve fast coordination for systems of arbitrary number of processors n.These protocols are all fairly simple, constructive, and their ezpectedrun-time is polynomial in n, even in the presence of an adaptive

Article Free Access Share on On the learnability of Boolean formulae Authors: M. Kearns Harvard University Harvard UniversityView Profile , M. Li Harvard University Harvard UniversityView Profile , L. Pitt University of Illinois University of IllinoisView Profile , L. Valiant Harvard University Harvard UniversityView Profile Authors Info & Claims STOC '87: Proceedings of the nineteenth annual ACM symposium on Theory of computingJanuary 1987 Pages 285–295https://doi.org/10.1145/28395.28426Online:01 January 1987Publication History 157citation769DownloadsMetricsTotal Citations157Total Downloads769Last 12 Months62Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We resolve the following long-standing conjecture of Harrison and Ibarra in 1968 [HI, p.462]: There are languages accepted by (k+1)-head 1-way deterministic pushdown automata ((k+1)-DPDA) but not by k-head 1-way pushdown automata (k-PDA), for every k. (Partial solutions for this conjecture can be found in [M1,M2,C].) On the assumption that their conjecture holds, [HI] also derived many important consequences. Now all those consequences become theorems. For example, the class of languages accepted by k-PDA's is not closed under ∩ and complementation. Several other interesting consequences also follow: CFL ⊆∪kDPDA(k) and FA(2)⊆∪kDPDA(k), where DPDA (k)={L|L is accepted by a k-DPDA} and FA(2)={L|L is accepted by a 2-head FA). Our new proof itself is also interesting in the sense that the k+l versus k heads problems was solved by diagonalization methods [I2,M2,M3,M4,S] for stronger machines (2-way, etc). and by traditional counting arguments [S2,IK,YR,M1] for weaker machines (k-FA, k-head counter machine, etc).

Article New lower bounds for parallel computation Share on Authors: M Li Department of Computer and Information Science, The Ohio State University, Columbus, OH Department of Computer and Information Science, The Ohio State University, Columbus, OHView Profile , Y Yesha Department of Computer and Information Science, The Ohio State University, Columbus, OH Department of Computer and Information Science, The Ohio State University, Columbus, OHView Profile Authors Info & Claims STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computingNovember 1986 Pages 177–187https://doi.org/10.1145/12130.12148Published:01 November 1986 11citation355DownloadsMetricsTotal Citations11Total Downloads355Last 12 Months4Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We show that string-matching cannot be performed by a two-head one-way deterministic finite automaton (or even by a Turing machine with two one-way input heads and o(n) storage space). Thus, we answer the special case k = 2 of the open question, due to Galil and Seiferas (1983), whether a k-head one-way deterministic finite automaton can perform string-matching.

Based on two graph separator theorems, we present two unexpected upper bounds and resolve several open problems for on-line computations. (1) 1 tape nondeterministic machines can simulate 2 pushdown stores in time O(n1.5√logn) (true for both on-line and off-line machines). Together with the Ω(n1.5/√logn) lower bound, this solves the open problem 1 in [DGPR] for the 1 tape vs. 2 pushdown case. It also disproves the commonly conjectured Ω(n2) lower bound. (2) The languages defined by Maass and Freivalds, aimed to obtain optimal lower bound for 1 tape nondeterministic machines, can be accepted in O(n2loglogn√logn) and O(n1.5√logn) time by a 1 tape TM, respectively. (3) 3 pushdown stores are better than 2 pushdown stores. This answers a rather old open problem by Book and Greibach, and Duris and Galil. An Ω(n4/3/loge n) lower bound is also obtained. (4) 1 tape can nondeterministically simulate 1 queue in O(n1.5/√logn) time. This disproves the conjectured Ω(n2) lower bound. Also 1 queue can simulate 2 pushdowns in time O(n1.5√logn).