nach oben

Foundations of Computational Mathematics

Erschienen in:

01.02.2015

A \(\tau \)-Conjecture for Newton Polygons

verfasst von: Pascal Koiran, Natacha Portier, Sébastien Tavenas, Stéphan Thomassé

Erschienen in: Foundations of Computational Mathematics | Ausgabe 1/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

One can associate to any bivariate polynomial \(P(X,Y)\) its Newton polygon. This is the convex hull of the points \((i,j)\) such that the monomial \(X^i Y^j\) appears in \(P\) with a nonzero coefficient. We conjecture that when \(P\) is expressed as a sum of products of sparse polynomials, the number of edges of its Newton polygon is polynomially bounded in the size of such an expression. We show that this so-called \(\tau \)-conjecture for Newton polygons, even in a weak form, implies that the permanent polynomial is not computable by polynomial-size arithmetic circuits. We make the same observation for a weak version of an earlier real \(\tau \)-conjecture. Finally, we make some progress toward the \(\tau \)-conjecture for Newton polygons using recent results from combinatorial geometry.

Vorheriger Artikel Degeneracy Loci and Polynomial Equation Solving

Nächster Artikel A Complexity Theory of Constructible Functions and Sheaves

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

Here and in [17], the term sparse refers to the fact that we measure the size of a polynomial \(f_{ij}\) by the number of its monomials.

M. Agrawal and V. Vinay. Arithmetic circuits: A chasm at depth four. In Proc. 49th IEEE Symposium on Foundations of Computer Science, pages 67–75, 2008.

O. Bílka, K. Buchin, R. Fulek, M. Kiyomi, Y. Okamoto, S.I. Tanigawa, and C.D. Tóth. A tight lower bound for convexly independent subsets of the Minkowski sums of planar point sets. Electr. J. Comb., 17(1), 2010.

L. Blum, F. Cucker, M. Shub, and S. Smale. Algebraic settings for the problem “\(\text{ P } \ne \text{ NP }?\)”. In J. Renegar, M. Shub, and S. Smale, editors, The Mathematics of Numerical Analysis, volume 32 of Lectures in Applied Mathematics, pages 125–144. American Mathematical Society, 1996.

L. Blum, M. Shub, and S. Smale. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bulletin of the American Mathematical Society, 21(1):1–46, July 1989.

A. Borodin and S. Cook. On the number additions to compute specific polynomials. SIAM Journal on Computing, 5(1):146–157, 1976.

P. Bürgisser. Completeness and Reduction in Algebraic Complexity Theory. Number 7 in Algorithms and Computation in Mathematics. Springer, 2000.

P. Bürgisser. On defining integers and proving arithmetic circuit lower bounds. Computational Complexity, 18:81–103, 2009. Conference version in STACS 2007.

X. Chen, N. Kayal, and A. Wigderson. Partial derivatives in arithmetic complexity and beyond. Foundations and Trends in Theoretical Computer Science, 6(1):1–138, 2011.

F. Eisenbrand, J. Pach, T. Rothvoß, and N.B. Sopher. Convexly independent subsets of the Minkowski sum of planar point sets. Electr. J. Comb., 15(1), 2008.

10.

I. Fischer. Sums of like powers of multivariate linear forms. Mathematics Magazine, 67(1):59–61, 1994.

11.

S. Gao. Absolute irreducibility of polynomials via Newton polytopes. Journal of Algebra, 237(2):501–520, 2001.

12.

A. Gupta, P. Kamath, N. Kayal, and R. Saptharishi. Arithmetic circuits: A chasm at depth three. Electronic Colloquium on Computational Complexity (ECCC), 20, 2013.

13.

N. Halman, S. Onn, and U. Rothblum. The convex dimension of a graph. Discrete Applied Mathematics, 155:1373–1383, 2007.

14.

P. Hrubeš. On the Real \(\tau \)-Conjecture and the Distribution of Complex Roots. Theory of Computing, 9(10):403–411, 2013.

15.

N. Kayal. An exponential lower bound for the sum of powers of bounded degree polynomials. Electronic Colloquium on Computational Complexity (ECCC), 19, 2012.

16.

P. Koiran. Hilbert’s Nullstellensatz is in the polynomial hierarchy. Journal of Complexity, 12(4):273–286, 1996. Long version: DIMACS report 96–27.

17.

P. Koiran. Shallow circuits with high-powered inputs. In Proc. Second Symposium on Innovations in Computer Science (ICS 2011), 2011. http://arxiv.org/abs/1004.4960

18.

P. Koiran. Arithmetic circuits: the chasm at depth four gets wider. Theoretical Computer Science, (448):56–65, 2012.

19.

A.M. Ostrowski. Über die Bedeütüng der Theorie der konvexen Polyeder für die formale Algebra. Jahresberichte Deutsche Math. Verein, 20:98–99, 1921.

20.

A. Shpilka and A. Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science, 5(3–4), 2010.

21.

M. Shub and S. Smale. On the intractability of Hilbert’s Nullstellensatz and an algebraic version of “P=NP”. Duke Mathematical Journal, 81(1):47–54, 1995.

22.

S. Smale. Mathematical problems for the next century. Mathematical Intelligencer, 20(2):7–15, 1998.

23.

B. Sturmfels. Polynomial equations and convex polytopes. The American Mathematical Monthly, 105(10):907–922, 1998.

24.

K.J. Swanepoel and P. Valtr. Large convexly independent subsets of Minkowski sums. Electr. J. Comb., 17(1), 2010.

25.

S. Tavenas. Improved bounds for reduction to depth 4 and depth 3. In Proc. 38th International Symposium on Mathematical Foundations of Computer Science (MFCS), 2013.

26.

S. Tavenas. Bornes inférieures et supérieures pour les circuits arithmétiques. PhD thesis, 2014.

27.

L. G. Valiant. Completeness classes in algebra. In Proc. 11th ACM Symposium on Theory of Computing, pages 249–261, 1979.

28.

L. G. Valiant. Reducibility by algebraic projections. In Logic and Algorithmic (an International Symposium held in honour of Ernst Specker), pages 365–380. Monographie \(n^{o}\) 30 de L’Enseignement Mathématique, 1982.

Titel: A -Conjecture for Newton Polygons
verfasst von: Pascal Koiran
Natacha Portier
Sébastien Tavenas
Stéphan Thomassé
Publikationsdatum: 01.02.2015
Verlag: Springer US
Erschienen in: Foundations of Computational Mathematics / Ausgabe 1/2015
Print ISSN: 1615-3375
Elektronische ISSN: 1615-3383
DOI: https://doi.org/10.1007/s10208-014-9216-x

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2015

Foreword

Degeneracy Loci and Polynomial Equation Solving

Probabilistic Analysis of the Grassmann Condition Number

Effect of Islands in Diffusive Properties of the Standard Map for Large Parameter Values

A Facility Location Formulation for Stable Polynomials and Elliptic Fekete Points

Overdetermined Systems of Sparse Polynomial Equations