Just a few years ago, general propositional inference beyond hundred variable problems appeared to be out of practical reach. Current reasoning engines can handle problems with over a million variables and several millions of constraints. In this talk, I will discuss what led to such a dramatic scale-up. We will see that these advances rely on a clever use of randomization and learning methods, which uncover hidden structure in practical problem instances. Work in this area has benefited from an interesting interplay between insights from statistical physics, combinatorics, and empirical algorithm design. I'll also discuss how progress in reasoning technology has opened up a range of new applications in AI and computer science in general.

Joint work with Carla Gomes (Cornell).


bio
===
Bart Selman is an associate professor of computer science at Cornell University. His current research interests include efficient reasoning procedures, stochastic search methods, knowledge compilation, planning, and connections between computer science and physics. He has received four best paper awards at the American and Canadian national artificial intelligence conferences, and at the international conference on knowledge representation. He received the Stephen Miles Excellence in Teaching Award, and a Cornell Outstanding Educator Award. He holds an NSF Career Award and is an Alfred P. Sloan Research Fellow. He is a Fellow of the American Association for Artificial Intelligence (AAAI) and a Fellow of the American Association for the Advancement of Science (AAAS).