Mostrar el registro sencillo del ítem
dc.contributor.author
Gimenez, Nardo Ariel
dc.contributor.author
Matera, Guillermo
dc.date.available
2022-01-03T14:54:41Z
dc.date.issued
2019-04
dc.identifier.citation
Gimenez, Nardo Ariel; Matera, Guillermo; On the bit complexity of polynomial system solving; Academic Press Inc Elsevier Science; Journal Of Complexity; 51; 4-2019; 20-67
dc.identifier.issn
0885-064X
dc.identifier.uri
http://hdl.handle.net/11336/149498
dc.description.abstract
We describe and analyze a randomized algorithm which solves a polynomial system over the rationals defined by a reduced regular sequence outside a given hypersurface. We show that its bit complexity is roughly quadratic in the Bézout number of the system and linear in its bit size. The algorithm solves the input system modulo a prime number p and applies p-adic lifting. For this purpose, we establish a number of results on the bit length of a “lucky” prime p, namely one for which the reduction of the input system modulo p preserves certain fundamental geometric and algebraic properties of the original system. These results rely on the analysis of Chow forms associated to the set of solutions of the input system and effective arithmetic Nullstellensätze.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
Academic Press Inc Elsevier Science
dc.rights
info:eu-repo/semantics/openAccess
dc.rights.uri
https://creativecommons.org/licenses/by-nc-nd/2.5/ar/
dc.subject
BIT COMPLEXITY
dc.subject
CHOW FORM
dc.subject
LIFTING FIBERS
dc.subject
LUCKY PRIMES
dc.subject
POLYNOMIAL SYSTEM SOLVING OVER Q
dc.subject
REDUCED REGULAR SEQUENCE
dc.subject.classification
Matemática Pura
dc.subject.classification
Matemáticas
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
dc.subject.classification
Matemática Aplicada
dc.subject.classification
Matemáticas
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
dc.title
On the bit complexity of polynomial system solving
dc.type
info:eu-repo/semantics/article
dc.type
info:ar-repo/semantics/artículo
dc.type
info:eu-repo/semantics/publishedVersion
dc.date.updated
2022-01-03T13:59:21Z
dc.identifier.eissn
1090-2708
dc.journal.volume
51
dc.journal.pagination
20-67
dc.journal.pais
Estados Unidos
dc.description.fil
Fil: Gimenez, Nardo Ariel. Universidad Nacional de General Sarmiento. Instituto del Desarrollo Humano; Argentina
dc.description.fil
Fil: Matera, Guillermo. Universidad Nacional de General Sarmiento. Instituto del Desarrollo Humano; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina
dc.journal.title
Journal Of Complexity
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S0885064X18300761
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/https://doi.org/10.1016/j.jco.2018.09.005
Archivos asociados