Relevant bibliographies by topics / Polynomial Identity Testing (PIT)

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Book chapters
  4. Conference papers

Academic literature on the topic 'Polynomial Identity Testing (PIT)'

Author: Grafiati
Published: 6 September 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Polynomial Identity Testing (PIT).'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Polynomial Identity Testing (PIT)"

1

Agrawal, Manindra, Sumanta Ghosh, and Nitin Saxena. "Bootstrapping variables in algebraic circuits." Proceedings of the National Academy of Sciences 116, no. 17 (2019): 8107–18. http://dx.doi.org/10.1073/pnas.1901272116.

Full text
Abstract:
We show that for the blackbox polynomial identity testing (PIT) problem it suffices to study circuits that depend only on the first extremely few variables. One needs only to consider size-s degree-s circuits that depend on the firstlog○c svariables (where c is a constant and composes a logarithm with itself c times). Thus, the hitting-set generator (hsg) manifests a bootstrapping behavior—a partial hsg against very few variables can be efficiently grown to a complete hsg. A Boolean analog, or a pseudorandom generator property of this type, is unheard of. Our idea is to use the partial hsg and
APA, Harvard, Vancouver, ISO, and other styles
2

Huang, Jinyu. "Parallel algorithms for matroid intersection and matroid parity." Discrete Mathematics, Algorithms and Applications 07, no. 02 (2015): 1550019. http://dx.doi.org/10.1142/s1793830915500196.

Full text
Abstract:
A maximum linear matroid parity set is called a basic matroid parity set, if its size is the rank of the matroid. We show that determining the existence of a common base (basic matroid parity set) for linear matroid intersection (linear matroid parity) is in NC2, provided that there are polynomial number of common bases (basic matroid parity sets). For graphic matroids, we show that finding a common base for matroid intersection is in NC2, if the number of common bases is polynomial bounded. To our knowledge, these algorithms are the first deterministic NC algorithms for matroid intersection a
APA, Harvard, Vancouver, ISO, and other styles
3

Shpilka, Amir, and Ilya Volkovich. "Read-once polynomial identity testing." computational complexity 24, no. 3 (2015): 477–532. http://dx.doi.org/10.1007/s00037-015-0105-8.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Kopparty, Swastik, Shubhangi Saraf, and Amir Shpilka. "Equivalence of Polynomial Identity Testing and Polynomial Factorization." computational complexity 24, no. 2 (2015): 295–331. http://dx.doi.org/10.1007/s00037-015-0102-y.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Kayal, Neeraj, and Nitin Saxena. "Polynomial Identity Testing for Depth 3 Circuits." computational complexity 16, no. 2 (2007): 115–38. http://dx.doi.org/10.1007/s00037-007-0226-9.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Arvind, V., and Partha Mukhopadhyay. "The ideal membership problem and polynomial identity testing." Information and Computation 208, no. 4 (2010): 351–63. http://dx.doi.org/10.1016/j.ic.2009.06.003.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Grochow, Joshua A., and Toniann Pitassi. "Circuit Complexity, Proof Complexity, and Polynomial Identity Testing." Journal of the ACM 65, no. 6 (2018): 1–59. http://dx.doi.org/10.1145/3230742.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Raz, Ran, and Amir Shpilka. "Deterministic polynomial identity testing in non-commutative models." computational complexity 14, no. 1 (2005): 1–19. http://dx.doi.org/10.1007/s00037-005-0188-8.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Arvind, V., Partha Mukhopadhyay, and Srikanth Srinivasan. "New Results on Noncommutative and Commutative Polynomial Identity Testing." computational complexity 19, no. 4 (2010): 521–58. http://dx.doi.org/10.1007/s00037-010-0299-8.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic "Polynomial Identity Testing (PIT)"

1

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.

Full text
Abstract:
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014.<br>This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.<br>Cataloged from student-submitted PDF version of thesis.<br>Includes bibliographical references (pages 209-220).<br>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 effic
APA, Harvard, Vancouver, ISO, and other styles
2

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Lagarde, Guillaume. "Contributions to arithmetic complexity and compression." Thesis, Sorbonne Paris Cité, 2018. http://www.theses.fr/2018USPCC192/document.

