[Colloquium] [Staff] Theory Seminars at Computer Science

[Donna Brooms]

    ~REMINDER~

COMPUTER SCIENCE

The University of Chicago

THEORY SEMINAR

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

Date:	Thursday, October 20th

Time:	3:15 p.m.

Place:	Ryerson 251, 1100 E. 58th Street

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

Speaker:	Satya V. Lokam

From:		Microsoft Research, India

Title:		Title: "Efficient Reconstruction of Random Multilinear Formulas."
 

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* multilinear formulas. Our algorithm succeeds with high probability when given blackbox access to the polynomial computed by a random multilinear formula according to a natural distribution. This is the strongest model of computation for which a reconstruction algorithm is presently known, albeit efficient in a distributional sense rather than in the worst-case. Previous results on this problem considered much weaker models such as depth-3 circuits with various restrictions or read-once formulas.

Our proof uses rank of partial derivative matrices as a key ingredient and combines it with analysis of the algebraic structure of random multilinear formulas. Partial derivative matrices have earlier been used to prove lower bounds in a number of models of arithmetic complexity, including multilinear formulas and constant depth circuits. As such, our results give supporting evidence to the general thesis that mathematical properties that capture efficient computation in a model should also enable learning algorithms for functions efficiently computable in that model.


Joint work with Ankit Gupta and Neeraj Kayal and based on a FOCS 2011 paper.


 Host: Laci Babai (Satya's former advisor)

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

*Refreshments will be served before the talk at 3pm in Ryerson 255*

Persons who need assistance should call 773-702-6614


-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20111020/5eaaf4ed/attachment.htm