Tata Institute of Fundamental Research
Fighting Boolean Circuits: New Correlation Bounds and Pseudorandom Generators
Seminar
Speaker:
Srikanth Srinivasan
Rutgers University
DIMACS
New Brunswick
New Jersey
United States of America
Organiser:
John Barretto
Date:
Wednesday, 4 Jan 2012, 11:30 to 12:30
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
The general problem of proving limitations on what efficient algorithms can accomplish has been the subject of much research over the past four decades. In this talk, we consider the specific question of bounding the power of Boolean circuits. We discuss three generic questions: those of proving lower bounds, correlation bounds, and constructing Pseudorandom generators (PRGs) for different classes of Boolean circuits. We look at the major results in these directions and the important questions that need to be tackled next.
In the process, we motivate the question of proving correlation bounds and constructing PRGs for bounded-depth circuits. We then describe our own results: correlation bounds for AC^0 with a few symmetric gates, and explicit PRGs against read-once ACC^0 (this is joint work with Shachar Lovett (IAS, Princeton) and Dmitry Gavinsky (NEC Research Labs, Princeton)).
| Speaker: | Srikanth Srinivasan Rutgers University DIMACS New Brunswick New Jersey United States of America |
| Organiser: | John Barretto |
| Date: | Wednesday, 4 Jan 2012, 11:30 to 12:30 |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
The general problem of proving limitations on what efficient algorithms can accomplish has been the subject of much research over the past four decades. In this talk, we consider the specific question of bounding the power of Boolean circuits. We discuss three generic questions: those of proving lower bounds, correlation bounds, and constructing Pseudorandom generators (PRGs) for different classes of Boolean circuits. We look at the major results in these directions and the important questions that need to be tackled next.
In the process, we motivate the question of proving correlation bounds and constructing PRGs for bounded-depth circuits. We then describe our own results: correlation bounds for AC^0 with a few symmetric gates, and explicit PRGs against read-once ACC^0 (this is joint work with Shachar Lovett (IAS, Princeton) and Dmitry Gavinsky (NEC Research Labs, Princeton)).
In the process, we motivate the question of proving correlation bounds and constructing PRGs for bounded-depth circuits. We then describe our own results: correlation bounds for AC^0 with a few symmetric gates, and explicit PRGs against read-once ACC^0 (this is joint work with Shachar Lovett (IAS, Princeton) and Dmitry Gavinsky (NEC Research Labs, Princeton)).