Identity testing and lower bounds for read-k oblivious algebraic branching programs

Matthew Anderson; Michael A. Forbes; Ramprasad Saptharishi; Amir Shpilka; Ben Lee Volk

doi:10.4230/LIPIcs.CCC.2016.30

Identity testing and lower bounds for read-k oblivious algebraic branching programs

Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Read-k oblivious algebraic branching programs are a natural generalization of the well-studied model of read-once oblivious algebraic branching program (ROABPs). In this work, we give an exponential lower bound of exp(n/kO(k)) on the width of any read-k oblivious ABP computing some explicit multilinear polynomial f that is computed by a polynomial size depth-3 circuit. We also study the polynomial identity testing (PIT) problem for this model and obtain a white-box subexponential-time PIT algorithm. The algorithm runs in time 2∼O(n1-1/2k-1 ) and needs white box access only to know the order in which the variables appear in the ABP.

Original language	English (US)
Title of host publication	31st Conference on Computational Complexity, CCC 2016
Editors	Ran Raz
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages	30:1-30:25
ISBN (Electronic)	9783959770088
DOIs	https://doi.org/10.4230/LIPIcs.CCC.2016.30
State	Published - May 1 2016
Externally published	Yes
Event	31st Conference on Computational Complexity, CCC 2016 - Tokyo, Japan Duration: May 29 2016 → Jun 1 2016

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	50
ISSN (Print)	1868-8969

Other

Other	31st Conference on Computational Complexity, CCC 2016
Country/Territory	Japan
City	Tokyo
Period	5/29/16 → 6/1/16

Keywords

Algebraic complexity
Derandomization
Lower bounds
Polynomial identity testing

ASJC Scopus subject areas

Software

Online availability

10.4230/LIPIcs.CCC.2016.30

Library availability

Discover UIUC Full Text

Cite this

Anderson, M., Forbes, M. A., Saptharishi, R., Shpilka, A., & Volk, B. L. (2016). Identity testing and lower bounds for read-k oblivious algebraic branching programs. In R. Raz (Ed.), 31st Conference on Computational Complexity, CCC 2016 (pp. 30:1-30:25). (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 50). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.CCC.2016.30

Identity testing and lower bounds for read-k oblivious algebraic branching programs. / Anderson, Matthew; Forbes, Michael A.; Saptharishi, Ramprasad et al.
31st Conference on Computational Complexity, CCC 2016. ed. / Ran Raz. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016. p. 30:1-30:25 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 50).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Anderson, M, Forbes, MA, Saptharishi, R, Shpilka, A & Volk, BL 2016, Identity testing and lower bounds for read-k oblivious algebraic branching programs. in R Raz (ed.), 31st Conference on Computational Complexity, CCC 2016. Leibniz International Proceedings in Informatics, LIPIcs, vol. 50, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, pp. 30:1-30:25, 31st Conference on Computational Complexity, CCC 2016, Tokyo, Japan, 5/29/16. https://doi.org/10.4230/LIPIcs.CCC.2016.30

Anderson M, Forbes MA, Saptharishi R, Shpilka A, Volk BL. Identity testing and lower bounds for read-k oblivious algebraic branching programs. In Raz R, editor, 31st Conference on Computational Complexity, CCC 2016. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2016. p. 30:1-30:25. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.CCC.2016.30

Anderson, Matthew ; Forbes, Michael A. ; Saptharishi, Ramprasad et al. / Identity testing and lower bounds for read-k oblivious algebraic branching programs. 31st Conference on Computational Complexity, CCC 2016. editor / Ran Raz. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016. pp. 30:1-30:25 (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{1661c2f4b1c845f994877bb1d45a1f6a,

title = "Identity testing and lower bounds for read-k oblivious algebraic branching programs",

abstract = "Read-k oblivious algebraic branching programs are a natural generalization of the well-studied model of read-once oblivious algebraic branching program (ROABPs). In this work, we give an exponential lower bound of exp(n/kO(k)) on the width of any read-k oblivious ABP computing some explicit multilinear polynomial f that is computed by a polynomial size depth-3 circuit. We also study the polynomial identity testing (PIT) problem for this model and obtain a white-box subexponential-time PIT algorithm. The algorithm runs in time 2∼O(n1-1/2k-1 ) and needs white box access only to know the order in which the variables appear in the ABP.",

keywords = "Algebraic complexity, Derandomization, Lower bounds, Polynomial identity testing",

author = "Matthew Anderson and Forbes, {Michael A.} and Ramprasad Saptharishi and Amir Shpilka and Volk, {Ben Lee}",

note = "Publisher Copyright: {\textcopyright} Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi,Amir Shpilka, and Ben Lee Volk.; 31st Conference on Computational Complexity, CCC 2016 ; Conference date: 29-05-2016 Through 01-06-2016",

year = "2016",

month = may,

day = "1",

doi = "10.4230/LIPIcs.CCC.2016.30",

language = "English (US)",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

pages = "30:1--30:25",

editor = "Ran Raz",

booktitle = "31st Conference on Computational Complexity, CCC 2016",

}

TY - GEN

T1 - Identity testing and lower bounds for read-k oblivious algebraic branching programs

AU - Anderson, Matthew

AU - Forbes, Michael A.

AU - Saptharishi, Ramprasad

AU - Shpilka, Amir

AU - Volk, Ben Lee

PY - 2016/5/1

Y1 - 2016/5/1

N2 - Read-k oblivious algebraic branching programs are a natural generalization of the well-studied model of read-once oblivious algebraic branching program (ROABPs). In this work, we give an exponential lower bound of exp(n/kO(k)) on the width of any read-k oblivious ABP computing some explicit multilinear polynomial f that is computed by a polynomial size depth-3 circuit. We also study the polynomial identity testing (PIT) problem for this model and obtain a white-box subexponential-time PIT algorithm. The algorithm runs in time 2∼O(n1-1/2k-1 ) and needs white box access only to know the order in which the variables appear in the ABP.

AB - Read-k oblivious algebraic branching programs are a natural generalization of the well-studied model of read-once oblivious algebraic branching program (ROABPs). In this work, we give an exponential lower bound of exp(n/kO(k)) on the width of any read-k oblivious ABP computing some explicit multilinear polynomial f that is computed by a polynomial size depth-3 circuit. We also study the polynomial identity testing (PIT) problem for this model and obtain a white-box subexponential-time PIT algorithm. The algorithm runs in time 2∼O(n1-1/2k-1 ) and needs white box access only to know the order in which the variables appear in the ABP.

KW - Algebraic complexity

KW - Derandomization

KW - Lower bounds

KW - Polynomial identity testing

UR - http://www.scopus.com/inward/record.url?scp=84973308378&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84973308378&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.CCC.2016.30

DO - 10.4230/LIPIcs.CCC.2016.30

M3 - Conference contribution

AN - SCOPUS:84973308378

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 30:1-30:25

BT - 31st Conference on Computational Complexity, CCC 2016

A2 - Raz, Ran

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 31st Conference on Computational Complexity, CCC 2016

Y2 - 29 May 2016 through 1 June 2016

ER -

Identity testing and lower bounds for read-k oblivious algebraic branching programs

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this