Gotowa bibliografia na temat „Polynomial Identity Testing (PIT)”
Utwórz poprawne odniesienie w stylach APA, MLA, Chicago, Harvard i wielu innych
Zobacz listy aktualnych artykułów, książek, rozpraw, streszczeń i innych źródeł naukowych na temat „Polynomial Identity Testing (PIT)”.
Przycisk „Dodaj do bibliografii” jest dostępny obok każdej pracy w bibliografii. Użyj go – a my automatycznie utworzymy odniesienie bibliograficzne do wybranej pracy w stylu cytowania, którego potrzebujesz: APA, MLA, Harvard, Chicago, Vancouver itp.
Możesz również pobrać pełny tekst publikacji naukowej w formacie „.pdf” i przeczytać adnotację do pracy online, jeśli odpowiednie parametry są dostępne w metadanych.
Artykuły w czasopismach na temat "Polynomial Identity Testing (PIT)"
Agrawal, Manindra, Sumanta Ghosh i Nitin Saxena. "Bootstrapping variables in algebraic circuits". Proceedings of the National Academy of Sciences 116, nr 17 (11.04.2019): 8107–18. http://dx.doi.org/10.1073/pnas.1901272116.
Pełny tekst źródłaHuang, Jinyu. "Parallel algorithms for matroid intersection and matroid parity". Discrete Mathematics, Algorithms and Applications 07, nr 02 (25.05.2015): 1550019. http://dx.doi.org/10.1142/s1793830915500196.
Pełny tekst źródłaShpilka, Amir, i Ilya Volkovich. "Read-once polynomial identity testing". computational complexity 24, nr 3 (27.05.2015): 477–532. http://dx.doi.org/10.1007/s00037-015-0105-8.
Pełny tekst źródłaKopparty, Swastik, Shubhangi Saraf i Amir Shpilka. "Equivalence of Polynomial Identity Testing and Polynomial Factorization". computational complexity 24, nr 2 (17.04.2015): 295–331. http://dx.doi.org/10.1007/s00037-015-0102-y.
Pełny tekst źródłaKayal, Neeraj, i Nitin Saxena. "Polynomial Identity Testing for Depth 3 Circuits". computational complexity 16, nr 2 (maj 2007): 115–38. http://dx.doi.org/10.1007/s00037-007-0226-9.
Pełny tekst źródłaArvind, V., i Partha Mukhopadhyay. "The ideal membership problem and polynomial identity testing". Information and Computation 208, nr 4 (kwiecień 2010): 351–63. http://dx.doi.org/10.1016/j.ic.2009.06.003.
Pełny tekst źródłaGrochow, Joshua A., i Toniann Pitassi. "Circuit Complexity, Proof Complexity, and Polynomial Identity Testing". Journal of the ACM 65, nr 6 (26.11.2018): 1–59. http://dx.doi.org/10.1145/3230742.
Pełny tekst źródłaRaz, Ran, i Amir Shpilka. "Deterministic polynomial identity testing in non-commutative models". computational complexity 14, nr 1 (kwiecień 2005): 1–19. http://dx.doi.org/10.1007/s00037-005-0188-8.
Pełny tekst źródłaArvind, V., Partha Mukhopadhyay i Srikanth Srinivasan. "New Results on Noncommutative and Commutative Polynomial Identity Testing". computational complexity 19, nr 4 (grudzień 2010): 521–58. http://dx.doi.org/10.1007/s00037-010-0299-8.
Pełny tekst źródłaGhosal, Purnata, i B. V. Raghavendra Rao. "A note on parameterized polynomial identity testing using hitting set generators". Information Processing Letters 151 (listopad 2019): 105839. http://dx.doi.org/10.1016/j.ipl.2019.105839.
Pełny tekst źródłaRozprawy doktorskie na temat "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.
Pełny tekst źródłaThis 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], i 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.
Pełny tekst źródłaJindal, Gorav Verfasser], i 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.
Pełny tekst źródłaLagarde, Guillaume. "Contributions to arithmetic complexity and compression". Thesis, Sorbonne Paris Cité, 2018. http://www.theses.fr/2018USPCC192/document.
Pełny tekst źródłaThis 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.
Pełny tekst źródłaNair, 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.
Pełny tekst źródłaCzęści książek na temat "Polynomial Identity Testing (PIT)"
Saxena, Nitin. "Progress on Polynomial Identity Testing-II". W Perspectives in Computational Complexity, 131–46. Cham: Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-05446-9_7.
Pełny tekst źródłaShpilka, Amir. "Recent Results on Polynomial Identity Testing". W 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.
Pełny tekst źródłaShpilka, Amir, i Ilya Volkovich. "Improved Polynomial Identity Testing for Read-Once Formulas". W 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.
Pełny tekst źródłaForbes, Michael A., i Amir Shpilka. "Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing". W 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.
Pełny tekst źródłaShpilka, Amir, i Ilya Volkovich. "On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors". W Automata, Languages and Programming, 408–19. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-14165-2_35.
Pełny tekst źródłaIvanyos, Gabor, i Youming Qiao. "Algorithms based on *-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing". W 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.
Pełny tekst źródłaStreszczenia konferencji na temat "Polynomial Identity Testing (PIT)"
Shpilka, Amir, i Ilya Volkovich. "Read-once polynomial identity testing". W the 40th annual ACM symposium. New York, New York, USA: ACM Press, 2008. http://dx.doi.org/10.1145/1374376.1374448.
Pełny tekst źródłaKopparty, Swastik, Shubhangi Saraf i Amir Shpilka. "Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization". W 2014 IEEE Conference on Computational Complexity (CCC). IEEE, 2014. http://dx.doi.org/10.1109/ccc.2014.25.
Pełny tekst źródłaAndrews, Robert. "On Matrix Multiplication and Polynomial Identity Testing". W 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2022. http://dx.doi.org/10.1109/focs54457.2022.00041.
Pełny tekst źródłaArvind, V., Pushkar S. Joglekar, Partha Mukhopadhyay i S. Raja. "Randomized polynomial time identity testing for noncommutative circuits". W STOC '17: Symposium on Theory of Computing. New York, NY, USA: ACM, 2017. http://dx.doi.org/10.1145/3055399.3055442.
Pełny tekst źródłaKayal, Neeraj, i Shubhangi Saraf. "Blackbox Polynomial Identity Testing for Depth 3 Circuits". W 2009 IEEE 50th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2009. http://dx.doi.org/10.1109/focs.2009.67.
Pełny tekst źródłaGrochow, Joshua A., i Toniann Pitassi. "Circuit Complexity, Proof Complexity, and Polynomial Identity Testing". W 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2014. http://dx.doi.org/10.1109/focs.2014.20.
Pełny tekst źródłaArvind, V., Partha Mukhopadhyay i Srikanth Srinivasan. "New Results on Noncommutative and Commutative Polynomial Identity Testing". W 2008 23rd Annual IEEE Conference on Computational Complexity. IEEE, 2008. http://dx.doi.org/10.1109/ccc.2008.22.
Pełny tekst źródłaAnderson, Matthew, Dieter van Melkebeek i Ilya Volkovich. "Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae". W 2011 IEEE Annual Conference on Computational Complexity (CCC). IEEE, 2011. http://dx.doi.org/10.1109/ccc.2011.18.
Pełny tekst źródłaGarg, Ankit, Leonid Gurvits, Rafael Oliveira i Avi Wigderson. "A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing". W 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2016. http://dx.doi.org/10.1109/focs.2016.95.
Pełny tekst źródłaSullivan, Paul, i Chris Evans. "“Improving the Robustness of Curve Fitting in Figure and Finish Metrology”". W Optical Fabrication and Testing. Washington, D.C.: Optica Publishing Group, 1992. http://dx.doi.org/10.1364/oft.1992.wa11.
Pełny tekst źródła