MATH Seminar

Title: On the complexity of factoring polynomials over finite fields
Colloquium: N16
Speaker: Kiran Kedlaya of
Contact: Aaron Abrams, abrams@mathcs.emory.edu
Date: 2009-02-24 at 4:00PM
Venue: MSC W201
Download Flyer
Abstract: Abstract: While factoring large polynomials over finite fields is (apparently) far easier than factoring large integers, it is still an open problem to give an algorithm that does it ``as fast as possible'' (roughly speaking, in time proportional to the length of the input data). We will explain a recent improvement in the complexity of factoring polynomials over finite fields, based on an asymptotically optimal solution of a related problem (the modular composition problem). Joint work with Chris Umans (Caltech).