Identity Testing and Lower Bounds for Read-k Oblivious Algebraic\n Branching Programs

2015/11/23 by Matthew Anderson, Anderson, Matthew, Michael A. Forbes +7 · 1 citation
Computer Science · #Advanced Data Storage Technologies #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.1511.07136

openalex publication_date 2015/11/23 · openalex created_date 2022/10/04 · openalex updated_date 2026/07/28

Abstract

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

Cited by

• On Closure Properties of Read-Once Oblivious Algebraic Branching Programs

Related

• Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order
• Deterministic Identity Testing for Sum of Read-Once Oblivious Arithmetic\n Branching Programs
• Hitting-sets for ROABP and Sum of Set-Multilinear circuits
• Deterministic Identity Testing of Read-Once Algebraic Branching Programs
• Deterministic Black-Box Identity Testing π-Ordered Algebraic Branching Programs