Seminars & Colloquia Calendar

Download as iCal file

Experimental Mathematics Seminar

Experimental Complexity Theory?

James Davenport, Univeristy of Bath, UK

Location:  Zoom
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.

Zoom Link: https://rutgers.zoom.us/j/94346444480
password: The 20th Catalan number, alias (40)!/(20!*21!), alias 6564120420

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.