We also saw a series of presentations by Andris Ambainis, Robert
Špalek and Mario Szegedy. Ambainis described his improved method
for showing lower bounds for quantum algorithms that provably beats
the degree method. Špalek talked about his work with
Szegedy showing that Ambainis techniques as well as different tools
developed by Zhang, Laplante and Magniez, and Barnum, Saks and Szegedy
all gave the same bounds. Szegedy, in his presentation, called this
measure the *div complexity* and showed that the size of a
Boolean formula computing a function f is at least the square of the
div complexity of f.

## Saturday, October 16, 2004

### Some Dagstuhl Presentations

At Dagstuhl Manindra Agrawal presented recent work of his students
Neeraj Kayal and Nitin Saxena (the trio that showed a polynomial-time
algorithm for primality testing) on rings given by a matrix describing
the actions on the base elements. They show a randomized reduction
from graph isomorphism to ring isomorphism and from factoring to #RI,
counting the number of ring isomorphisms. They also show a
polynomial-time algorithm for determining if there are any non-trivial
automorphisms of a ring and that #RI is computable with an oracle for
AM∩co-AM. Agrawal conjectured that #RI is computable in polynomial
time, a conjecture that would imply factoring and graph isomorphism
have efficient algorithms.

## No comments:

## Post a Comment