Seminars & Colloquia Calendar
Experimental Complexity Theory?
James Davenport, Univeristy of Bath, UK
Date & time: Thursday, 09 December 2021 at 5:00PM - 6:00PM
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.
password: The 20th Catalan number, alias (40)!/(20!*21!), alias 6564120420