×

Ulrich complexity. (English) Zbl 1521.68070

Summary: In this note we suggest a new measure of the complexity of polynomials, the Ulrich complexity. Valiant’s conjecture on the exponential complexity of the permanent would imply exponential behavior of the Ulrich complexity as well, and this may be easier to prove. We compute some families of examples, one of which has provably exponential behavior.

MSC:

68Q25 Analysis of algorithms and problem complexity
13B25 Polynomials over commutative rings
13H10 Special types (Cohen-Macaulay, Gorenstein, Buchsbaum, etc.)
14M05 Varieties defined by ring conditions (factorial, Cohen-Macaulay, seminormal)
68Q06 Networks and circuits as models of computation; circuit complexity
68W30 Symbolic computation and algebraic computation

Software:

Macaulay2
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alper, Jarod; Bogart, Tristram; Velasco, Mauricio, A lower bound for the determinantal complexity of a hypersurface (2015), preprint · Zbl 1375.14201
[2] Backelin, Jörgen; Herzog, Jürgen, On Ulrich-modules over hypersurface rings, (Commutative Algebra. Commutative Algebra, Berkeley, CA, 1987. Commutative Algebra. Commutative Algebra, Berkeley, CA, 1987, Math. Sci. Res. Inst. Publ., vol. 15 (1989), Springer: Springer New York), 63-68, MR1015513 (90i:13006) · Zbl 0733.13013
[3] Backelin, Jörgen; Herzog, Jürgen; Sanders, Herbert, Matrix factorizations of homogeneous polynomials, (Algebra—Some Current Trends. Algebra—Some Current Trends, Varna, 1986. Algebra—Some Current Trends. Algebra—Some Current Trends, Varna, 1986, Lecture Notes in Math., vol. 1352 (1988), Springer: Springer Berlin), 1-33, MR981815 · Zbl 0668.13009
[4] Beauville, Arnaud, Determinantal hypersurfaces, Mich. Math. J., 48, 39-64 (2000) · Zbl 1076.14534
[5] Beauville, Arnaud, Ulrich bundles on abelian surfaces (2015), preprint · Zbl 1375.14148
[6] Brennan, Joseph P.; Herzog, Jürgen; Ulrich, Bernd, Maximally generated Cohen-Macaulay modules, Math. Scand., 61, 2, 181-203 (1987), MR947472 (89j:13027) · Zbl 0653.13015
[7] Buchweitz, Ragnar-Olaf; Greuel, Gert-Martin; Schreyer, Frank-Olaf, Cohen-Macaulay modules on hypersurface singularities. II, Invent. Math., 88, 1, 165-182 (1987) · Zbl 0617.14034
[8] Brent, R. P.; Kung, H. T., Fast algorithms for manipulating formal power series, J. Assoc. Comput. Mach., 25, 4, 581-595 (1978), MR0520733 · Zbl 0388.68052
[9] Buchweitz, Ragnar-Olaf; Eisenbud, David; Herzog, Jürgen, Cohen-Macaulay modules on quadrics, (Singularities, Representation of Algebras, and Vector Bundles. Singularities, Representation of Algebras, and Vector Bundles, Lambrecht, 1985. Singularities, Representation of Algebras, and Vector Bundles. Singularities, Representation of Algebras, and Vector Bundles, Lambrecht, 1985, Lecture Notes in Math., vol. 1273 (1987), Springer: Springer Berlin), 58-116 · Zbl 0633.13008
[10] Bürgisser, Peter; Clausen, Michael; Shokrollahi, M. Amin, Algebraic Complexity Theory, Grundlehren der Mathematischen Wissenschaften, vol. 315 (1997), Springer-Verlag: Springer-Verlag Berlin, With the collaboration of Thomas Lickteig. MR1440179 · Zbl 1087.68568
[11] Bürgisser, Peter, Completeness and Reduction in Algebraic Complexity Theory, Algorithms and Computation in Mathematics, vol. 7 (2000), Springer-Verlag: Springer-Verlag Berlin, MR1771845 · Zbl 0948.68082
[12] Childs, Lindsay N., Linearizing of \(n\)-ic forms and generalized Clifford algebras, Linear Multilinear Algebra, 5, 4, 267-278 (1977/78), MR0472880 (57 #12567) · Zbl 0385.15012
[13] Eisenbud, David, Homological algebra on a complete intersection, with an application to group representations, Trans. Am. Math. Soc., 260, 1, 35-64 (1980) · Zbl 0444.13006
[14] Eisenbud, David, Commutative Algebra with a View Toward Algebraic Geometry, Graduate Texts in Mathematics, vol. 150 (1995), Springer-Verlag: Springer-Verlag New York · Zbl 0819.13001
[15] Eisenbud, David; Schreyer, Frank-Olaf, Betti numbers of graded modules and cohomology of vector bundles, J. Am. Math. Soc., 22, 3, 859-888 (2009), MR2505303 (2011a:13024) · Zbl 1213.13032
[16] Eisenbud, David; Schreyer, Frank-Olaf; Weyman, Jerzy, Resultants and Chow forms via exterior syzygies, J. Am. Math. Soc., 16, 3, 537-579 (2003), MR1969204 (2004j:14067) · Zbl 1069.14019
[17] Bruno Grenet, An upper bound for the permanent versus determinant problem, preprint, 2011.; Bruno Grenet, An upper bound for the permanent versus determinant problem, preprint, 2011.
[18] Grothendieck, Alexander, Cohomologie locale des faisceaux cohérents et théorèmes de Lefschetz locaux et globaux (SGA 2), Documents Mathématiques (Paris), vol. 4 (2005), Société Mathématique de France: Société Mathématique de France Paris, (French). Séminaire de Géométrie Algébrique du Bois Marie, 1962; Augmenté d’un exposé de Michèle Raynaud [With an exposé by Michèle Raynaud]; With a preface and edited by Yves Laszlo; Revised reprint of the 1968 French original. MR2171939 · Zbl 1079.14001
[19] Grigoriev, Dima; Karpinski, Marek, An exponential lower bound for depth 3 arithmetic circuits, (STOC ’98. STOC ’98, Dallas, TX (1999), ACM: ACM New York), 577-582, MR1715606 · Zbl 1028.68069
[20] Grigoriev, D.; Razborov, A., Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields, Appl. Algebra Eng. Commun. Comput., 10, 6, 465-487 (2000), MR1770876 · Zbl 1040.68045
[21] Herzog, J.; Ulrich, B.; Backelin, J., Linear maximal Cohen-Macaulay modules over strict complete intersections, J. Pure Appl. Algebra, 71, 2-3, 187-202 (1991), MR1117634 · Zbl 0734.13007
[22] Jacobson, Nathan, Basic Algebra. II (1989), W. H. Freeman and Company: W. H. Freeman and Company New York, MR1009787 · Zbl 0694.16001
[23] Knörrer, Horst, Cohen-Macaulay modules on hypersurface singularities. I, Invent. Math., 88, 1, 153-164 (1987) · Zbl 0617.14033
[24] Landsberg, J. M., Tensors: Geometry and Applications, Graduate Studies in Mathematics, vol. 128 (2012), American Mathematical Society: American Mathematical Society Providence, RI, MR2865915 · Zbl 1238.15013
[25] Mignon, Thierry; Ressayre, Nicolas, A quadratic bound for the determinant and permanent problem, Int. Math. Res. Not., 79, 4241-4253 (2004), MR2126826 (2006b:15015) · Zbl 1081.15003
[26] Grayson, Daniel R.; Stillman, Michael E., Macaulay2, a software system for research in algebraic geometry, Available at
[27] Shpilka, Amir; Yehudayoff, Amir, Arithmetic circuits: a survey of recent results and open questions, Found. Trends Theor. Comput. Sci., 5, 3-4, 207-388 (2010), MR2756166 · Zbl 1205.68175
[28] Ulrich, Bernd, Gorenstein rings and modules with high numbers of generators, Math. Z., 188, 1, 23-32 (1984), MR767359 (85m:13021) · Zbl 0573.13013
[29] Valiant, L. G., Completeness classes in algebra, (Conference Record of the Eleventh Annual ACM Symposium on Theory of Computing. Conference Record of the Eleventh Annual ACM Symposium on Theory of Computing, Atlanta, Ga., 1979 (1979), ACM: ACM New York), 249-261, MR564634
[30] Valiant, L. G., The complexity of computing the permanent, Theor. Comput. Sci., 8, 2, 189-201 (1979), MR526203 (80f:68054) · Zbl 0415.68008
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.