Oliveira, Rafael ;
Shpilka, Amir ;
Volk, Ben Lee
Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas
Abstract
In this paper we give subexponential size hitting sets for bounded depth multilinear arithmetic formulas. Using the known relation
between blackbox PIT and lower bounds we obtain lower bounds for these models.
For depth3 multilinear formulas, of size exp(n^delta), we give a hitting set of size exp(~O(n^(2/3 + 2*delta/3))). This implies a lower bound of exp(~Omega(n^(1/2))) for depth3 multilinear formulas, for some explicit polynomial.
For depth4 multilinear formulas, of size exp(n^delta), we give a hitting set of size exp(~O(n^(2/3 + 4*delta/3)). This implies a lower bound of exp(~Omega(n^(1/4))) for depth4 multilinear formulas, for some explicit polynomial.
A regular formula consists of alternating layers of +,* gates, where all gates at layer i have the same fanin. We give a
hitting set of size (roughly) exp(n^(1delta)), for regular depthd multilinear formulas of size exp(n^delta), where delta = O(1/sqrt(5)^d)). This result implies a lower bound of roughly exp(~Omega(n^(1/sqrt(5)^d))) for such formulas.
We note that better lower bounds are known for these models, but also that none of these bounds was achieved via construction of
a hitting set. Moreover, no lower bound that implies such PIT results, even in the whitebox model, is currently known.
Our results are combinatorial in nature and rely on reducing the underlying formula, first to a depth4 formula, and then to a
readonce algebraic branching program (from depth3 formulas we go straight to readonce algebraic branching programs).
BibTeX  Entry
@InProceedings{oliveira_et_al:LIPIcs:2015:5054,
author = {Rafael Oliveira and Amir Shpilka and Ben Lee Volk},
title = {{Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas}},
booktitle = {30th Conference on Computational Complexity (CCC 2015)},
pages = {304322},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897811},
ISSN = {18688969},
year = {2015},
volume = {33},
editor = {David Zuckerman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5054},
URN = {urn:nbn:de:0030drops50548},
doi = {10.4230/LIPIcs.CCC.2015.304},
annote = {Keywords: Arithmetic Circuits, Derandomization, Polynomial Identity Testing}
}
2015
Keywords: 

Arithmetic Circuits, Derandomization, Polynomial Identity Testing 
Seminar: 

30th Conference on Computational Complexity (CCC 2015)

Issue date: 

2015 
Date of publication: 

2015 