Literatura académica sobre el tema "Polynomial Identity Testing (PIT)"
Crea una cita precisa en los estilos APA, MLA, Chicago, Harvard y otros
Consulte las listas temáticas de artículos, libros, tesis, actas de conferencias y otras fuentes académicas sobre el tema "Polynomial Identity Testing (PIT)".
Junto a cada fuente en la lista de referencias hay un botón "Agregar a la bibliografía". Pulsa este botón, y generaremos automáticamente la referencia bibliográfica para la obra elegida en el estilo de cita que necesites: APA, MLA, Harvard, Vancouver, Chicago, etc.
También puede descargar el texto completo de la publicación académica en formato pdf y leer en línea su resumen siempre que esté disponible en los metadatos.
Artículos de revistas sobre el tema "Polynomial Identity Testing (PIT)"
Agrawal, Manindra, Sumanta Ghosh y Nitin Saxena. "Bootstrapping variables in algebraic circuits". Proceedings of the National Academy of Sciences 116, n.º 17 (11 de abril de 2019): 8107–18. http://dx.doi.org/10.1073/pnas.1901272116.
Texto completoHuang, Jinyu. "Parallel algorithms for matroid intersection and matroid parity". Discrete Mathematics, Algorithms and Applications 07, n.º 02 (25 de mayo de 2015): 1550019. http://dx.doi.org/10.1142/s1793830915500196.
Texto completoShpilka, Amir y Ilya Volkovich. "Read-once polynomial identity testing". computational complexity 24, n.º 3 (27 de mayo de 2015): 477–532. http://dx.doi.org/10.1007/s00037-015-0105-8.
Texto completoKopparty, Swastik, Shubhangi Saraf y Amir Shpilka. "Equivalence of Polynomial Identity Testing and Polynomial Factorization". computational complexity 24, n.º 2 (17 de abril de 2015): 295–331. http://dx.doi.org/10.1007/s00037-015-0102-y.
Texto completoKayal, Neeraj y Nitin Saxena. "Polynomial Identity Testing for Depth 3 Circuits". computational complexity 16, n.º 2 (mayo de 2007): 115–38. http://dx.doi.org/10.1007/s00037-007-0226-9.
Texto completoArvind, V. y Partha Mukhopadhyay. "The ideal membership problem and polynomial identity testing". Information and Computation 208, n.º 4 (abril de 2010): 351–63. http://dx.doi.org/10.1016/j.ic.2009.06.003.
Texto completoGrochow, Joshua A. y Toniann Pitassi. "Circuit Complexity, Proof Complexity, and Polynomial Identity Testing". Journal of the ACM 65, n.º 6 (26 de noviembre de 2018): 1–59. http://dx.doi.org/10.1145/3230742.
Texto completoRaz, Ran y Amir Shpilka. "Deterministic polynomial identity testing in non-commutative models". computational complexity 14, n.º 1 (abril de 2005): 1–19. http://dx.doi.org/10.1007/s00037-005-0188-8.
Texto completoArvind, V., Partha Mukhopadhyay y Srikanth Srinivasan. "New Results on Noncommutative and Commutative Polynomial Identity Testing". computational complexity 19, n.º 4 (diciembre de 2010): 521–58. http://dx.doi.org/10.1007/s00037-010-0299-8.
Texto completoGhosal, Purnata y B. V. Raghavendra Rao. "A note on parameterized polynomial identity testing using hitting set generators". Information Processing Letters 151 (noviembre de 2019): 105839. http://dx.doi.org/10.1016/j.ipl.2019.105839.
Texto completoTesis sobre el tema "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.
Texto completoThis 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] y 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.
Texto completoJindal, Gorav Verfasser] y 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.
Texto completoLagarde, Guillaume. "Contributions to arithmetic complexity and compression". Thesis, Sorbonne Paris Cité, 2018. http://www.theses.fr/2018USPCC192/document.
Texto completoThis 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.
Texto completoNair, 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.
Texto completoCapítulos de libros sobre el tema "Polynomial Identity Testing (PIT)"
Saxena, Nitin. "Progress on Polynomial Identity Testing-II". En Perspectives in Computational Complexity, 131–46. Cham: Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-05446-9_7.
Texto completoShpilka, Amir. "Recent Results on Polynomial Identity Testing". En 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.
Texto completoShpilka, Amir y Ilya Volkovich. "Improved Polynomial Identity Testing for Read-Once Formulas". En 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.
Texto completoForbes, Michael A. y Amir Shpilka. "Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing". En 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.
Texto completoShpilka, Amir y Ilya Volkovich. "On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors". En Automata, Languages and Programming, 408–19. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-14165-2_35.
Texto completoIvanyos, Gabor y Youming Qiao. "Algorithms based on *-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing". En 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.
Texto completoActas de conferencias sobre el tema "Polynomial Identity Testing (PIT)"
Shpilka, Amir y Ilya Volkovich. "Read-once polynomial identity testing". En the 40th annual ACM symposium. New York, New York, USA: ACM Press, 2008. http://dx.doi.org/10.1145/1374376.1374448.
Texto completoKopparty, Swastik, Shubhangi Saraf y Amir Shpilka. "Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization". En 2014 IEEE Conference on Computational Complexity (CCC). IEEE, 2014. http://dx.doi.org/10.1109/ccc.2014.25.
Texto completoAndrews, Robert. "On Matrix Multiplication and Polynomial Identity Testing". En 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2022. http://dx.doi.org/10.1109/focs54457.2022.00041.
Texto completoArvind, V., Pushkar S. Joglekar, Partha Mukhopadhyay y S. Raja. "Randomized polynomial time identity testing for noncommutative circuits". En STOC '17: Symposium on Theory of Computing. New York, NY, USA: ACM, 2017. http://dx.doi.org/10.1145/3055399.3055442.
Texto completoKayal, Neeraj y Shubhangi Saraf. "Blackbox Polynomial Identity Testing for Depth 3 Circuits". En 2009 IEEE 50th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2009. http://dx.doi.org/10.1109/focs.2009.67.
Texto completoGrochow, Joshua A. y Toniann Pitassi. "Circuit Complexity, Proof Complexity, and Polynomial Identity Testing". En 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2014. http://dx.doi.org/10.1109/focs.2014.20.
Texto completoArvind, V., Partha Mukhopadhyay y Srikanth Srinivasan. "New Results on Noncommutative and Commutative Polynomial Identity Testing". En 2008 23rd Annual IEEE Conference on Computational Complexity. IEEE, 2008. http://dx.doi.org/10.1109/ccc.2008.22.
Texto completoAnderson, Matthew, Dieter van Melkebeek y Ilya Volkovich. "Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae". En 2011 IEEE Annual Conference on Computational Complexity (CCC). IEEE, 2011. http://dx.doi.org/10.1109/ccc.2011.18.
Texto completoGarg, Ankit, Leonid Gurvits, Rafael Oliveira y Avi Wigderson. "A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing". En 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2016. http://dx.doi.org/10.1109/focs.2016.95.
Texto completoSullivan, Paul y Chris Evans. "“Improving the Robustness of Curve Fitting in Figure and Finish Metrology”". En Optical Fabrication and Testing. Washington, D.C.: Optica Publishing Group, 1992. http://dx.doi.org/10.1364/oft.1992.wa11.
Texto completo