Department of Mathematics

Distinguished Undergraduate Lecture Series

  •  The blessings and curses of complexity
  •  04/15/2017
  •  4:10 PM - 5:00 PM
  •  C304 Wells Hall
  •  Olga V. Holtz, University of California, Berkeley

Ever since the invention of the first algorithms, mathematicians wondered how 'complex' such computational procedures are. This talk will offer an excursion into the world of complexity. How fast can we determine if a given number is prime, find the greatest common divisor of two polynomials, or multiply two matrices? What problems are solvable in polynomial time? What are randomized algorithms and how complex are they? What is communication complexity? And why should we care whether or not P equals NP?



Department of Mathematics
Michigan State University
619 Red Cedar Road
C212 Wells Hall
East Lansing, MI 48824

Phone: (517) 353-0844
Fax: (517) 432-1562

College of Natural Science