Invited Speakers

The Complexity of Matrix Rank and Feasible Systems of Linear Equations

Eric Allender (Rutgers University), Robert Beals (Institute of Advanced Study), Mitsunori Ogihara (Univ of Rochester)

We consider the following problems:

\hspace*{\fill}{\it Ver.RANK} $= \{(A,r) : A \in {\bf Z}^{n \times n}, r \in {\bf N}, \mbox{rank}(A) = r\}$.\hspace*{\fill}

\hspace*{\fill}{\it Comp.RANK} $= \{(A,i,b) : A \in {\bf Z}^{n \times n}, \mbox{rank}(A)=r,\ \mbox{and bit number}\ i\ \mbox{of}\ r\ \mbox{is}\ b\}$ \hspace*{\fill}

\hspace*{\fill}{\it FSLE} $= \{(A,\vec{b}) : A \in {\bf Z}^{n \times n}, \vec{b} \in {\bf Z}^{n\times 1}, \exists X \in {\bf Q}^{n\times 1} : AX = \vec{b}\}$.\hspace*{\fill}

We show that {\it FSLE} and {\em Comp.RANK} are complete for L(C$_=$L) (Equivalently, this is the class of languages logspace-Turing reducible to the set of singular matrices.) Also, we show that {\it Ver.RANK} is complete for the second level of the Boolean Hierarchy above C$_=$L. If C$_=$L is closed under complement, then all of these classes collapse to C$_=$L. One of our main results is the collapse of the C$_=$L hierarchy:

\hspace*{\fill}L$^{{\rm C}_={\rm L}} \subseteq$ NL$^{{\rm C}_={\rm L}} \subseteq$ C$_=$L$^{{\rm C}_={\rm L}} \subseteq$ C$_=$L$^{{\rm C}_={\rm L}^{{\rm C}_={\rm L}}}\subseteq \ldots$\hspace*{\fill}

Jay Belanger (Northeast Missouri State University)

Levin (1986) initiated the study of average-case completeness and defined a robust notion of average-case complexity. A sound theory of average-case completeness has been developed and a number of average-case NP-complete problems have been shown. Levin's definition concerns only what is easy on average and what is not. To make finer distinctions, a generalization of Levin's definition was proposed by Ben-David et. al. (1992), which, however, has some counter-intuitive consequences from a structural point of view. Other definitions of average time which don't have these consequences have been proposed, but which have been shown to lack certain properties of the Levin/Ben-David et. al. definition. So it makes sense to investigate structural properties of the Levin/Ben-David et. al. definition, and we will discuss hierarchies (and limits to their fineness) among the resulting complexity classes.

Ronald V. Book (University of California, Santa Barbara)

There are certain simple conditions that make a reducibility R appropriate. For any appropriate R, define almost-R to be {A|Prob{B|A \in R(B)} = 1}. Book, Lutz and Wagner showed that for appropriate R, almost-R = R(RAND)\cap REC, where REC denotes the class of all recursive sets and RAND denotes the class of algorithmically random languages. This leads to the following:

Hartmanis conjectured in 1978 that there are no sparse complete sets for P under logspace many-one reductions, unless P=LOGSPACE. Following a breakthrough by Ogihara, we resolve this conjecture of Hartmanis in the affirmative.

This talk will summarize the results on the bounded query complexity of NP-approximation problems. For several NP-approximation problems (e.g., Maximum Clique, Maximum Satisfiability and Graph Coloring), studies have shown a very tight connection between the complexity of approximating the problem and bounded query classes. Approximate solutions to these problems can be found using queries to an NP oracle. In addition, functions computable using queries to an NP oracle can be reduced to these approximation problems. These results also provide a quantitative link between the number of queries and closeness of approximations. Thus, bounded query classes provide a natural complexity measure for NP-approximation problems.

We address the possibility that all polynomial-time computable, honest, onto functions are invertible in polynomial time. This is the dual of the statement that all one-to-one p-time functions are invertible, which was shown by Grollmann and Selman to be equivalent to P = UP. The current statement, which we call Q, is shown to have a number of interesting equivalent formulations. For example, Q is equivalent to tautological search as defined by Impagliazzo and Naor. We show that Q is equivalent to the following: for every NP machine $M$ that accepts SAT, there is a p-time function mapping accepting paths of $M$ to satisfying assignments of the input. As a corollary, if Q holds, then Karp's notion of many-one completeness is equivalent to Levin's notion of universal search problems.

A set $S\subseteq \{0,1\}^n$ is defined to be {\em linearly restrictable} if $\sum_{x\in S} x \neq 0^n$. This is a generalization of the concept of {\em linear independence}.

Given an arbitrary set of $n$-bit vectors, it is possible to construct, with a constant probability, a probabilistic subset that is linearly restrictable. Given a linearly restrictable set, it is easy to construct a probabilistic subset that has an odd number of elements. These two constructions can then be used together to prove Toda's theorem that the polynomial-time hierarchy ``collapses'' to $\oplus P$ with a high probability.

Interestingly, Toda's theorem can be proved directly using linearly restrictable sets. The ``high probability part'' in Toda's result naturally corresponds to the generation of linearly restrictable sets from arbitrary witness sets; linearly restrictable sets can be easily ``collapsed'' to $\oplus P$.

