[Colloquium] Reminder: today's talk by Amir Shpilka at 11:00 a.m.

[Margery Ishmael]

UNIVERSITY OF CHICAGO, DEPARTMENT OF COMPUTER SCIENCE
THEORY SEMINAR

Date:  Thursday, March 25, 2004

Time:  11:00 a.m.

Place:  Ryerson 277

Speaker: Amir Shpilka (Weizmann Institute)

Title: Derandomizing Homomorphism Testing in General Groups
________________________________________________________

ABSTRACT

In this talk we will show a near optimal derandomization of the 
homomorphism test of Blum, Luby and Rubinfeld (BLR).

In particular we will show that for any function f:G->H
between two finite groups G,H and any expanding
generating set S of G, the natural derandomization of
BLR in which we pick random elements g in G and s in S
and test whether f(g)f(s)=f(gs), performs nearly as
well as the original test. Moreover we show that the
underlying homomorphism can be found by the natural
"belief propagation decoding".

If time permits we will show a polynomial time
construction of a relatively small (|G|^\epsilon)
generating set S for G, such that the Cayley graph of G
w.r.t. S is an expander. This follows a simple
derandomization of a result by Alon and Roichman who
showed that almost every set of size O(\log |G|) is
expanding.

This is a joint work with Avi Wigderson.

____________________________________________

The visitor's host is Laci Babai.