Now showing items 1-8 of 8

    • Lower Bounds by Kolmogorov-Complexity 

      Li, Ming (Cornell University, 1985-03)
      Using Kolmogorov-complexity, we obtain the following new lower bounds. For on-line nondeterministic Turing machines, (1) simulating 2 pushdown stores by 1 tape requires $\Omega(n^{1.5} / logn)$ time; together with a newly ...
    • Lower bounds in Computational Complexity 

      Li, Ming (Cornell University, 1985-03)
      No abstract available
    • Lower Bounds on String-Matching 

      Li, Ming (Cornell University, 1984-09)
      New techniques for obtaining lower bounds on string-matching problems are developed and we prove the following new results. String-matching cannot be performed by a three-head one-way deterministic finite automaton. This ...
    • On One Tape Versus Two Stacks 

      Li, Ming (Cornell University, 1984-01)
      We develop a simple method which enables us to prove three new lower bounds (for both worst and average cases) for on-line computations, answering two open problems summarized in [DGPR]. We give a language that requires ...
    • On the Duality of Intersections and Closest Points 

      Bajaj, Chanderjit; Li, Ming (Cornell University, 1983-08)
      We call the common intersection of $k$ objects a $k$-intersection. We address questions of the form: Given $n$ objects in the plane, "Does there exist a $k$-intersection?", "How many such $k$-intersections exist?" and ...
    • Simulating Two Pushdown Stores by One Tape in $O(n^{1.5}\sqrt{logn}$) Time. (Preliminary Version) 

      Li, Ming (Cornell University, 1985-03)
      Based on two graph separator theorems, one old (the Lipton-Tarjan planar separator theorem) and one new, we present two unexpected upper bounds and resolve several open problems for on-line computations: (1) 1 tape ...
    • Single Molecule Studies Of Chromatin Dynamics And Transcription Coupled Repair 

      Li, Ming (2016-02-01)
      Biological systems create designs that respond to the need to perform specific functions. In particular, protein-DNA complexes form unique structures to maintain the stability of genetic information and yet the dynamics ...
    • String-Matching Cannot be Done by a Two-Head One-Way Deterministic Finite Automaton 

      Li, Ming; Yesha, Yaacov (Cornell University, 1983-10)
      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 ...