Date: May 21st
Time: 15:00 - 17:30

Center for ELC, Seminar room, Tokyo Tech. CIC 4F

* After the seminar, we will go out for dinner to some place.
  Please let me know if you want to join us.

===============
Speaker: Jacobo Toran (Univ. of Ulm)
Title: Graph Isomorphism is not AC_0 reducible to Group Isomorphism

Abstract:
We give a new upper bound for the Group and Quasigroup Isomorphism
problems when the input structures are given explicitly by
multiplication tables. We show that these problems can be computed by
polynomial size nondeterministic circuits of unbounded fan-in with O(log
log n) depth and O(log2 n) nondeterministic bits, where n is the number
of group elements. This improves the previously existing upper bound for
the problems. In the previous upper bound the circuits have bounded fan-
in but depth O(log2 n) and also O(log2 n) nondeterministic bits. We then
prove that the kind of circuits from our upper bound cannot compute the
Parity function. Since Parity is AC0 reducible to Graph Isomorphism,
this implies that Graph Isomorphism is strictly harder than Group or
Quasigroup Isomorphism under the ordering defined by AC0 reductions.

===============
Speaker: Jaikumar Radhakrishnan (Tata Institute of Fundamental Research)

Title: Set membership with two bit probes

Abstract:
We will consider the bit-probe complexity of the set membership
problem, where a set S of size at most n from a universe of size
m is to be represented as a short bit vector in order to answer
membership queries of the form ``Is x in S?'' by adaptively
probing the bit vector at t places. Let s(m,n,t) be the minimum
number of bits of storage needed for such a scheme. Alon and Feige
showed that for t=2 (two bit probes) such schemes can be obtained
from dense graphs with large girth. In particular, they showed that
for n < log m,

s(m,n,2) = O(m n log((log m) / n) / log m).

We improve their analysis and obtain a better upper bound and
a corresponding lower bound.

Upper bound: There is a constant C>0, such that for all large m,

s(m,n,2) <= C  m^{1-1/(4n+1)}.

Lower bound: There is a constant D>0, such that for n>=4 and all
large m, we have s(m,n,2) >= D  m^{1-{4}{n}}.

(This is joint work with Mohit Garg.)

END
Host: watanabe(at)is.titech.ac.jp