Full text
Abstract:
Cette thèse explore deux territoires distincts de l’informatique fondamentale : la complexité et la compression. Plus précisément, dans une première partie, nous étudions la puissance des circuits arithmétiques non commutatifs, qui calculent des polynômes non commutatifs en plusieurs indéterminées. Pour cela, nous introduisons plusieurs modèles de calcul, restreints dans leur manière de calculer les monômes. Ces modèles en généralisent d’autres, plus anciens et largement étudiés, comme les programmes à branchements. Les résultats sont de trois sortes. Premièrement, nous donnons des bornes infé
APA, Harvard, Vancouver, ISO, and other styles
5

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.

Full text
Abstract:
La complexité algorithmique est l'étude des ressources nécessaires -- le temps, la mémoire, ... -- pour résoudre un problème de manière algorithmique. Dans ce cadre, la théorie de la complexité algébrique est l'étude de la complexité algorithmique de problèmes de nature algébrique, concernant des polynômes.Dans cette thèse, nous étudions différents aspects de la complexité algébrique. D'une part, nous nous intéressons à l'expressivité des déterminants de matrices comme représentations des polynômes dans le modèle de complexité de Valiant. Nous montrons que les matrices symétriques ont la même
APA, Harvard, Vancouver, ISO, and other styles
6

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.

Full text
Abstract:
Consider the problem of Polynomial Identity Testing(PIT): we are given an arithmetic circuit computing a multivariate polynomial over some eld and we have to determine whether that polynomial is identically zero or not. PIT is a fundamental problem and has applications in both algorithms and complexity theory. In this work, our aim is to study PIT for the model of multilinear depth three circuits for which no deterministic polynomial time identity test is known. An nO(log n) time blackbox PIT for set-multilinear depth three circuits (a special kind of multilinear depth three circuits) i
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Polynomial Identity Testing (PIT)"

1

Saxena, Nitin. "Progress on Polynomial Identity Testing-II." In Perspectives in Computational Complexity. Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-05446-9_7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Shpilka, Amir. "Recent Results on Polynomial Identity Testing." In Computer Science – Theory and Applications. Springer Berlin Heidelberg, 2011. http://dx.doi.org/10.1007/978-3-642-20712-9_31.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Shpilka, Amir, and Ilya Volkovich. "Improved Polynomial Identity Testing for Read-Once Formulas." In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-03685-9_52.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

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. Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-40328-6_37.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Shpilka, Amir, and Ilya Volkovich. "On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors." In Automata, Languages and Programming. Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-14165-2_35.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

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. Society for Industrial and Applied Mathematics, 2018. http://dx.doi.org/10.1137/1.9781611975031.152.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Polynomial Identity Testing (PIT)"

1

Shpilka, Amir, and Ilya Volkovich. "Read-once polynomial identity testing." In the 40th annual ACM symposium. ACM Press, 2008. http://dx.doi.org/10.1145/1374376.1374448.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

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. ACM, 2017. http://dx.doi.org/10.1145/3055399.3055442.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Sullivan, Paul, and Chris Evans. "“Improving the Robustness of Curve Fitting in Figure and Finish Metrology”." In Optical Fabrication and Testing. Optica Publishing Group, 1992. http://dx.doi.org/10.1364/oft.1992.wa11.

Full text
Abstract:
Curve fitting has many applications in topographic characterization including areas such as datum definition, modelling, and filtering e.g. the use of Zernike polynomials in figure metrology and the removal of tilt and curvature in finish measurement. However, topography measurement data does not represent a purely theoretical manufacturing process and contains events which are part of the "true" surface such as scratches and digs (also referred to as pits and troughs or cosmetics), and include erroneous data which are not part of the "true" surface resulting from measurement errors (e.g. sign
APA, Harvard, Vancouver, ISO, and other styles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography