On occurrence of subpattern and method of gambling teams

The expected value and generating function of the number of overlapping occurrences of a pattern P in a Markov chain until the first occurrence of a member from a finite collection of patterns that start with P is obtained. A martingale technique is employed to address the problem.      

Permutations and words counted by consecutive patterns

Generating functions which count occurrences of consecutive sequences in a permutation or a word which matches a given pattern are studied by exploiting the combinatorics associated with symmetric functions. Our theorems take the generating function for the number of permutations which do not contain a certain pattern and give generating functions refining permutations by the both the total number of pattern matches and the number of non-overlapping pattern matches. Our methods allow us to give new proofs of several previously recorded results on this topic as well as to prove new extensions and new q-analogues of such results.     

Permutations and words counted by consecutive patterns

Generating functions which count occurrences of consecutive sequences in a permutation or a word which matches a given pattern are studied by exploiting the combinatorics associated with symmetric functions. Our theorems take the generating function for the number of permutations which do not contain a certain pattern and give generating functions refining permutations by the both the total number of pattern matches and the number of non-overlapping pattern matches. Our methods allow us to give new proofs of several previously recorded results on this topic as well as to prove new extensions and new q-analogues of such results.     

An Inverse-Ackermann Type Lower Bound For Online Minimum Spanning Tree Verification*

Given a spanning tree T of some graph G, the problem of minimum spanning tree verification is to decide whether T = MST(G). A celebrated result of Komlós shows that this problem can be solved with a linear number of comparisons. Somewhat unexpectedly, MST verification turns out to be useful in actually computing minimum spanning trees from scratch. It is this application that has led some to wonder whether a more flexible version of MST verification could be used to derive a faster deterministic minimum spanning tree algorithm. In this paper we consider the online MST verification problem in which we are given a sequence of queries of the form “Is e in the MST of T ∪{e}?”, where the tree T is fixed. We prove that there are no linear-time solutions to the online MST verification problem, and in particular, that answering m queries requires Ω(mα(m,n)) time, where α(m,n) is the inverse-Ackermann function and n is the size of the tree. On the other hand, we show that if the weights of T are permuted randomly there is a simple data structure that preprocesses the tree in expected linear time and answers queries in constant time. * A preliminary version of this paper appeared in the proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS 2002), pages 155–163. † This work was supported by Texas Advanced Research Program Grant 003658-0029-1999, NSF Grant CCR-9988160, and an MCD Graduate Fellowship.     

Reducing The Seed Length In The Nisan-Wigderson Generator*

The Nisan–Wigderson pseudo-random generator [19] was constructed to derandomize probabilistic algorithms under the assumption that there exist explicit functions which are hard for small circuits. We give the first explicit construction of a pseudo-random generator with asymptotically optimal seed length even when given a function which is hard for relatively small circuits. Generators with optimal seed length were previously known only assuming hardness for exponential size circuits [13,26]. We also give the first explicit construction of an extractor which uses asymptotically optimal seed length for random sources of arbitrary min-entropy. Our construction is the first to use the optimal seed length for sub-polynomial entropy levels. It builds on the fundamental connection between extractors and pseudo-random generators discovered by Trevisan [29], combined with the construction above. The key is a new analysis of the NW-generator [19]. We show that it fails to be pseudorandom only if a much harder function can be efficiently constructed from the given hard function. By repeatedly using this idea we get a new recursive generator, which may be viewed as a reduction from the general case of arbitrary hardness to the solved case of exponential hardness. * This paper is based on two conference papers [11,12] by the same authors. † Research Supported by NSF Award CCR-9734911, NSF Award CCR-0098197, Sloan Research Fellowship BR-3311, grant #93025 of the joint US-Czechoslovak Science and Technology Program, and USA-Israel BSF Grant 97-00188. ‡ Part of this work was done while at the Hebrew University and the Institute for advanced study. § This research was supported by grant number 69/96 of the Israel Science Foundation, founded by the Israel Academy for Sciences and Humanities and USA-Israel BSF Grant 97-00188.     

Testing of matrix-poset properties

