Max-Planck-Institut für Informatik
max planck institut
informatik
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:Subexponential Size HItting Sets for Bounded Depth Multilinear Formulas
Speaker:Ben Lee Volk/Amir Shpilka
coming from:Tel Aviv University
Speakers Bio:
Event Type:Talk
Visibility:D1
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Tuesday, 17 March 2015
Time:09:30
Duration:60 Minutes
Location:Saarbr├╝cken
Building:E2.1
Room:001
Abstract
We give subexponential size hitting sets for bounded depth multilinear arithmetic formulas. Using the known relation between black-box PIT and lower bounds we obtain lower bounds for these models.

Our results are combinatorial in nature and rely on reducing the underlying formula, first to a depth-4 formula, and then to a read-once algebraic branching program (from depth-3 formulas we go straight to read-once algebraic branching programs).

Based on a joint work with Rafael Mendes de Oliveira and Ben Lee Volk

Contact
Name(s):Karteek Sreenivasaiah
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):

Created by:Karteek Sreenivasaiah, 03/12/2015 01:57 PMLast modified by:Uwe Brahm/MPII/DE, 03/17/2015 04:01 AM
  • Karteek Sreenivasaiah, 03/12/2015 01:57 PM -- Created document.