Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/14867Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Heintz, Joos | - |
| dc.contributor.author | KUIJPERS, Bart | - |
| dc.contributor.author | Paredes, Andres Rojas | - |
| dc.date.accessioned | 2013-03-29T10:49:04Z | - |
| dc.date.available | 2013-03-29T10:49:04Z | - |
| dc.date.issued | 2013 | - |
| dc.identifier.citation | JOURNAL OF COMPLEXITY, 29 (1), p. 92-138 | - |
| dc.identifier.issn | 0885-064X | - |
| dc.identifier.uri | http://hdl.handle.net/1942/14867 | - |
| dc.description.abstract | One may represent polynomials not only by their coefficients but also by arithmetic circuits which evaluate them. This idea allowed in the past fifteen years considerable complexity progress in effective polynomial equation solving. We present a circuit based computation model which captures all known symbolic elimination algorithms in effective Algebraic Geometry and exhibit a class of simple elimination problems which require exponential size circuits to be solved in this model. This implies that the known, circuit based elimination algorithms are already optimal. | - |
| dc.description.sponsorship | FWO G.0344.05 | - |
| dc.language.iso | en | - |
| dc.rights | Journal of Complexity copyright | - |
| dc.subject.other | Software engineering; Complexity; Algebraic Geometry; Databases | - |
| dc.title | Software Engineering and complexity in effective Algebraic Geometry | - |
| dc.type | Journal Contribution | - |
| dc.identifier.epage | 138 | - |
| dc.identifier.issue | 1 | - |
| dc.identifier.spage | 92 | - |
| dc.identifier.volume | 29 | - |
| local.bibliographicCitation.jcat | A1 | - |
| dc.relation.references | [1] A. Alder, Grenzrang und Grenzkomplexität aus algebraischer und topologischer Sicht, Ph.D. Thesis, Universität Zürich, Philosophische Fakultät II, 1984. [2] K.R.Apt,TenyearsofHoare’slogic:asurvey—partI,ACMTransactionsonProgrammingLanguagesandSystems(TOPLAS) 3 (4) (1981) 431–483. [3] László Babai, Lance Fortnow, Arithmetization: a new method in structural complexity theory, Computational Complexity 1 (1991) 41–66. [4] E.H. Bareiss, Sylvester’s identity and multistep integer-preserving Gaussian elimination, Mathematics of Computation 22 (103) (1968) 565–578. [5] R. Blanco, Complexity of Villamayor’s algorithm in the non-exceptional monomial case, International Journal of Mathematics 20 (6) (2009) 659–678. [6] T. Bloom, J.P. Calvi, A continuity property of multivariate Lagrange interpolation, Mathematics of Computation 66 (220) (1997) 1561–1577. [7] L. Blum, F. Cucker, M. Shub, S. Smale, Complexity and Real Computation, Springer-Verlag, 1998. [8] L.Blum,M.Shub,S.Smale,Onatheoryofcomputationandcomplexityovertherealnumbers:NP-completeness,recursive functions and universal machines, Bulletin of the American Mathematical Society 1 (21) (1989) 1–45. [9] P. Bürgisser, M. Clausen, M.A. Shokrollahi, Algebraic Complexity Theory, in: Grundlehren der Mathematischen Wissenschaften, vol. 315, Springer Verlag, 1997. [10] L. Caniglia, A. Galligo, J. Heintz, Some new effectivity bounds in computational geometry, in: Applied Algebra, Algebraic Algorithms and Error Correcting Codes. Proc. of the 6th Intern. Conference AAECC, Best Paper Award AAECC-6, in: Springer LNCS, vol. 357, 1989, pp. 131–151. [11] D. Castro, M. Giusti, J. Heintz, G. Matera, L.M. Pardo, The hardness of polynomial equation solving, Foundations of Computational Mathematics 3 (4) (2003) 347–420. [12] C. de Boor, A. Ron, The least solution for the polynomial interpolation problem, Mathematische Zeitschrift 210 (3) (1992) 347–378. [13] A.Dickenstein,N.Fitchas,M.Giusti,C.Sessa,Themembershipproblemofunmixedpolynomialidealsissolvableinsingle exponential time, Discrete Applied Mathematics 33 (1991) 73–94. [14] J. Edmonds, Systems of distinct representatives and linear algebra, Journal of Research. National Bureau of Standards. Section B 71 (1967) 241–245. [15] S. Encinas, O. Villamayor, A course on constructive desingularization and equivariance, in: Resolution of Singularities: A Research Textbook in Tribute to Oscar Zariski, in: Progress in Mathematics, vol. 181, 2000, pp. 147–227. [16] T. Freeman, G. Imirzian, E. Kaltofen, A system for manipulating polynomials given by straight-line programs, in: Proceedings of the Fifth ACM Symposium on Symbolic and Algebraic Computation, SYMSAC’86, ACM, 1986, pp. 169–175. [17] WilliamFulton,IntersectionTheory,in:ErgebnissederMathematikundihreGrenzgebiete,vol.2,Springer-Verlag,Berlin, 1984, 3. Folge. [18] N.Giménez,J.Heintz,G.Matera,P.Solernó,Lowercomplexityboundsforinterpolationalgorithms,JournalofComplexity 27 (2011) 151–187. [19] M. Giusti, K. Hägele, J. Heintz, J.L. Montaña, J.E. Morais, L.M. Pardo, Lower bounds for diophantine approximation, Journal of Pure and Applied Algebra 117 (1997) 277–317. [20] M. Giusti, J. Heintz, La détermination de la dimension et des points isolés d’une variété algébrique peut se faire en temps polynomial, in: D. Eisenbud, R. Robbiano (Eds.), Computational Algebraic Geometry and Commutative Algebra, in: Symposia Mathematica, vol. 34, Istituto de Alta Matematica Francesco Severi and Cambridge University Press, Cambridge, 1993, pp. 216–256. [21] M. Giusti, J. Heintz, Kronecker’s smart, little black boxes, in: R.A. DeVore, A. Iserles, E. Süli (Eds.), Foundations of Computational Mathematics, in: London Mathematical Society Lecture Note Series, vol. 284, Cambridge University Press, Cambridge, 2001, pp. 69–104. [22] M. Giusti, J. Heintz, B. Kuijpers, The evaluation of geometric queries: constraint databases and quantifier elimination, Manuscript University of Buenos Aires, 2007. http://alpha.uhasselt.be/~lucp1265/publications/sad.pdf. [23] M.Giusti,J.Heintz,J.E.Morais,J.Morgenstern,L.M.Pardo,Straight-lineprogramsingeometriceliminationtheory,Journal of Pure and Applied Algebra 124 (1998) 101–146. [24] M. Giusti, J. Heintz, J.E. Morais, L.M. Pardo, Le rôle des structures de données dans les problemes d’élimination, Comptes Rendus de l’Academie des Sciences, Serie I (325) (1997) 1223–1228. [25] M. Giusti, G. Lecerf, B. Salvy, A Gröbner free alternative for polynomial system solving, Journal of Complexity 17 (2001) 154–211. [26] R. Grimson, J. Heintz, B. Kuijpers, Evaluating geometric queries with few arithmetic operations, Manuscript University of Buenos Aires, 2011. 138 J. Heintz et al. / Journal of Complexity 29 (2013) 92–138 [27] K.Hägele,J.L.Montaña,Polynomialrandomtestfortheequivalenceofintegersgivenbyarithmeticcircuits,Preprint4/97, Departamento de Matemática, Estadística y Computación, Universidad de Cantabria, 1997. [28] J. Harris, Algebraic Geometry: A First Course, second ed., Springer Verlag, 1992. [29] J.Heintz,Definabilityandfastquantifiereliminationinalgebraicallyclosedfields,TheoreticalComputerScience24(1983) 239–277. [30] J. Heintz, On the computational complexity of polynomials and bilinear mappings. A survey, in: Proceedings 5th International Symposium on Applied Algebra, Algebraic Algorithms and Error Correcting Codes, in: Springer LNCS, vol. 356, 1989, pp. 269–300. [31] J. Heintz, B. Kuijpers, Constraint databases, data structures and efficient query evaluation, in: Constraint Databases. First International Symposium, in: Springer LNCS, vol. 3074, 2004, pp. 1–24. [32] J.Heintz,G.Matera,L.M.Pardo,R.Wachenchauzer,Theintrinsiccomplexityofparametriceliminationmethods,Electronic Journal of SADIO 1 (1998) 37–51. [33] J. Heintz, J. Morgenstern, On the intrinsic complexity of elimination theory, Journal of Complexity 9 (1993) 471–498. [34] J. Heintz, C.P. Schnorr, Testing polynomials which are easy to compute, in: International Symposium on Logic and Algorithmic, in: Monogr. Enseig. Math., vol. 30, 1982, pp. 237–254. and 12th Annual Symposium ACM on Theory of Computing (STOC’80) ACM Press, 262–272, 1980. [35] J. Heintz, M. Sieveking, Absolute primality of polynomials is decidable in random polynomial time in the number of variables, in: S. Even, O. Kariv (Eds.), International Colloquium on Automata, Languages and Programming ICALP, in: Lecture Notes in Computer Science, vol. 115, Springer, 1981, pp. 16–28. [36] B. Iversen, Generic Local Structure of the Morphisms in Commutative Algebra, Springer-Verlag, Berlin, 1973. [37] V.Kabanets,R.Impagliazzo,Derandomizingpolynomialidentitytestsmeansprovingcircuitlowerbounds,Computational Complexity 1–2 (13) (2004) 1–46. [38] E. Kaltofen, Greatest common divisors of polynomials given by straight-line programs, Journal of the ACM 35 (1) (1988) 231–264. [39] T. Krick, L.M. Pardo, A computational method for diophantine approximation, in: Algorithms in Algebraic Geometry and Applications. Proceedings of MEGA’94, in: Progress in Mathematics, vol. 143, 1996, pp. 193–254. [40] E. Kunz, Introduction to Commutative Algebra and Algebraic Geometry, Birkhäuser, Boston, 1985. [41] S. Lang, Algebra, Addison-Wesley, Massachusetts, 1993. [42] T.M. Lickteig, On semialgebraic decision complexity, Habilitationsschrift, Universität Tübingen TR-90-052, Int. Comp. Sc. Inst., Berkeley, 1990. [43] R.J.Lipton,Straight-linecomplexityandintegerfactorization,in:AlgorithmicNumberTheory,in:SpringerLNCS,vol.877, 1994, pp. 71–79. [44] C. Lund, L. Fortnow, H. Karloff, N. Nisan, Algebraic methods for interactive proof systems, Journal of the ACM 39 (1992) 859–868. [45] B. Meyer, Object-Oriented Software Construction, second ed., Prentice-Hall, 2000. [46] T. Mora, SPES I: The Kronecker–Duval Philosophy, Cambridge University Press, 2003. [47] T. Mora, SPES II: Macaulay’s Paradigm and Groebner Technology, Cambridge University Press, 2005. [48] K.Mulmuley,Afastparallelalgorithmtocomputetherankofamatrixoveranarbitraryfield,Combinatorica7(1)(1987) 101–104. [49] D. Mumford, The Red Book of Varieties and Schemes, first ed., vol. 1358, Springer, Berlin, Heidelberg, New York, 1988. [50] P. Olver, On multivariate interpolation, Studies in Applied Mathematics 116 (2) (2006) 201–240. [51] M.S. Paterson, L.J. Stockmeyer, On the number of nonscalar multiplications necessary to evaluate polynomials, SIAM Journal on Computing 2 (1973) 60–66. [52] N. Saxena, Progress on polynomial identity testing, Bulletin of the EATCS 90 (2009) 49–79. [53] I.R. Shafarevich, Basic Algebraic Geometry: Varieties in Projective Space, Springer, Berlin, Heidelberg, New York, 1994. [54] A. Shamir, IP = PSPACE, Journal of the ACM 39 (1992) 869–877. [55] A. Shpilka, Arithmetic circuits: a survey of recent results and open questions, Foundations and Trends in Theoretical Computer Science 5 (3–4) (2010) 207–388. [56] M.Shub,S.Smale,OntheintractabilityofHilbert’sNullstellensatzandanalgebraicversionofNP̸=P?DukeMathematical Journal 81 (1995) 47–54. [57] V. Strassen, Vermeidung von Divisionen, Crelle Journal für die Reine und Angewandte Mathematik 264 (1973) 182–202. [58] W. Vogel, Results on Bézout’s Theorem, in: Tata Institute of Fundamental Research, Springer, 1984. [59] O. Zariski, P. Samuel, Commutative Algebra II, vol. 39, Springer, New York, 1960. | - |
| local.type.refereed | Refereed | - |
| local.type.specified | Article | - |
| local.relation.fp7 | 245410 | - |
| dc.identifier.doi | 10.1016/j.jco.2012.04.005 | - |
| dc.identifier.isi | 000313312400006 | - |
| item.fulltext | With Fulltext | - |
| item.accessRights | Restricted Access | - |
| item.fullcitation | Heintz, Joos; KUIJPERS, Bart & Paredes, Andres Rojas (2013) Software Engineering and complexity in effective Algebraic Geometry. In: JOURNAL OF COMPLEXITY, 29 (1), p. 92-138. | - |
| item.validation | ecoom 2014 | - |
| item.contributor | Heintz, Joos | - |
| item.contributor | KUIJPERS, Bart | - |
| item.contributor | Paredes, Andres Rojas | - |
| crisitem.journal.issn | 0885-064X | - |
| crisitem.journal.eissn | 1090-2708 | - |
| Appears in Collections: | Research publications | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| JoComplexity-2013.pdf Restricted Access | Published version | 466.31 kB | Adobe PDF | View/Open Request a copy |
SCOPUSTM
Citations
6
checked on Sep 3, 2020
WEB OF SCIENCETM
Citations
8
checked on May 8, 2024
Page view(s)
118
checked on Sep 5, 2022
Download(s)
112
checked on Sep 5, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.