Where the hard computational problems are ?
Speakers: Tao Xie
Topic(s): Artificial Language/Machine Learning
Some computational problems are easy. We can sort numbers quickly for example. Other problems are hard. Scheduling jobs, routing trucks, these are all hard problems to solve. I will survey research in Artificial Intelligence that helps find where hard computational problems can be found, and throws some light on what makes some problems hard and others easy. Computational complexity gives us some tools (for example, big O analysis and complexity classes) but much of my talk will come from an unusual direction - statistical mechanics. Surprisingly, phase transition behaviour observed in nature is also observed in computation, and problem hardness can often be found at phase boundaries. The talk will be richly illustrated with many examples of such behaviour.
About this Lecture
Number of Slides: 45
Duration: 45 - 60 minutes
Languages Available: English
Last Updated: 05-01-2017
Request this Lecture
To request this particular lecture, please complete this online form.
Request a Tour
To request a tour with this speaker, please complete this online form.
All requests will be sent to ACM headquarters for review.