- Circuits with Medium Fan-In
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in April 2014
Circuits with Medium Fan-In
Speaker:
Anup Rao
, University of Washington
Date: Tuesday, April 15, 2014
Time: 4:15 PM to 5:15 PM Note: all times are in the Eastern Time Zone
Refreshments: 3:45 PM
Public: Yes
Location: 32-G449
Event Type:
Room Description:
Host: Ankur Moitra, CIS, TOC, CSAIL, MIT
Contact: Holly A Jones, hjones01@csail.mit.edu
Relevant URL: http://toc.csail.mit.edu/node/486
Speaker URL: None
Speaker Photo:
None
Reminders to:
seminars@csail.mit.edu, theory-seminars@csail.mit.edu, toc@csail.mit.edu
Reminder Subject:
TALK: Circuits with Medium Fan-In
Abstract:
We consider boolean circuits in which every gate may compute an arbitrary boolean function of k other gates, for a parameter k. We give an explicit function f:{0,1}^n to {0,1} that requires at least Omega(log^2 n) non-input gates when k = 2n/3. When the circuit is restricted to being layered and depth 2, we prove a lower bound of n^{Omega(1)} on the number of non-input gates. When the circuit is a formula with gates of fan-in k, we give a lower bound Omega(n^2/k \log n) on the total number of gates.
Our model is connected to some well known approaches to proving lower bounds in complexity theory. Optimal lower bounds for the Number-On-Forehead model in communication complexity, or for bounded depth circuits in AC_0, or extractors for varieties over small fields would imply strong lower bounds in our model. On the other hand, new lower bounds for our model would prove new time-space tradeoffs for branching programs and impossibility results for (fan-in 2) circuits with linear size and logarithmic depth. In particular, our lower bound gives a different proof for a known time-space tradeoff for oblivious branching programs.
Joint work with Pavel Hrubes.
Research Areas:
Impact Areas:
Created by Holly A Jones 
at Friday, April 04, 2014 at 2:09 PM.