Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

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

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/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(n11/2k1) and needs white box access only to know the order in which the variables appear in the ABP. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

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

Download PDF
30 pages

Loading next page...
 
/lp/association-for-computing-machinery/identity-testing-and-lower-bounds-for-read-k-oblivious-algebraic-sDo5T4Bo7f
Publisher
Association for Computing Machinery
Copyright
Copyright © 2018 ACM
ISSN
1942-3454
eISSN
1942-3462
DOI
10.1145/3170709
Publisher site
See Article on Publisher Site

Abstract

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/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(n11/2k1) and needs white box access only to know the order in which the variables appear in the ABP.

Journal

ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery

Published: Jan 10, 2018

Keywords: Algebraic complexity theory

References

  • Proving lower bounds via pseudo-random generators
    Agrawal, Manindra
  • Hitting-sets for ROABP and sum of set-multilinear circuits
    Agrawal, Manindra; Gurjar, Rohit; Korwar, Arpita; Saxena, Nitin
  • Arithmetic circuits: A chasm at depth four
    Agrawal, Manindra; Vinay, V.
  • Proofs from THE BOOK
    Aigner, Martin; Ziegler, Günter M.
  • A non-linear time lower bound for Boolean branching programs
    Ajtai, Miklós
  • Separating pairs of points by standard boxes
    Alon, Noga; Füredi, Zoltán; Katchalski, Meir
  • Identity testing and lower bounds for read-k oblivious algebraic branching programs
    Anderson, Matthew; Forbes, Michael A.; Saptharishi, Ramprasad; Shpilka, Amir; Volk, Ben Lee
  • Deterministic polynomial identity tests for multilinear bounded-read formulae
    Anderson, Matthew; van Melkebeek, Dieter; Volkovich, Ilya
  • Some lower bound results for set-multilinear arithmetic computations
    Arvind, Vikraman; Raja, S.
  • A lower bound for read-once-only branching programs
    Babai, László; Hajnal, Péter; Szemerédi, Endre; Turán, György
  • Time-space trade-off lower bounds for randomized computation of decision problems
    Beame, Paul; Saks, Michael E.; Sun, Xiaodong; Vee, Erik
  • Pseudorandomness for width-2 branching programs
    Bogdanov, Andrej; Dvir, Zeev; Verbin, Elad; Yehudayoff, Amir
  • Pseudorandomness for read-once formulas
    Bogdanov, Andrej; Papakonstantinou, Periklis A.; Wan, Andrew
  • On lower bounds for read--times branching programs
    Borodin, Allan; Razborov, Alexander A.; Smolensky, Roman
  • Pseudorandom generators for regular branching programs
    Braverman, Mark; Rao, Anup; Raz, Ran; Yehudayoff, Amir
  • Pseudorandomness for permutation and regular branching programs
    De, Anindya
  • A probabilistic remark on algebraic program testing
    DeMillo, Richard A.; Lipton, Richard J.
  • Locally decodable codes with two queries and polynomial identity testing for depth 3 circuits
    Dvir, Zeev; Shpilka, Amir
  • Hardness-randomness tradeoffs for bounded depth arithmetic circuits
    Dvir, Zeev; Shpilka, Amir; Yehudayoff, Amir
  • A combinatorial problem in geometry
    Erdős, Paul; Szekeres, George
  • Polynomial Identity Testing of Read-Once Oblivious Algebraic Branching Programs
    Forbes, Michael
  • Hitting sets for multilinear read-once algebraic branching programs, in any order
    Forbes, Michael A.; Saptharishi, Ramprasad; Shpilka, Amir
  • Explicit noether normalization for simultaneous conjugation via polynomial identity testing
    Forbes, Michael A.; Shpilka, Amir
  • Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs
    Forbes, Michael A.; Shpilka, Amir
  • Lower bounds for depth 4 formulas computing iterated matrix multiplication
    Fournier, Hervé; Limaye, Nutan; Malod, Guillaume; Srinivasan, Srikanth
  • Better pseudorandom generators from milder pseudorandom restrictions
    Gopalan, Parikshit; Meka, Raghu; Reingold, Omer; Trevisan, Luca; Vadhan, Salil P.
  • Arithmetic circuits: A chasm at depth three
    Gupta, Ankit; Kamath, Pritish; Kayal, Neeraj; Saptharishi, Ramprasad
  • Approaching the chasm at depth four
    Gupta, Ankit; Kamath, Pritish; Kayal, Neeraj; Saptharishi, Ramprasad
  • Deterministic identity testing for sum of read-once oblivious arithmetic branching programs
    Gurjar, Rohit; Korwar, Arpita; Saxena, Nitin; Thierauf, Thomas
  • Testing polynomials which are easy to compute (extended abstract)
    Heintz, Joos; Schnorr, Claus-Peter
  • Pseudorandomness from shrinkage
    Impagliazzo, Russell; Meka, Raghu; Zuckerman, David
  • Pseudorandomness for network algorithms
    Impagliazzo, Russell; Nisan, Noam; Wigderson, Avi
  • Deterministic black-box identity testing $pi$-ordered algebraic branching programs
    Jansen, Maurice J.; Qiao, Youming; Sarma, Jayalal
  • Deterministic identity testing of read-once algebraic branching programs
    Jansen, Maurice J.; Qiao, Youming; Sarma, Jayalal
  • Derandomizing polynomial identity tests means proving circuit lower bounds
    Kabanets, Valentine; Impagliazzo, Russell
  • Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in
    Karnin, Zohar Shay; Mukhopadhyay, Partha; Shpilka, Amir; Volkovich, Ilya
  • Constructing a perfect matching is in random NC
    Karp, Richard M.; Upfal, Eli; Wigderson, Avi
  • An exponential lower bound for homogeneous depth four arithmetic circuits
    Kayal, Neeraj; Limaye, Nutan; Saha, Chandan; Srinivasan, Srikanth
  • Separation between read-once oblivious algebraic branching programs (ROABPs) and multilinear depth three circuits
    Kayal, Neeraj; Nair, Vineet; Saha, Chandan
  • A super-polynomial lower bound for regular arithmetic formulas
    Kayal, Neeraj; Saha, Chandan; Saptharishi, Ramprasad
  • Blackbox polynomial identity testing for depth- circuits
    Kayal, Neeraj; Saraf, Shubhangi
  • Polynomial identity testing for depth 3 circuits
    Kayal, Neeraj; Saxena, Nitin
  • Arithmetic circuits: The chasm at depth four gets wider
    Koiran, Pascal
  • Equivalence of polynomial identity testing and polynomial factorization
    Kopparty, Swastik; Saraf, Shubhangi; Shpilka, Amir
  • Pseudorandom generators for group products: Extended abstract
    Koucký, Michal; Nimbhorkar, Prajakta; Pudlák, Pavel
  • Monotonic subsequences
    Kruskal, Joseph B.
  • The limits of depth reduction for arithmetic formulas: It’s all about the top fan-in
    Kumar, Mrinal; Saraf, Shubhangi
  • On the power of homogeneous depth arithmetic circuits
    Kumar, Mrinal; Saraf, Shubhangi
  • Complete derandomization of identity testing and reconstruction of read-once formulas
    Minahan, Daniel; Volkovich, Ilya
  • Geometric complexity theory v: Equivalence between blackbox derandomization of polynomial identity testing and derandomization of noether’s normalization lemma
    Mulmuley, Ketan
  • Matching is as easy as matrix inversion
    Mulmuley, Ketan; Vazirani, Umesh V.; Vazirani, Vijay V.
  • Lower bounds for non-commutative computation
    Nisan, Noam
  • Pseudorandom generators for space-bounded computation
    Nisan, Noam
  • Hardness vs randomness
    Nisan, Noam; Wigderson, Avi
  • Lower bounds on the complexity of realization of characteristic functions of binary codes by branching programs
    Okolnishnikova, E. A.
  • Subexponential size hitting sets for bounded depth multilinear formulas
    Oliveira, Rafael; Shpilka, Amir; Volk, Ben Lee
  • Deterministic polynomial identity testing in non-commutative models
    Raz, Ran; Shpilka, Amir
  • Lower bounds and separations for constant depth multilinear circuits
    Raz, Ran; Yehudayoff, Amir
  • Pseudorandomness for regular branching programs via fourier analysis
    Reingold, Omer; Steinke, Thomas; Vadhan, Salil P.
  • Black-box identity testing of depth-4 multilinear circuits
    Saraf, Shubhangi; Volkovich, Ilya
  • Blackbox identity testing for bounded top-fanin depth-3 circuits: The field doesn’t matter
    Saxena, Nitin; Seshadhri, C.
  • Fast probabilistic algorithms for verification of polynomial identities
    Schwartz, Jacob T.
  • On the relation between polynomial identity testing and finding variable disjoint factors
    Shpilka, Amir; Volkovich, Ilya
  • Read-once polynomial identity testing
    Shpilka, Amir; Volkovich, Ilya
  • Arithmetic circuits: A survey of recent results and open questions
    Shpilka, Amir; Yehudayoff, Amir
  • Pseudorandomness for permutation branching programs without the group theory
    Steinke, Thomas
  • Pseudorandomness and fourier growth bounds for width-3 branching programs
    Steinke, Thomas; Vadhan, Salil P.; Wan, Andrew
  • Improved bounds for reduction to depth 4 and depth 3
    Tavenas, Sébastien
  • On separating the read-k-times branching program hierarchy
    Thathachar, Jayram S.
  • Fast parallel computation of polynomials using few processors
    Valiant, Leslie G.; Skyum, Sven; Berkowitz, S.; Rackoff, Charles
  • On the complexity of branching programs and decision trees for clique functions
    Wegener, Ingo
  • An exponential lower bound for one-time-only branching programs
    Zák, Stanislav
  • Probabilistic algorithms for sparse polynomials
    Zippel, Richard