3 papers
cs.CC2001
Two heads are better than two tapes
Tao Jiang, Joel Seiferas, Paul Vitanyi
We show that a Turing machine with two single-head one-dimensional tapes cannot recognize the set {x2x'| x \in {0,1}^* and x' is a prefix of x} in real time, although it can do so…
math.CO1999
The Average-Case Area of Heilbronn-Type Triangles
Tao Jiang, Ming Li, Paul Vitanyi
From among triangles with vertices chosen from points in the unit square, let be the one with the smallest area, and let be the area of . Heilbronn'…
cs.DS1999
Average-Case Complexity of Shellsort
Tao Jiang, Ming Li, Paul Vitanyi
We prove a general lower bound on the average-case complexity of Shellsort: the average number of data-movements (and comparisons) made by a -pass Shellsort for any incremental…