Combinatorial property testing, initiated by Rubinfeld and Sudan [23] and formally defined by Goldreich, Goldwasser and Ron in [18], deals with the following relaxation of decision problems: Given a fixed property P and an input f, distinguish between the case that f satisfies P, and the case that no input that differs from f in less than some fixed fraction of the places satisfies P. An (ε, q)-test for P is a randomized algorithm that queries at most q places of an input f and distinguishes with probability 2/3 between the case that f has the property and the case that at least an ε-fraction of the places of f need to be changed in order for it to have the property. Here we concentrate on labeled, d-dimensional grids, where the grid is viewed as a partially ordered set (poset) in the standard way (i.e. as a product order of total orders). The main result here presents an (ε, poly(1/ε))-test for every property of 0/1 labeled, d-dimensional grids that is characterized by a finite collection of forbidden induced posets. Such properties include the “monotonicity” property studied in [9,8,13], other more complicated forbidden chain patterns, and general forbidden poset patterns. We also present a (less efficient) test for such properties of labeled grids with larger fixed size alphabets. All the above tests have in addition a 1-sided error probability. This class of properties is related to properties that are defined by certain first order formulae with no quantifier alternation over the syntax containing the grid order relations. We also show that with one quantifier alternation, a certain property can be defined, for which no test with query complexity of O(n ^1/4) (for a small enough fixed ε) exists. The above results identify new classes of properties that are defined by means of restricted logics, and that are efficiently testable. They also lay out a platform that bridges some previous results. A preliminary version of these results formed part of [14]. Research supported in part by grant 55/03 from the Israel Science Foundation.     

A generalization of the monotonicity condition and applications

We introduce a new class of sequences called NBVS to generalize GBVS, essentially extending monotonicity from “one sided” to “two sided”, while some important classical results keep true. Supported in part by Natural Science Foundation of China under grant number 10471130.     

Computing the bump number with techniques from two-processor scheduling

Let (X, <) be a partially ordered set. A linear extension x ₁, x ₂, ... has a bump whenever x _i<x _i+1, and it has a jump whenever x _iand x _i+1are incomparable. The problem of finding a linear erxtension that minimizes the number of jumps has been studied extensively; Pulleyblank shows that it is NP-complete in the general case. Fishburn and Gehrlein raise the question of finding a linear extension that minimizes the number of bumps. We show that the bump number problem is closely related to the well-studied problem of scheduling unit-time tasks with a precedence partial order on two identical processors. We point out that a variant of Gabow's linear-time algorithm for the two-processor scheduling problem solves the bump number problem. Habib, Möhring, and Steiner have independently discovered a different polynomial-time algorithm to solve the bump number problem.Part of this work was done while the first author was a Research Student Associate at IBM Almaden Research Center. During the academic year his work is primarily supported by a Fannie and John Hertz Foundation Fellowship and is supported in part by ONR contract N00014-85-C-0731.     

A fast parallel algorithm to compute the rank of a matrix over an arbitrary field

It is shown that the rank of a matrix over an arbitrary field can be computed inO(log² n) time using a polynomial number of processors. Also appeared in ACM Symposium on Theory of Computing, May 28–30, 1986 Berkeley, California. Research supported by Miller Fellowship, University of California, Berkeley.     

Polling systems in heavy traffic: Exhaustiveness of service policies

We study the expected delay in cyclic polling models with general ‘branching-type’ service disciplines. For this class of models, which contains models with exhaustive and gated service as special cases, we obtain closed-form expressions for the expected delay under standard heavy-traffic scalings. We identify a single parameter associated with the service discipline at each queue, which we call the ‘exhaustiveness’. We show that the scaled expected delay figures depend on the service policies at the queues only through the exhaustiveness of each of the service disciplines. This implies that the influence of different service disciplines, but with the same exhaustiveness, on the expected delays at the queues becomes the same when the system reaches saturation. This observation leads to a new classification of the service disciplines. In addition, we show monotonicity of the scaled expected delays with respect to the exhaustiveness of the service disciplines. This induces a complete ordering in terms of efficiency of the service disciplines. The results also lead to new rules for optimization of the system performance with respect to the service disciplines at the queues. Further, the exact asymptotic results suggest simple expected waiting-time approximations for polling models in heavy traffic. Numerical experiments show that the accuracy of the approximations is excellent for practical heavy-traffic scenarios. This revised version was published online in June 2006 with corrections to the Cover Date.     

