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.