[Colloquium] Grochow/MS Presentation/Nov. 4, 2008

[Margaret Jaffey]

This is an announcement of Joshua Grochow's MS Presentation.

----------------------------------------------------------------------------
Date:  Tuesday, November 4, 2008

Time:  11:00 a.m.

Place:  Ryerson 277

M.S. Candidate:  Joshua Grochow

M.S. Paper Title:  The Complexity of Equivalence Relations

Abstract:
To determine if two given lists of numbers are the same set, we would
sort both lists and see if we get the same result.  The sorted list is
a "canonical form" for the equivalence relation of set equality.
Other canonical forms for equivalences arise in graph isomorphism and
its variants, and the equality of permutation groups given by
generators.  To determine if two given graphs are cospectral, however,
we compute their spectra and see if they are the same set; the graph
spectrum is a "complete invariant" for the equivalence relation of
cospectrality.  This is weaker than a canonical form, and it is not
known whether a canonical form for cospectrality exists.  Note that it
is a priori possible for an equivalence relation to be decidable in
polynomial time without either a complete invariant or canonical form.

Blass and Gurevich ("Equivalence relations, invariants, and normal
forms, I and II", 1984) ask whether these conditions on equivalence
relations -- having an FP canonical form, having an FP complete
invariant, and simply being in P -- are in fact different.  They
showed that this question requires non-relativizing techniques to
resolve.  Here we extend their results using generic oracles, and give
new connections to probabilistic and quantum computation.

We denote the class of equivalence problems in P by PEq, the class of
problems with complete FP invariants Ker and the class with FP
canonical forms CF; CF is contained in Ker which is contained in PEq,
and we ask whether these inclusions are proper.  If an equivalence
relation R has the property that xRy implis |y| < poly(|x|), we say
that R is polynomially bounded; we denote the corresponding classes of
equivalence relation CF_p, Ker_p, and PEq_p.  Our main results are:

1. If CF=PEq then NP=UP=RP and thus PH=BPP;

2. If CF=Ker then NP=UP, PH=ZPP^{NP}, integers can be factored in
probabilistic polynomial time, and deterministic collision-free hash
functions do not exist;

3. If Ker=PEq then UP is contained in BQP;

4. There is an oracle relative to which CF, Ker, and PEq are all  
distinct

5. There are oracles relative to which CF_p = Ker_p, yet many-one
one-way functions exist, and Ker and PEq are distinct.

Attempting to generalize the third result above from UP to NP leads to
a new open question about the structure of witness sets for NP
problems (roughly: can the witness sets for an NP-complete problem
form an abelian group?).  We also introduce a natural notion of
reduction between equivalence problems, and present several open
questions about generalizations of these concepts to the polynomial
hierarchy, to logarithmic space, and to counting problems.

Advisor:  Prof. Laszlo Babai

A draft copy of Mr. Grochow's MS Paper is available in Ry 156.


=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Margaret P. Jaffey                             margaret at cs.uchicago.edu
Department of Computer Science
Student Support Rep (Ry 156)        (773) 702-6011
The University of Chicago                  http://www.cs.uchicago.edu
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=