# DIMACS Seminar

## Title:

The Resolution of a Hartmanis Conjecture--Recent Progress on P-hard Sparse Sets

## Speaker:

- Jin-yi Cai
- Department of Computer Science
- SUNY - Buffalo

## Place:

- DIMACS Seminar Room 431, CoRE Building, Busch Campus
- Rutgers University

## Time:

- 10:30 AM (with a continuation after a break for lunch)
- Tuesday, June 6, 1995

## Abstract:

A set $S$ is called sparse if there are at most a polynomial
number of strings in $S$ up to length $n$.
Sparse sets have been the subject of study in complexity
theory for the past 20 years, as they reveal inherent
structure and limitations of computation.
For instance, it is well known that
the class of languages Cook reducible to a sparse set
is precisely the class of languages with polynomial size circuits.
Some fundamental results concerning the existence of
sparse sets hard for various classes:
Karp and Lipton proved that if a Turing hard sparse set
exists for NP, then the polynomial time hierarchy collapses
to its second level $\Sigma_2^p$. Mahaney showed that if
a sparse set exists which is hard for NP under many-one
reductions, then P = NP.
Hartmanis conjectured in 1978 that there are no sparse complete
sets for P under logspace many-one reductions.
We resolve this conjecture of Hartmanis.
The following theorem will be presented: If a P-hard sparse
set exists under logspace reductions, then P = LOGSPACE.
An interesting aspect of our work is that the techniques we employ
are probabilistic and algebraic in nature.

Following recent work by M. Ogihara, we first show that
if a sparse set exists for P under log-space reductions,
then $P = NC^2$. We will first give a randomized
construction that shows $P = {\cal R}NC^2$, under the given
hypothesis. Then we use techniques from finite field theory
to provide a deterministic construction. The techniques
are relavant to constructions of small sample spaces.

Then a string of improvements and ramifications to other
topics in complexity theory will be presented. The final
result collapses $P$ to $NC^1$. Our proofs for this final
stage uses more of finite field theory, error correcting codes,
and discrete Fourier transform. If time permit we will also
present other exciting development on the existence of
sparse sets hard for P under various weak reductions such
as bounded truth table reductions.

Supported by NSF grant CCR9319393 and CCR9057486, and
a Sloan fellowship. Joint work with D. Sivakumar of SUNY Buffalo.
And joint work with Ashish Naik and D. Sivakumar.

dimacs-www@dimacs.rutgers.edu
Document last modified on May 23, 1995