TY - CHAP
TI - Polynomial-time factorization of multivariate polynomials over finite fields
AU - von zur Gathen, J.
AU - Kaltofen, E.
T2 - Automata, Languages and Programming
T3 - Lecture Notes in Computer Science
AB - We present a probabilistic algorithm that finds the irreducible factors of a bivariate polynomial with coefficients from a finite field in time polynomial in the input size, i.e. in the degree of the polynomial and log (cardinality of field). The algorithm generalizes to multivariate polynomials and has polynomial running time for densely encoded inputs. Also a deterministic version of the algorithm is discussed whose running time is polynomial in the degree of the input polynomial and the size of the field.
PY - 1983///
DO - 10.1007/bfb0036913
SP - 250–263
PB - Springer
SN - 9783540123170 9783540400387
SV - 154
UR - http://dx.doi.org/10.1007/bfb0036913
ER -
TY - JOUR
TI - A Generalized Class of Polynomials that are Hard to Factor
AU - Kaltofen, Erich
AU - Musser, David R.
AU - Saunders, B. David
T2 - SIAM Journal on Computing
AB - A class of univariate polynomials is defined which make the Berlekamp-Hensel factorization algorithm take an exponential amount of time. This class contains as subclasses the Swinnerton-Dyer polynomials discussed by Berlekamp and a subset of the cyclotomic polynomials. Aside from shedding light on the complexity of polynomial factorization this class is also useful in testing implementations of the Berlekamp–Hensel and related algorithms.
DA - 1983/8//
PY - 1983/8//
DO - 10.1137/0212031
VL - 12
IS - 3
SP - 473-483
J2 - SIAM J. Comput.
LA - en
OP -
SN - 0097-5397 1095-7111
UR - http://dx.doi.org/10.1137/0212031
DB - Crossref
ER -
TY - CHAP
TI - On the complexity of finding short vectors in integer lattices
AU - Kaltofen, Erich
T2 - Lecture Notes in Computer Science
AB - In [Lenstra, A., et al. 82] an algorithm is presented which, given n linearly independent n-dimensional integer vectors, calculates a vector in the integer lattice spanned by these vectors whose Euclidean length is within a factor of 2(n−1)/2 of the length of the shortest vector in this lattice. If B denotes the maximum length of the basis vectors, the algorithm is shown to run in O(n 6(log B)3) binary steps. We prove that this algorithm can actually be executed in O(n 6(log B)2+n 5(log B)3) binary steps by analyzing a modified version of the algorithm which also performs better in practice.KeywordsBinary ComplexityInteger LatticeInteger MultiplicationEuclidean LengthShort VectorThese keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
PY - 1983///
DO - 10.1007/3-540-12868-9_107
SP - 236-244
OP -
PB - Springer Berlin Heidelberg
SN - 9783540128687 9783540387565
UR - http://dx.doi.org/10.1007/3-540-12868-9_107
DB - Crossref
ER -
TY - JOUR
TI - Admissible State Semantics for Representational Systems
AU - Doyle, J.
T2 - Computer
AB - Several authors have proposed specifying semantics for representational systems by translating them into logic. Unfortunately, such translations often introduce unnecessary detail and complexity. We indicate how many kinds of informal semantics can be transformed directly into formal semantics of no greater complexity. The key to avoiding the difficulties of logical translations is to recognize the difference between internal and external meanings.
DA - 1983///
PY - 1983///
DO - 10.1109/MC.1983.1654209
VL - 16
IS - 10
SP - 119-123
UR - http://www.scopus.com/inward/record.url?eid=2-s2.0-0020833068&partnerID=MN8TOARS
ER -
TY - CONF
TI - SOCIETY OF MIND - MULTIPLE PERSPECTIVES, REASONED ASSUMPTIONS, AND VIRTUAL COPIES.
AU - Doyle, Jon
C2 - 1983///
DA - 1983///
VL - 1
SP - 309-314
UR - http://www.scopus.com/inward/record.url?eid=2-s2.0-0020892425&partnerID=MN8TOARS
ER -
TY - CONF
TI - INS AND OUTS OF REASON MAINTENANCE.
AU - Doyle, Jon
C2 - 1983///
DA - 1983///
VL - 1
SP - 349-351
UR - http://www.scopus.com/inward/record.url?eid=2-s2.0-0020909766&partnerID=MN8TOARS
ER -
TY - THES
TI - AN AUGMENTING PATHS ALGORITHM FOR THE MATROID PARITY PROBLEM ON BINARY MATROIDS.
AU - Stallmann, Matthias Friedemann Martin
DA - 1983///
PY - 1983///
PB - University of Colorado, Boulder
ER -