Standard
Polynomial-time presentations of algebraic number fields. / Alaev, Pavel; Selivanov, Victor.
Sailing Routes in the World of Computation - 14th Conference on Computability in Europe, CiE 2018, Proceedings. ed. / F Manea; RG Miller; D Nowotka. Springer-Verlag GmbH and Co. KG, 2018. p. 20-29 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10936 LNCS).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Harvard
Alaev, P & Selivanov, V 2018,
Polynomial-time presentations of algebraic number fields. in F Manea, RG Miller & D Nowotka (eds),
Sailing Routes in the World of Computation - 14th Conference on Computability in Europe, CiE 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10936 LNCS, Springer-Verlag GmbH and Co. KG, pp. 20-29, 14th Conference on Computability in Europe, CiE 2018, Kiel, Germany,
30.07.2018.
https://doi.org/10.1007/978-3-319-94418-0_2
APA
Vancouver
Alaev P, Selivanov V.
Polynomial-time presentations of algebraic number fields. In Manea F, Miller RG, Nowotka D, editors, Sailing Routes in the World of Computation - 14th Conference on Computability in Europe, CiE 2018, Proceedings. Springer-Verlag GmbH and Co. KG. 2018. p. 20-29. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-94418-0_2
Author
Alaev, Pavel ; Selivanov, Victor. /
Polynomial-time presentations of algebraic number fields. Sailing Routes in the World of Computation - 14th Conference on Computability in Europe, CiE 2018, Proceedings. editor / F Manea ; RG Miller ; D Nowotka. Springer-Verlag GmbH and Co. KG, 2018. pp. 20-29 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
BibTeX
@inproceedings{86d76e5fd0d945599f407b5a8d34e6b4,
title = "Polynomial-time presentations of algebraic number fields",
abstract = "Using an extension of the notion of polynomial time presentable structure we show that some natural presentations of the ordered field ℝalg of algebraic reals and of the field ℂalg of algebraic complex numbers are polynomial-time equivalent to each other and are polynomial time. We also establish upper complexity bounds for the problem of rational polynomial evaluation in ℂalg and for the problem of root-finding for polynomials in ℂalg[x] which improve the previously known bound.",
keywords = "Algebraic number, Complexity bound, Ordered field, Polynomial, Polynomial-time presentable structure",
author = "Pavel Alaev and Victor Selivanov",
year = "2018",
month = jan,
day = "1",
doi = "10.1007/978-3-319-94418-0_2",
language = "English",
isbn = "9783319944173",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag GmbH and Co. KG",
pages = "20--29",
editor = "F Manea and RG Miller and D Nowotka",
booktitle = "Sailing Routes in the World of Computation - 14th Conference on Computability in Europe, CiE 2018, Proceedings",
address = "Germany",
note = "14th Conference on Computability in Europe, CiE 2018 ; Conference date: 30-07-2018 Through 03-08-2018",
}
RIS
TY - GEN
T1 - Polynomial-time presentations of algebraic number fields
AU - Alaev, Pavel
AU - Selivanov, Victor
PY - 2018/1/1
Y1 - 2018/1/1
N2 - Using an extension of the notion of polynomial time presentable structure we show that some natural presentations of the ordered field ℝalg of algebraic reals and of the field ℂalg of algebraic complex numbers are polynomial-time equivalent to each other and are polynomial time. We also establish upper complexity bounds for the problem of rational polynomial evaluation in ℂalg and for the problem of root-finding for polynomials in ℂalg[x] which improve the previously known bound.
AB - Using an extension of the notion of polynomial time presentable structure we show that some natural presentations of the ordered field ℝalg of algebraic reals and of the field ℂalg of algebraic complex numbers are polynomial-time equivalent to each other and are polynomial time. We also establish upper complexity bounds for the problem of rational polynomial evaluation in ℂalg and for the problem of root-finding for polynomials in ℂalg[x] which improve the previously known bound.
KW - Algebraic number
KW - Complexity bound
KW - Ordered field
KW - Polynomial
KW - Polynomial-time presentable structure
UR - http://www.scopus.com/inward/record.url?scp=85051111244&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-94418-0_2
DO - 10.1007/978-3-319-94418-0_2
M3 - Conference contribution
AN - SCOPUS:85051111244
SN - 9783319944173
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 20
EP - 29
BT - Sailing Routes in the World of Computation - 14th Conference on Computability in Europe, CiE 2018, Proceedings
A2 - Manea, F
A2 - Miller, RG
A2 - Nowotka, D
PB - Springer-Verlag GmbH and Co. KG
T2 - 14th Conference on Computability in Europe, CiE 2018
Y2 - 30 July 2018 through 3 August 2018
ER -
