[Colloquium] [Staff] Theory Seminars at Computer Science

[Donna Brooms]

      **REMINDER**

COMPUTER SCIENCE

The University of Chicago

THEORY SEMINAR

_______________________

Date:	Tuesday, January 10, 2012

Time:	3 p.m.

Place:	Ryerson 251, 1100 E. 58th Street

______________________

Speaker:	YouMing (Jimmy) Qiao

From:		Institute for Theoretical Computer Science

Title:		Random Arithmetic Formulas can be Reconstructed Efficiently

Abstract:	 	In the reconstruction problem for a multivariate polynomial $f$, we have blackbox access to $f$ and the goal is to efficiently reconstruct a representation of $f$ in a suitable model of computation. We give a polynomial time randomized algorithm for reconstructing *random* arithmetic formulas. Our algorithm succeeds with high probability when given blackbox access to the polynomial computed by a random formula according to a natural distribution. Previous results on this problem considered models such as depth-3 circuits with various restrictions or read-once formulas, as well as multilinear depth-4 circuits with top fan-in 2, and random multilinear formulas (which Satya Lokam just talked about here). 

Our result then is the most natural model of arithmetic computation (e.g. without various constraints, notably without multilinear constraint) for which a reconstruction algorithm is presently known, albeit efficient in a distributional sense rather than in the worst case. The main technical work involved in devising the above algorithm is understanding and characterizing the high-dimensional components of the singular locus of an arbitrary linear combination of (a few) random formulas.

Joint work with Ankit Gupta and Neeraj Kayal. 

Refreshments will be served prior to the talk in Ryerson 255 @ 2:30 p.m.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20120110/730ff3d2/attachment.htm