On The Parameterized Intractability Of Motif Search Problems*

We show that Closest Substring, one of the most important problems in the field of consensus string analysis, is W[1]-hard when parameterized by the number k of input strings (and remains so, even over a binary alphabet). This is done by giving a “strongly structure-preserving” reduction from the graph problem Clique to Closest Substring. This problem is therefore unlikely to be solvable in time O(f(k)•n^c) for any function f of k and constant c independent of k, i.e., the combinatorial explosion seemingly inherent to this NP-hard problem cannot be restricted to parameter k. The problem can therefore be expected to be intractable, in any practical sense, for k ≥ 3. Our result supports the intuition that Closest Substring is computationally much harder than the special case of Closest String, althoughb othp roblems are NP-complete. We also prove W[1]-hardness for other parameterizations in the case of unbounded alphabet size. Our W[1]-hardness result for Closest Substring generalizes to Consensus Patterns, a problem arising in computational biology. * An extended abstract of this paper was presented at the 19th International Symposium on Theoretical Aspects of Computer Science (STACS 2002), Springer-Verlag, LNCS 2285, pages 262–273, held in Juan-Les-Pins, France, March 14–16, 2002. † Work was supported by the Deutsche Forschungsgemeinschaft (DFG), research project “OPAL” (optimal solutions for hard problems in computational biology), NI 369/2. ‡ Work was done while the author was with Wilhelm-Schickard-Institut für Informatik, Universit?t Tübingen. Work was partially supported by the Deutsche Forschungsgemeinschaft (DFG), Emmy Noether research group “PIAF” (fixed-parameter algorithms), NI 369/4.     

Towards Minimal Addition Chains Using Ant Colony Optimisation

Modular exponentiation is one of the most important operations in almost all modern cryptosystems. It is performed using a series of modular multiplications. This operation is time consuming for large operands as is always the case in cryptography. Hence fast public-key cryptography software or hardware requires optimisation of the time consumed by a single modular multiplication and/or the reduction of the total number of modular multiplications required. This paper introduces a novel idea based on the principles of ant colony optimisation for finding a minimal addition chain that allows one to reduce the number of modular multiplications so that modular exponentiation can be implemented efficiently. The best addition chain reached by the ant system is compared to the one used in the m-ary and sliding window methods as well as with the best addition chain evolved by genetic algorithms. We demonstrate that the ant system significantly outperforms all these methods for any exponent size. ^★★ Research supported by FAPERJ () and CNPq ().     

Monotonicity and Consistency in Matching Markets

Objective: To obtain axiomatic characterizations of the core of one-to-one and one-to-many matching markets. Methods: The axioms recently applied to characterize the core of assignment games were adapted to the models of this paper. Results: The core of one-to-one matching markets is characterized by two different lists of axioms. The first one consists of weak unanimity, population monotonicity, and Maskin monotonicity. The second consists of weak unanimity, population monotonicity, and consistency. If we allow for weak preferences, the core is characterized by weak unanimity, population monotonicity, Maskin monotonicity, and consistency. For one-to-many matchings, the same lists as for the case of strict preferences characterize the core. Conclusions: The cores of the discrete matching markets are characterized by axioms that almost overlap with the axioms characterizing the core of the continuous matching markets. This provides an axiomatic explanation for the observations in the literature that almost parallel properties are obtained for the core of the two models. We observe that Maskin monotonicity is closely related to consistency in matching marketsThis research is financially supported by Waseda University Grant for Special Research Projects #2000A−887, 21COE-GLOPE, and Grant-in-Aid for Scientific Research #15530125, JSPS. This paper was presented at the 7th. International Meeting of the Society for Social Choice and Welfare held in Osaka, Japan. The comments of the participants are gratefully acknowledged. The author thanks Professors William Thomson, Eiichi Miyagawa and anonymous referees for their valuable comments and suggestions. Any remaining errors are independent     

