ACM Distinguished Speakers Program:  talks by and with technology leaders and innovators

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.
Featured Speaker

Keith Cheverst
Lancaster University

Get Involved!
Help improve the DSP by nominating a speaker or providing feedback to ACM.