A decade and a half ago, Selman introduced semi-feasible computation, a complexity-theoretic analog of Jockusch's semirecursive sets. In particular, a set L is semi-feasible if there is a deterministic polynomial-time function f(.,.) such that, for all x and y, (a) f(x,y) = x or f(x,y)=y, and (b) {x, y} \cap L \neq \emptyset \Longleftrightarrow f(x,y) \in L. Semi-feasible computation captures the complexity of left cuts of real numbers.

More recently, nondeterministic analogs of semi-feasible computation have been studied. In particular, L. Hemaspaandra, A. Hoene, A. Naik, M. Ogihara, A. Selman, T. Thierauf, and J. Wang introduced and studied NP-selectivity, and L. Hemaspaandra, A. Naik, M. Ogihara, and A. Selman have studied nondeterministic selectivity with respect to partial functions.

We prove that tree isomorphism is not expressible in the language (FO +TC + COUNT). This is surprising since in the presence of ordering the language captures NSPACE[log n], whereas tree isomorphism and canonization are in DSPACE[log n]. Our proof uses an Ehrenfeucht-Fra\"{\i}ss\'{e} game for transitive closure logic with counting.

As a corresponding upper bound, we show that tree canonization is expressible in (FO + COUNT)[log n]. The lower bound remains true for bounded-degree trees, and we show that for bounded-degree trees counting is not needed in the upper bound. These results are the first separations of the unordered versions of the logical languages for NSPACE[log n], AC^1, and ThC^1.

Assuming that $k \geq 2$ and $\Delta^P_k$ does not have p-measure 0, it is shown that $BP \cdot \Delta^P_k = \Delta^P_k$. This implies that the following conditions hold if $\Delta^P_2$ does not have p-measure 0.

1. $AM \cap co-AM$ is low for $\Delta^P_2$. (Thus $BPP$ and the graph isomorphism problem are low for $\Delta^P_2$.)
2. If $\Delta^p_2 \neq PH$, then $NP$ does not have polynomial-size circuits.

Error-correcting codes are used to improve the Valiant-Vazirani randomized reduction from NP to parity, which has been used in several important results in complexity theory. The running time, success probability, and number of random bits are all improved by an order of magnitude over VV, and the codes beat both the $2n$ random bits and time/success tradeoff in previous improvements to VV based on universal hashing. The theorem of Wigderson that NL/poly $\subseteq$ $\oplus$L/poly, from the 1994 IEEE Structure in Complexity Theory conference, falls out of the same construction.

Questions of further improvements are connected to open problems in the theory of error-correcting codes. This talk will also discuss other applications of codes in complexity theory.

We extend Levin's theory of average polynomial time to arbitrary time-bounds in accordance with the following general principles: (1) It essentially agrees with Levin's notion when applied to polynomial time-bounds. (2) If a language $L$ belongs to DTIME($T(n)$), for some time-bound $T(n)$, then every distributional problem $(L,\mu)$ is $T$ on the $\mu$-average. (3) If $L$ does not belong to DTIME($T(n)$) {\it almost everywhere}, then no distributional problem $(L,\mu)$ is $T$ on the $\mu$-average.

We present a hierarchy theorem for average-case complexity, for arbitrary time-bounds, that is as tight as the well-known Hartmanis-Stearns (J. Hartmanis and R. Stearns, On the computational complexity of algorithms, {\em Trans. Amer. Math. Soc.}, 117:285--306, 1965) hierarchy theorem for deterministic complexity. As a consequence, for every time-bound $T(n)$, there are distributional problems $(L,\mu)$ that can be solved using only a slight increase in time but that cannot be solved on the $\mu$-average in time $T(n)$.

We demonstrate that our definition is natural and is as justified for arbitrary time-bounds as is Levin's definition for polynomial time-bounds. We critique an earlier proposal of a definition of average case complexity for arbitrary time-bounds (S.~Ben-David, B.~Chor, O.~Goldreich, and M.~Luby, On the theory of average case complexity, {\em J. Computer System Sci.}, 44(2):193--219, 1992) by demonstrating that it does not satisfy our general principles. Nevertheless, we obtain a fine hierarchy, for the earlier definition, for distributional problems whose running time is bounded by a polynomial.

Recently, ``average-case complexity'' has received considerable attention in several fields of computer science. Even if a problem is not (or may not be) solvable efficiently in the worst-case, it may be solvable efficiently on average. In this talk, we begin with such examples, and introduce some mathematical framework for investigating average-case computational complexity of problems.

The Sheraton Greensboro Hotel & Conference Center is located minutes from I-85 and I-40 in the middle of the business district and downtown. It is 12 miles from the Piedmont Triad International Airport (Greensboro). Coming from the airport take Highway 68 to I-40 east, taking a right onto Wendover Avenue East to the Market Street exit and bear right, then left on Eugene St., right on Smith St. then right on Greene St. The Hotel entrance will be on the left just past the intersection of Greene and Lindsay Sts.

Participants traveling by car from the north or south: take US 29 to the Cone Blvd. exit heading west, turn left on Elm St. (towards downtown), turn onto Lindsay St. then left onto Greene and the hotel entrance is on the left.

East or west: take either I-85 or I-40 towards Greensboro and then take the South Elm exit. Follow South Elm-Eugene St. into the downtown area, take a right off Eugene St. onto Smith St. (go one block), turn right on Greene St., hotel entrance is on the left.