Efficient algorithms for finding minimum spanning trees in undirected and directed graphs

Recently, Fredman and Tarjan invented a new, especially efficient form of heap (priority queue). Their data structure, theFibonacci heap (or F-heap) supports arbitrary deletion inO(logn) amortized time and other heap operations inO(1) amortized time. In this paper we use F-heaps to obtain fast algorithms for finding minimum spanning trees in undirected and directed graphs. For an undirected graph containingn vertices andm edges, our minimum spanning tree algorithm runs inO(m logβ (m, n)) time, improved fromO(mβ(m, n)) time, whereβ(m, n)=min {i|log⁽ⁱ⁾ n ≦m/n}. Our minimum spanning tree algorithm for directed graphs runs inO(n logn + m) time, improved fromO(n log n +m log log log_(m/n+2) n). Both algorithms can be extended to allow a degree constraint at one vertex. Research supported in part by National Science Foundation Grant MCS-8302648. Research supported in part by National Science Foundation Grant MCS-8303139. Research supported in part by National Science Foundation Grant MCS-8300984 and a United States Army Research Office Program Fellowship, DAAG29-83-GO020.     

Higman’s question revisited

We construct a two-generated group with the co-recursively enumerable word problem that has no presentation by recursive permutations. This answers Higman’s question and exemplifies a group with the minimal possible number of generators. The previous article [1], in which that question was claimed settled, contains an incorrigible error. Dedicated to the 60th birthday of Academician Yu. L. Ershov Supported by the Alexander von Humboldt Foundation. This result was obtained during my work at the University of Heidelberg (Germany) as Alexander von Humboldt Research Fellow. The term a “II-group” was proposed by A. Nies. Translated fromAlgebra i Logika, Vol. 39, No. 2, pp. 134–144, March–April, 2000.     

A Tutorial on Computational Cluster Analysis with Applications to Pattern Discovery in Microarray Data

Microarrays offer unprecedented possibilities for the so-called omic, e.g., genomic and proteomic, research. However, they are also quite challenging data to analyze. The aim of this paper is to provide a short tutorial on the most common approaches used for pattern discovery and cluster analysis as they are currently used for microarrays, in the hope to bring the attention of the Algorithmic Community on novel aspects of classification and data analysis that deserve attention and have potential for high reward. R. Giancarlo is partially supported by Italian MIUR grants PRIN “Metodi Combinatori ed Algoritmici per la Scoperta di Patterns in Biosequenze” and FIRB “Bioinformatica per la Genomica e la Proteomica” and Italy-Israel FIRB Project “Pattern Discovery Algorithms in Discrete Structures, with Applications to Bioinformatics”. D. Scaturro is supported by a MIUR Fellowship in the Italy-Israel FIRB Project “Pattern Discovery Algorithms in Discrete Structures, with Applications to Bioinformatics”.     

An analysis of a Monte Carlo algorithm for estimating the permanent

Karmarkar, Karp, Lipton, Lovász, and Luby proposed a Monte Carlo algorithm for approximating the permanent of a non-negativen×n matrix, which is based on an easily computed, unbiased estimator. It is not difficult to construct 0,1-matrices for which the variance of this estimator is very large, so that an exponential number of trials is necessary to obtain a reliable approximation that is within a constant factor of the correct value. Nevertheless, the same authors conjectured that for a random 0,1-matrix the variance of the estimator is typically small. The conjecture is shown to be true; indeed, for almost every 0,1-matrixA, just O(nw(n)e ^-2) trials suffice to obtain a reliable approximation to the permanent ofA within a factor 1±ɛ of the correct value. Here ω(n) is any function tending to infinity asn→∞. This result extends to random 0,1-matrices with density at leastn ^−1/2ω(n). It is also shown that polynomially many trials suffice to approximate the permanent of any dense 0,1-matrix, i.e., one in which every row- and column-sum is at least (1/2+α)n, for some constant α>0. The degree of the polynomial bounding the number of trials is a function of α, and increases as α→0. Supported by NSF grant CCR-9225008. The work described here was partly carried out while the author was visiting Princeton University as a guest of DIMACS (Center for Discrete Mathematics and Computer Science).     

