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

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

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים

תקציר

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.

שפה מקוריתאנגלית
כותר פרסום המארח31st Conference on Computational Complexity, CCC 2016
עורכיםRan Raz
עמודים30:1-30:25
מסת"ב (אלקטרוני)9783959770088
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1 מאי 2016
אירוע31st Conference on Computational Complexity, CCC 2016 - Tokyo, יפן
משך הזמן: 29 מאי 20161 יוני 2016

סדרות פרסומים

שםLeibniz International Proceedings in Informatics, LIPIcs
כרך50

כנס

כנס31st Conference on Computational Complexity, CCC 2016
מדינה/אזוריפן
עירTokyo
תקופה29/05/161/06/16

ASJC Scopus subject areas

  • ???subjectarea.asjc.1700.1712???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Identity testing and lower bounds for read-k oblivious algebraic branching programs'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי