Log in

Relevant bibliographies by topics / Polynomial Identity Testing (PIT)

Contents

Journal articles
Dissertations / Theses
Book chapters
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 its annihilator polynomial to efficiently bootstrap the hsg exponentially w.r.t. variables. This is repeated c times in an efficient way. Pushing the envelope further we show that (i) a quadratic-time blackbox PIT for 6,913-variate degree-s size-s polynomials will lead to a “near”-complete derandomization of PIT and (ii) a blackbox PIT for n-variate degree-s size-s circuits insnδtime, forδ<1/2, will lead to a near-complete derandomization of PIT (in contrast,sntime is trivial). Our second idea is to study depth-4 circuits that depend on constantly many variables. We show that a polynomial-time computable,O(s1.49)-degree hsg for trivariate depth-4 circuits bootstraps to a quasipolynomial time hsg for general polydegree circuits and implies a lower bound that is a bit stronger than that of Kabanets and Impagliazzo [Kabanets V, Impagliazzo R (2003)Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing STOC ’03].

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 and matroid parity. We also give a new RNC2 algorithm that finds a common base for graphic matroid intersection. We prove that if there is a black-box NC algorithm for Polynomial Identity Testing (PIT), then there is an NC algorithm to determine the existence of a common base (basic matroid parity set) for linear matroid intersection (linear matroid parity).

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 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.<br>by Michael Andrew Forbes.<br>Ph. D.

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érieures sur le nombre d’opérations arithmétiques nécessaires au calcul de certains polynômes tels que le déterminant ou encore le permanent. Deuxièmement, nous concevons des algorithmes déterministes fonctionnant en temps polynomial pour résoudre le problème du test d’identité polynomiale. Enfin, nous construisons un pont entre la théorie des automates et les circuits arithmétiques non commutatifs, ce qui nous permet de dériver de nouvelles bornes inférieures en utilisant une mesure reposant sur le rang de la matrice dite de Hankel, provenant de la théorie des automates. Une deuxième partie concerne l’analyse de l’algorithme de compression sans perte Lempel-Ziv. Pourtant très utilisé, sa stabilité est encore mal établie. Vers la fin des années 90s, Jack Lutz popularise la question suivante, connue sous le nom de « one-bit catastrophe » : « étant donné un mot compressible, est-il possible de le rendre incompressible en ne changeant qu’un seul bit ? ». Nous montrons qu’une telle catastrophe est en effet possible. Plus précisément, en donnant des bornes optimales sur la variation de la taille de la compression, nous montrons qu’un mot « très compressible » restera toujours compressible après modification d’un bit, mais que certains mots « peu compressibles » deviennent en effet incompressibles<br>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

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 expressivité que les matrices quelconques dès que la caractéristique du corps est différente de deux, mais que ce n'est plus le cas en caractéristique deux. Nous construisons également la représentation la plus compacte connue du permanent par un déterminant. D'autre part, nous étudions la complexité algorithmique de problèmes algébriques. Nous montrons que la détection de racines dans un système de n polynômes homogènes à n variables est NP-difficile. En lien avec la question " VP = VNP ? ", version algébrique de " P = NP ? ", nous obtenons une borne inférieure pour le calcul du permanent d'une matrice par un circuit arithmétique, et nous exhibons des liens unissant ce problème et celui du test d'identité polynomiale. Enfin nous fournissons des algorithmes efficaces pour la factorisation des polynômes lacunaires à deux variables.

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) is known due to [ASS12], [FS13]. To get a better understanding of the problem at hand, we move towards multilinear depth three circuits by considering in- termediate circuit classes which encompasse more polynomials than set-multilinear depth three circuits and are `natural' subclasses of multilinear depth three circuits. One such model is `superposition of set-multilinear depth 3 circuits'. Our initial observations are: There is an nO(log n) whitebox PIT for superposition of two set-multilinear depth 3 circuits. There is a sub-exponential time whitebox PIT for superposition of constantly many set- multilinear depth 3 circuits. The second observation is subsumed by the recent independent and almost simultaneous work by [OSV15] that gives sub-exponential time hitting set for multilinear depth three circuits. A recent line of research considers hitting set for Read Once Oblivious Algebraic Branching Programs (ROABP's) which subsumes set-multilinear depth three circuits. An nO(log n) black box PIT is given for ROABP's of width polynomial in the number of variables in [AGKS14]. It is natural to ask whether this result on ROABP PIT can be used to give e cient (meaning polynomial or quasi-polynomial time) PIT for multilinear depth three circuits. For instance, the result by [OSV15] elegantly uses ROABP PIT as a `base case' (in a certain sense) to give a sub-exponential time PIT algorithm for multilinear depth three circuits. At this point, we wondered if multilinear depth three circuits of size s could also be computed by an ROABP of size polynomial in s. If true then this would immediately imply a quasi-polynomial time hitting set for multilinear depth three circuits, which is a long standing open problem in algebraic complexity theory. For instance, it can be shown that any multlinear depth three circuit with top fan-in two and just two variables per linear polynomial can be computed by an ROABP with constant width. But we show in our main result that this is not true for general multilinear depth three circuits that are superpositions of only two set-multilinear depth three circuits. There is a polynomial computed by a superposition of two set-multilinear depth 3 circuits with top fan-in just three and size polynomial in the number of variables n, such that any ROABP computing the polynomial has width 2 (n). There is a polynomial computed by a superposition of three set-multilinear depth 3 circuits with top fan-in just two and size polynomial in the number of variables n, such that any ROABP computing the polynomial has width 2 (n). This means the approach of directly converting a multilinear depth 3 circuit (even a superposi- tion of set-multilinear depth 3 circuits) to an ROABP and then applying the existing PIT for ROABP will not work. However the underlying techniques in [ASS12], [AGKS14] and [OSV15] might still be useful. The proofs of the above lower bounds are based on explicit construction of expander graphs that can be used to design multilinear depth three circuits (in particular su- perposition of set-multilinear depth 3 circuits) with high `evaluation dimension' - a complexity measure that is well suited to capture a `weakness' of ROABPs.

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. signal noise). These events and measurement errors may result in outliers in the measured surface data. The general treatment of outliers is subject to functional considerations but essential to a comprehensive characterization system is the ability to identify outliers and determine their significance on subsequent characterization. Specifically, the presence of outliers within surface data limits the robustness of conventional curve fitting algorithms and thus limits subsequent characterization fidelity.

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!