Campus Event Calendar
Event Entry
What and Who
Subexponential Size HItting Sets for Bounded Depth Multilinear Formulas
Ben Lee Volk/Amir Shpilka
Tel Aviv University
Talk
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 17 March 2015
09:30
60 Minutes
E2.1
001
Saarbrücken
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
Karteek Sreenivasaiah
--email hidden
passcode not visible
logged in users only
Karteek Sreenivasaiah, 03/12/2015 13:57 -- Created document.