Now showing items 1-8 of 8

• #### Lower Bounds by Kolmogorov-Complexity ﻿

(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 ﻿

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

(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 ﻿

(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 ﻿

(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) ﻿

(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 ﻿

(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 ﻿

(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 ...