[Colloquium] THEORY SEMINAR TODAY: Srikanth Srinivasan

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Tuesday, April 10, 2012
Time: 3:00 p.m.
Place: RY 251

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

Speaker:		Srikanth Srinivasan	

From:		IAS/Rutgers 

Web page:	http://dimacs.rutgers.edu/~srikanth/

Title: 		Pseudorandom Generators for Read-Once ACC^0

Abstract:		We consider the problem of constructing pseudorandom generators for read-once circuits. We give an explicit construction of a pseudorandom generator for the class of read-once $ACC^0$ circuits: constant depth circuits with unbounded fan-in AND, OR, NOT and generalized $MOD_m$ gates, where m is an arbitrary fixed constant. The seed length of our generator is poly-logarithmic in the number of variables and the error.
Joint work with Dmitry Gavinsky (NEC Laboratories America, Inc.) and Shachar Lovett (Institute of Advanced Study).


Refreshments will be served in Ryerson 255 before the talk at 2:30.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20120410/e2ae6ac3/attachment.htm