Improved bounds on the max-flow min-cut ratio for multicommodity flows

In this paper we consider the worst case ratio between the capacity of min-cuts and the value of max-flow for multicommodity flow problems. We improve the best known bounds for the min-cut max-flow ratio for multicommodity flows in undirected graphs, by replacing theO(logD) in the bound byO(logk), whereD denotes the sum of all demands, andk demotes the number of commodities. In essence we prove that up to constant factors the worst min-cut max-flow ratios appear in problems where demands are integral and polynomial in the number of commodities.Klein, Rao, Agrawal, and Ravi have previously proved that if the demands and the capacities are integral, then the min-cut max-flow ratio in general undirected graphs is bounded byO(logClogD), whereC denotes the sum of all the capacities. Tragoudas has improved this bound toO(lognlogD), wheren is the number of nodes in the network. Garg, Vazirani and Yannakakis further improved this toO(logklogD). Klein, Plotkin and Rao have proved that for planar networks, the ratio isO(logD).Our result improves the bound for general networks toO(log² k) and the bound for planar networks toO(logk). In both cases our result implies the first non-trivial bound that is independent of the magnitude of the numbers involved. The method presented in this paper can be used to give polynomial time approximation algorithms to the minimum cuts in the network up to the above factors.Preliminary version appeared in Proceedings of the 25th Annual ACM Symposium on the Theory of Computing, 1993, 691-697.Research supported by U.S. Army Research Office Grant DAAL-03-91-G-0102, and by a grant from Mitsubishi Electric Laboratories.Research supported in part by a Packard Fellowship, an NSF PYI award, a Sloan Fellowship, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.     

The Hardness of 3-Uniform Hypergraph Coloring

We prove that coloring a 3-uniform 2-colorable hypergraph with c colors is NP-hard for any constant c. The best known algorithm [20] colors such a graph using O(n^1/5) colors. Our result immediately implies that for any constants k ≥ 3 and c₂ > c₁ > 1, coloring a k-uniform c₁-colorable hypergraph with c₂ colors is NP-hard; the case k = 2, however, remains wide open. This is the first hardness result for approximately-coloring a 3-uniform hypergraph that is colorable with a constant number of colors. For k ≥ 4 such a result has been shown by [14], who also discussed the inherent difference between the k = 3 case and k ≥ 4. Our proof presents a new connection between the Long-Code and the Kneser graph, and relies on the high chromatic numbers of the Kneser graph [19,22] and the Schrijver graph [26]. We prove a certain maximization variant of the Kneser conjecture, namely that any coloring of the Kneser graph by fewer colors than its chromatic number, has ‘many’ non-monochromatic edges. * Research supported by NSF grant CCR-9987845. † Supported by an Alon Fellowship and by NSF grant CCR-9987845. ‡ Work supported in part by NSF grants CCF-9988526 and DMS 9729992, and the State of New Jersery.     

Text Indexing and Dictionary Matching with One Error

The indexing problem is where a text is preprocessed and subsequent queries of the form “Find all occurrences of pattern P in the text” are answered in time proportional to the length of the query and the number of occurrences. In the dictionary matching problem a set of patterns is preprocessed and subsequent queries of the form “Find all occurrences of dictionary patterns in text T” are answered in time proportional to the length of the text and the number of occurrences.There exist efficient worst-case solutions for the indexing problem and the dictionary matching problem, but none that find approximate occurrences of the patterns, i.e., where the pattern is within a bound edit (or Hamming) distance from the appropriate text location.In this paper we present a uniform deterministic solution to both the indexing and the general dictionary matching problem with one error. We preprocess the data in time O(n log² n), where n is the text size in the indexing problem and the dictionary size in the dictionary matching problem. Our query time for the indexing problem is O(m log n log log n + tocc), where m is the query string size and tocc is the number of occurrences. Our query time for the dictionary matching problem is O(n log³ d log log d + tocc), where n is the text size and d the dictionary size. The time bounds above apply to both bounded and unbounded alphabets.