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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 1 مايو 2016
الحدث31st Conference on Computational Complexity, CCC 2016 - Tokyo, اليابان
المدة: ٢٩ مايو ٢٠١٦١ يونيو ٢٠١٦

سلسلة المنشورات

الاسمLeibniz International Proceedings in Informatics, LIPIcs
مستوى الصوت50

!!Conference

!!Conference31st Conference on Computational Complexity, CCC 2016
الدولة/الإقليماليابان
المدينةTokyo
المدة٢٩/٠٥/١٦١/٠٦/١٦

All Science Journal Classification (ASJC) codes

  • !!Software

بصمة

أدرس بدقة موضوعات البحث “Identity testing and lower bounds for read-k oblivious algebraic branching programs'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا