Добірка наукової літератури з теми "Algebraic Branching Programs"
Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями
Ознайомтеся зі списками актуальних статей, книг, дисертацій, тез та інших наукових джерел на тему "Algebraic Branching Programs".
Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.
Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.
Статті в журналах з теми "Algebraic Branching Programs"
Kayal, Neeraj, Vineet Nair, Chandan Saha, and Sébastien Tavenas. "Reconstruction of Full Rank Algebraic Branching Programs." ACM Transactions on Computation Theory 11, no. 1 (January 16, 2019): 1–56. http://dx.doi.org/10.1145/3282427.
Повний текст джерелаKumar, Mrinal. "A quadratic lower bound for homogeneous algebraic branching programs." computational complexity 28, no. 3 (June 8, 2019): 409–35. http://dx.doi.org/10.1007/s00037-019-00186-3.
Повний текст джерелаGhosal, Purnata, and B. V. Raghavendra Rao. "On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models." Fundamenta Informaticae 177, no. 1 (December 18, 2020): 69–93. http://dx.doi.org/10.3233/fi-2020-1980.
Повний текст джерелаAllender, Eric, and Fengming Wang. "On the power of algebraic branching programs of width two." computational complexity 25, no. 1 (November 5, 2015): 217–53. http://dx.doi.org/10.1007/s00037-015-0114-7.
Повний текст джерелаAnderson, Matthew, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, and Ben Lee Volk. "Identity Testing and Lower Bounds for Read- k Oblivious Algebraic Branching Programs." ACM Transactions on Computation Theory 10, no. 1 (January 30, 2018): 1–30. http://dx.doi.org/10.1145/3170709.
Повний текст джерелаKayal, Neeraj, Vineet Nair, and Chandan Saha. "Average-case linear matrix factorization and reconstruction of low width algebraic branching programs." computational complexity 28, no. 4 (July 18, 2019): 749–828. http://dx.doi.org/10.1007/s00037-019-00189-0.
Повний текст джерелаKayal, Neeraj, Vineet Nair, and Chandan Saha. "Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth-three Circuits." ACM Transactions on Computation Theory 12, no. 1 (February 25, 2020): 1–27. http://dx.doi.org/10.1145/3369928.
Повний текст джерелаChaugule, Prasad, Nutan Limaye, and Aditya Varre. "Variants of Homomorphism Polynomials Complete for Algebraic Complexity Classes." ACM Transactions on Computation Theory 13, no. 4 (December 31, 2021): 1–26. http://dx.doi.org/10.1145/3470858.
Повний текст джерелаSTRAUBING, HOWARD. "CONSTANT-DEPTH PERIODIC CIRCUITS." International Journal of Algebra and Computation 01, no. 01 (March 1991): 49–87. http://dx.doi.org/10.1142/s0218196791000043.
Повний текст джерелаŠíma, Jiří, and Stanislav Žák. "A Polynomial-Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3." Fundamenta Informaticae 184, no. 4 (March 7, 2022): 307–54. http://dx.doi.org/10.3233/fi-2021-2101.
Повний текст джерелаДисертації з теми "Algebraic Branching Programs"
Forbes, Michael Andrew. "Polynomial identity testing of read-once oblivious algebraic branching programs." Thesis, Massachusetts Institute of Technology, 2014. http://hdl.handle.net/1721.1/89843.
Повний текст джерелаThis electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
Cataloged from student-submitted PDF version of thesis.
Includes bibliographical references (pages 209-220).
We study the problem of obtaining efficient, deterministic, black-box polynomial identity testing algorithms (PIT) for algebraic branching programs (ABPs) that are read-once and oblivious. This class has an efficient, deterministic, white-box polynomial identity testing algorithm (due to Raz and Shpilka [RS05]), but prior to this work there was no known such black-box algorithm. The main result of this work gives the first quasi-polynomial sized hitting set for size S circuits from this class, when the order of the variables is known. As our hitting set is of size exp(lg2 S), this is analogous (in the terminology of boolean pseudorandomness) to a seed-length of lg2 S, which is the seed length of the pseudorandom generators of Nisan [Nis92] and Impagliazzo-Nisan-Wigderson [INW94] for read-once oblivious boolean branching programs. Thus our work can be seen as an algebraic analogue of these foundational results in boolean pseudorandomness. We also show that several other circuit classes can be black-box reduced to readonce oblivious ABPs, including non-commutative ABPs and diagonal depth-4 circuits, and consequently obtain similar hitting sets for these classes as well. To establish the above hitting sets, we use a form of dimension reduction we call a rank condenser, which maps a large-dimensional space to a medium-dimensional space, while preserving the rank of low-dimensional subspaces. We give an explicit construction of a rank condenser that is randomness efficient and show how it can be used as a form of oblivious Gaussian elimination. As an application, we strengthen a result of Mulmuley [Mul12a], and show that derandomizing a particular case of the Noether Normalization Lemma is reducible to black-box PIT of read-once oblivious ABPs. Using our hitting set results, this gives a derandomization of Noether Normalization in that case.
by Michael Andrew Forbes.
Ph. D.
Nair, Vineet. "Expanders in Arithmetic Circuit Lower Bound : Towards a Separation Between ROABPs and Multilinear Depth 3 Circuits." Thesis, 2015. https://etd.iisc.ac.in/handle/2005/4811.
Повний текст джерелаNair, Vineet. "On Learning and Lower Bound Problems Related to the Iterated Matrix Multiplication Polynomial." Thesis, 2020. https://etd.iisc.ac.in/handle/2005/4597.
Повний текст джерелаЧастини книг з теми "Algebraic Branching Programs"
Malod, Guillaume. "Succinct Algebraic Branching Programs Characterizing Non-uniform Complexity Classes." In Fundamentals of Computation Theory, 205–16. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. http://dx.doi.org/10.1007/978-3-642-22953-4_18.
Повний текст джерелаAllender, Eric, and Fengming Wang. "On the Power of Algebraic Branching Programs of Width Two." In Automata, Languages and Programming, 736–47. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. http://dx.doi.org/10.1007/978-3-642-22006-7_62.
Повний текст джерелаТези доповідей конференцій з теми "Algebraic Branching Programs"
Forbes, Michael A., Ramprasad Saptharishi, and Amir Shpilka. "Hitting sets for multilinear read-once algebraic branching programs, in any order." In STOC '14: Symposium on Theory of Computing. New York, NY, USA: ACM, 2014. http://dx.doi.org/10.1145/2591796.2591816.
Повний текст джерелаForbes, Michael A., and Amir Shpilka. "Quasipolynomial-Time Identity Testing of Non-commutative and Read-Once Oblivious Algebraic Branching Programs." In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2013. http://dx.doi.org/10.1109/focs.2013.34.
Повний текст джерела