[Colloquium] REMINDER: Jimmy Qiao Talk Today

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Tuesday, April 13, 2010
Time: 3:00 p.m.
Place: Ryerson 251, 1100 E. 58th Street

----------------------------------------------------------

Speaker:	Jimmy Qiao

From:		Tsinghua University and University of Chicago

Website:		http://itcs.tsinghua.edu.cn/students/QiaoYM/index.html

Title: Pseudorandom Generators for Polynomial Identity Testing

Abstract: The polynomial identity testing problem (PIT) asks whether the polynomial computed by a given arithmetic circuit is identically zero. It ranks as one of the most important problems in the intersection of algebra and complexity, with many applications like deciding the existence of a perfect matching of a graph, primality testing and proving IP=PSPACE.

As Schwartz-Zipple lemma gives a randomized algorithm for PIT, the next goal is to devise a deterministic algorithm. However, Impagliazzo and Kabanets show that a deterministic algorithm for PIT is essentially equivalent to proving circuit lower bound. With the latter being considered difficult, a deterministic algorithm of PIT seems far from reach. But the other way around suggests that derandomizing PIT may be a way to go for circuit lower bound, and there is a formal program, proposed by Agrawal, of proving arithmetic circuit lower bound by devising strong enough pseudorandom generator for PIT.
Since the general problem may be very hard, current works have been concentrated on restricted models of arithmetic circuits, like sparse polynomials, depth-3 circuits and sum of k read-once formulas. To make progress towards general case, we consider skew circuits, that is the class of circuits in which every multiplication gate has at least one child labeled with a variable. It can be seen as an intermediate object between formula and circuit. We construct a generator for ordered read-k skew circuits, in which every variable appears at most k times as input. Ordered means that for every path from a leaf to the root, every variable appears once and the order is fixed. The idea of the generator is to consider the degree of the variety spanned by a certain set of polynomials, and try to escape from this variety by adding a small number of variables. This is joint work with Maurice Jansen and Jayalal Sarma. Then I will describe the algebraic NW generator by Kabanets and Impagliazzo, to show the construction of a conditional generator, which gives rise to some interesting open problems.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20100413/2a8fa5d7/attachment.htm