James Davenport, University of Bath

Abstract

Complexity theory is generally a two-handed piece between the upper bound O(f(n)) algorithm designers and the lower bound Ω(f(n)) example builders. If they agree, we're in Θ(f(n)) paradise. Implicit in this is "worst case''. Only rarely does "average case'' complexity get mentioned, not least because even defining "average case'' is hard. What the user of an algorithm is really interested in, of course, is "complexity on my problems''. Failing this, we could at least ask for "complexity on typical problems'', which raises "what is typical''. This is normally answered by having a collection of typical problems, something many fields (e.g. my own computer algebra) are pretty poor at. I will contrast this with the situation in SAT-solving, and finish with some ideas for the future.

Link to video:https://vimeo.com/658021480

Presented Via Zoom: https://rutgers.zoom.us/j/94346444480

Password: 6564120420

For further information see: https://sites.math.rutgers.edu/~zeilberg/expmath/