GOING BEYOND NP: NEW CHALLENGES IN INFERENCE TECHNOLOGY
BART SELMAN
Department of Computer Science, Cornell University
In recent years, we have seen tremendous progress in inference
technologies. For example, in the area of Boolean satisfiability (SAT) and
Mixed Integer Programming (MIP) solvers now enable us to tackle
significant practical problem instances with up to a million variables and
constraints. Key to this success is the ability to strike the right
balance between the expressiveness of the underlying representation
formalism and the efficiency of the solvers. The next challenge is to
extend the reach of these solvers to more complex tasks that lie beyond
NP. I will discuss our work on sampling, counting, probabilistic
reasoning, and adversarial reasoning. In particular, I will discuss a new
sampling technique based on the so-called flat histogram method, from
statistical physics. The technique allows for fast probabilistic inference
and learning in Markov Logic networks and other graphical models. In the
area of adversarial reasoning, the UCT method, based on sampling
strategies first developed for use in multi-armed bandit scenarios,
provides a compelling alternative to traditional minimax search. The
method has led to an exciting advance in the strength of GO programs. I
will discuss insights into the surprising effectiveness of the UCT technique.
BIO
Bart Selman is a professor of computer science at Cornell University. His
research interests include efficient reasoning procedures, planning,
knowledge representation, and connections between computer science and
statistical physics. He has (co-)authored over 150 papers, which have
appeared in venues spanning Nature, Science, Proc. Natl. Acad. of Sci.,
and a variety of conferences and journals in AI and Computer Science. He
has received six Best Paper Awards, and is an Alfred P. Sloan Research
Fellowship recipient, a Fellow of AAAI, and a Fellow of AAAS.