Seminar Details
Experimental Complexity Theory?
- Start Date: December 9, 2021
- Event Start Time: 5:00 PM
- Event End Time: 6:00 PM
- Seminar Series: Experimental Math Seminar
- Presenter(s): James Davenport - University of Bath
- Event Location: Online Event
- Event Additional Info: <p>Presented Via Zoom: <a href="https://rutgers.zoom.us/j/94346444480">https://rutgers.zoom.us/j/94346444480</a></p> <p>Password: 6564120420</p> <p>For further information see: <a href="https://sites.math.rutgers.edu/~zeilberg/expmath/">https://sites.math.rutgers.edu/~zeilberg/expmath/</a></p>
- Presentation Type: Stand Alone Presentation
- 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