Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Approaching the chasm at depth four
Speaker:Michael Forbes
coming from:Massachusetts Institute of Technology
Speakers Bio:
Event Type:Talk
Visibility:D1, D2, D3, D4, D5, SWS, RG1, MMCI
We use this to send out email in the morning.
Level:Expert Audience
Date, Time and Location
Date:Tuesday, 25 March 2014
Duration:180 Minutes
Building:E2 1 - Bioinformatik
Contributed Talks

Michael Forbes, Massachusetts Institute of Technology
Hitting Sets for Multilinear Read-Once Algebraic Branching Programs, in any Order

It is an important open question whether we can derandomize small space computation, that is, whether RL equals L. One version of this question is to construct pseudorandom generators for read-once oblivious branching programs. There are well-known results in this area (due to Nisan, and Impagliazzo-Nisan-Wigderson), but they fail to achieve optimal seed-length. Further, it has been observed that these pseudorandom generators depend strongly on the "order" of the "reads" of the branching program. When this order is allowed to vary, only much weaker results are known.

In this work, we consider an "algebraic" version of this question. That is, we seek to fool read-once algebraic branching programs, regardless of the variable order. By rephrasing and improving the techniques of Agrawal-Saha-Saxena, we are able to construct hitting sets for multilinear polynomials in this unknown-order model that have polylogarithmic "seed-length". This constitutes the first quasipolynomial-time, deterministic, black-box polynomial identity testing (PIT) algorithm for this model.

Joint work with Ramprasad Saptharishi (MSR India) and Amir Shpilka (Technion).

Ankit Gupta, Chennai Mathematical Institute
Approaching the chasm at depth four

Agrawal-Vinay'08 and Koiran'12 have recently shown that an exp(n1/2+ϵ) lower bound for depth four homogeneous circuits computing the permanent with bottom layer of x gates having fanin bounded by n1/2 translates to exp(nϵ)lower bound for general arithmetic circuits computing the permanent. Motivated by this, we examine the complexity of computing the permanent via such restricted homogeneous depth four circuits.

We show here that any homogeneous depth four arithmetic circuit with bottom fanin bounded by n1/2 computing the permanent must be of size exp(Ω(n1/2)).

(joint work with Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi)

Name(s):Markus Bläser
EMail:--email address not disclosed on the web
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Christine Kiesel, 03/20/2014 09:16 AM
  • Christine Kiesel, 03/19/2014 04:45 PM
  • Christine Kiesel, 03/19/2014 04:36 PM -- Created document.