Identity Testing and Lower Bounds for Read- k Oblivious Algebraic Branching Programs
Copyright policy )Identity Testing and Lower Bounds for Read- k Oblivious Algebraic Branching Programs
Read- k oblivious algebraic branching programs are a natural generalization of the well-studied model of read-once oblivious algebraic branching program (ABP). In this work, we give an exponential lower bound of exp ( n/k O ( 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 Õ( n 1−1/2 k −1 ) and needs white box access only to know the order in which the variables appear in the ABP.
- University of Illinois at Urbana Champaign United States
- College of New Jersey United States
- King’s University United States
- Tel Aviv University Israel
- Department of Computer Science Princeton University United States
FOS: Computer and information sciences, Lower Bounds, algebraic circuits, polynomial identity testing, Networks and circuits as models of computation; circuit complexity, Computational Complexity (cs.CC), 004, lower bounds, Computer Science - Computational Complexity, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), Analysis of algorithms, Derandomization, algebraic complexity theory, Algebraic Complexity, Polynomial Identity Testing, ddc: ddc:004
FOS: Computer and information sciences, Lower Bounds, algebraic circuits, polynomial identity testing, Networks and circuits as models of computation; circuit complexity, Computational Complexity (cs.CC), 004, lower bounds, Computer Science - Computational Complexity, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), Analysis of algorithms, Derandomization, algebraic complexity theory, Algebraic Complexity, Polynomial Identity Testing, ddc: ddc:004
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).5 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!