Добірка наукової літератури з теми "Polynomial Identity Testing (PIT)"
Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями
Ознайомтеся зі списками актуальних статей, книг, дисертацій, тез та інших наукових джерел на тему "Polynomial Identity Testing (PIT)".
Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.
Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.
Статті в журналах з теми "Polynomial Identity Testing (PIT)"
Agrawal, Manindra, Sumanta Ghosh, and Nitin Saxena. "Bootstrapping variables in algebraic circuits." Proceedings of the National Academy of Sciences 116, no. 17 (April 11, 2019): 8107–18. http://dx.doi.org/10.1073/pnas.1901272116.
Повний текст джерелаHuang, Jinyu. "Parallel algorithms for matroid intersection and matroid parity." Discrete Mathematics, Algorithms and Applications 07, no. 02 (May 25, 2015): 1550019. http://dx.doi.org/10.1142/s1793830915500196.
Повний текст джерелаShpilka, Amir, and Ilya Volkovich. "Read-once polynomial identity testing." computational complexity 24, no. 3 (May 27, 2015): 477–532. http://dx.doi.org/10.1007/s00037-015-0105-8.
Повний текст джерелаKopparty, Swastik, Shubhangi Saraf, and Amir Shpilka. "Equivalence of Polynomial Identity Testing and Polynomial Factorization." computational complexity 24, no. 2 (April 17, 2015): 295–331. http://dx.doi.org/10.1007/s00037-015-0102-y.
Повний текст джерелаKayal, Neeraj, and Nitin Saxena. "Polynomial Identity Testing for Depth 3 Circuits." computational complexity 16, no. 2 (May 2007): 115–38. http://dx.doi.org/10.1007/s00037-007-0226-9.
Повний текст джерелаArvind, V., and Partha Mukhopadhyay. "The ideal membership problem and polynomial identity testing." Information and Computation 208, no. 4 (April 2010): 351–63. http://dx.doi.org/10.1016/j.ic.2009.06.003.
Повний текст джерелаGrochow, Joshua A., and Toniann Pitassi. "Circuit Complexity, Proof Complexity, and Polynomial Identity Testing." Journal of the ACM 65, no. 6 (November 26, 2018): 1–59. http://dx.doi.org/10.1145/3230742.
Повний текст джерелаRaz, Ran, and Amir Shpilka. "Deterministic polynomial identity testing in non-commutative models." computational complexity 14, no. 1 (April 2005): 1–19. http://dx.doi.org/10.1007/s00037-005-0188-8.
Повний текст джерелаArvind, V., Partha Mukhopadhyay, and Srikanth Srinivasan. "New Results on Noncommutative and Commutative Polynomial Identity Testing." computational complexity 19, no. 4 (December 2010): 521–58. http://dx.doi.org/10.1007/s00037-010-0299-8.
Повний текст джерелаGhosal, Purnata, and B. V. Raghavendra Rao. "A note on parameterized polynomial identity testing using hitting set generators." Information Processing Letters 151 (November 2019): 105839. http://dx.doi.org/10.1016/j.ipl.2019.105839.
Повний текст джерелаДисертації з теми "Polynomial Identity Testing (PIT)"
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.
Jindal, Gorav [Verfasser], and Markus [Akademischer Betreuer] Bläser. "On approximate polynomial identity testing and real root finding / Gorav Jindal ; Betreuer: Markus Bläser." Saarbrücken : Saarländische Universitäts- und Landesbibliothek, 2019. http://d-nb.info/1200408160/34.
Повний текст джерелаJindal, Gorav Verfasser], and Markus [Akademischer Betreuer] [Bläser. "On approximate polynomial identity testing and real root finding / Gorav Jindal ; Betreuer: Markus Bläser." Saarbrücken : Saarländische Universitäts- und Landesbibliothek, 2019. http://nbn-resolving.de/urn:nbn:de:bsz:291--ds-298805.
Повний текст джерелаLagarde, Guillaume. "Contributions to arithmetic complexity and compression." Thesis, Sorbonne Paris Cité, 2018. http://www.theses.fr/2018USPCC192/document.
Повний текст джерелаThis thesis explores two territories of computer science: complexity and compression. More precisely, in a first part, we investigate the power of non-commutative arithmetic circuits, which compute multivariate non-commutative polynomials. For that, we introduce various models of computation that are restricted in the way they are allowed to compute monomials. These models generalize previous ones that have been widely studied, such as algebraic branching programs. The results are of three different types. First, we give strong lower bounds on the number of arithmetic operations needed to compute some polynomials such as the determinant or the permanent. Second, we design some deterministic polynomial-time algorithm to solve the white-box polynomial identity problem. Third, we exhibit a link between automata theory and non-commutative arithmetic circuits that allows us to derive some old and new tight lower bounds for some classes of non-commutative circuits, using a measure based on the rank of a so-called Hankel matrix. A second part is concerned with the analysis of the data compression algorithm called Lempel-Ziv. Although this algorithm is widely used in practice, we know little about its stability. Our main result is to show that an infinite word compressible by LZ’78 can become incompressible by adding a single bit in front of it, thus closing a question proposed by Jack Lutz in the late 90s under the name “one-bit catastrophe”. We also give tight bounds on the maximal possible variation between the compression ratio of a finite word and its perturbation—when one bit is added in front of it
Grenet, Bruno. "Représentations des polynômes, algorithmes et bornes inférieures." Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2012. http://tel.archives-ouvertes.fr/tel-00770148.
Повний текст джерела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.
Повний текст джерелаЧастини книг з теми "Polynomial Identity Testing (PIT)"
Saxena, Nitin. "Progress on Polynomial Identity Testing-II." In Perspectives in Computational Complexity, 131–46. Cham: Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-05446-9_7.
Повний текст джерелаShpilka, Amir. "Recent Results on Polynomial Identity Testing." In Computer Science – Theory and Applications, 397–400. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. http://dx.doi.org/10.1007/978-3-642-20712-9_31.
Повний текст джерелаShpilka, Amir, and Ilya Volkovich. "Improved Polynomial Identity Testing for Read-Once Formulas." In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 700–713. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-03685-9_52.
Повний текст джерелаForbes, Michael A., and Amir Shpilka. "Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing." In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 527–42. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-40328-6_37.
Повний текст джерелаShpilka, Amir, and Ilya Volkovich. "On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors." In Automata, Languages and Programming, 408–19. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-14165-2_35.
Повний текст джерелаIvanyos, Gabor, and Youming Qiao. "Algorithms based on *-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing." In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2357–76. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2018. http://dx.doi.org/10.1137/1.9781611975031.152.
Повний текст джерелаТези доповідей конференцій з теми "Polynomial Identity Testing (PIT)"
Shpilka, Amir, and Ilya Volkovich. "Read-once polynomial identity testing." In the 40th annual ACM symposium. New York, New York, USA: ACM Press, 2008. http://dx.doi.org/10.1145/1374376.1374448.
Повний текст джерелаKopparty, Swastik, Shubhangi Saraf, and Amir Shpilka. "Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization." In 2014 IEEE Conference on Computational Complexity (CCC). IEEE, 2014. http://dx.doi.org/10.1109/ccc.2014.25.
Повний текст джерелаAndrews, Robert. "On Matrix Multiplication and Polynomial Identity Testing." In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2022. http://dx.doi.org/10.1109/focs54457.2022.00041.
Повний текст джерелаArvind, V., Pushkar S. Joglekar, Partha Mukhopadhyay, and S. Raja. "Randomized polynomial time identity testing for noncommutative circuits." In STOC '17: Symposium on Theory of Computing. New York, NY, USA: ACM, 2017. http://dx.doi.org/10.1145/3055399.3055442.
Повний текст джерелаKayal, Neeraj, and Shubhangi Saraf. "Blackbox Polynomial Identity Testing for Depth 3 Circuits." In 2009 IEEE 50th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2009. http://dx.doi.org/10.1109/focs.2009.67.
Повний текст джерелаGrochow, Joshua A., and Toniann Pitassi. "Circuit Complexity, Proof Complexity, and Polynomial Identity Testing." In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2014. http://dx.doi.org/10.1109/focs.2014.20.
Повний текст джерелаArvind, V., Partha Mukhopadhyay, and Srikanth Srinivasan. "New Results on Noncommutative and Commutative Polynomial Identity Testing." In 2008 23rd Annual IEEE Conference on Computational Complexity. IEEE, 2008. http://dx.doi.org/10.1109/ccc.2008.22.
Повний текст джерелаAnderson, Matthew, Dieter van Melkebeek, and Ilya Volkovich. "Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae." In 2011 IEEE Annual Conference on Computational Complexity (CCC). IEEE, 2011. http://dx.doi.org/10.1109/ccc.2011.18.
Повний текст джерелаGarg, Ankit, Leonid Gurvits, Rafael Oliveira, and Avi Wigderson. "A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing." In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2016. http://dx.doi.org/10.1109/focs.2016.95.
Повний текст джерелаSullivan, Paul, and Chris Evans. "“Improving the Robustness of Curve Fitting in Figure and Finish Metrology”." In Optical Fabrication and Testing. Washington, D.C.: Optica Publishing Group, 1992. http://dx.doi.org/10.1364/oft.1992.wa11.
Повний текст джерела