^October November – 2008 ^December

We consider scenarios where a sequence of tests is to be applied to an object, where the result of a test may be that a decision (such as classification of the object) can be made without running additional tests. Thus, one seeks an ordering of the tests that is optimal in some sense, such as minimum expected resource consumption. Such sequences of tests are commonly used in computer vision cite{Viola2001} and other applications. We examine conditions under which one can efficiently find an optimal ordering of the tests. Two types of dependencies between tests are examined: ordering constraints, and statistical dependencies. We show that with dependencies the optimization problem is NP-hard in the general case, and provide low-order polynomial time algorithms for special cases with non-trivial constraint structures. (Patent pending)

Fixed-parameter algorithms provide an alternative methodology of coping with NP-hardness that allows to solve hard optimization problems exactly and in a low-polynomial time.The necessary condition for design of a fixed- parameter algorithm is the presence of a parameter associated with the given problem. The time complexity of a fixed-parameter algorithm can be represented in a form $O(f(k)*n^c)$, where $k$ is the parameter, $f(k)$ is an exponential function on the parameter, $c$ is a constant usually not greater than 3. Thus a fixed-parameter algorithm is exponential in the parameter but polynomial in the input size. The low-polynomial time is achieved for small values of $k$.

The design of fixed-parameter algorithms was inspired by observation that in areas like bioinformatics and network design many hard problems are associated with natural parameters that in practice are very small.

Problems that admit fixed-parameter algorithms are called fixed-parameter tractable (FPT) and the area of Theoretical Computer Science studying various aspects of fixed-parameter tractability and intractability is called Parameterized Complexity. One of the key questions investigated in the area is classification of problems i.e. telling whether a particular problem is FPT. The community has identified a number of the most challenging open questions related to classification of problems. One of such questions is understanding whether the following problem is FPT: given a 2-CNF formula, is it possible to remove at most $k$ clauses so that the resulting formula becomes satisfiable? This problem is called 2-CNF deletion. It attracted attention of researchers due to a large number of potential applications of this problem. Despite a number of attempts to solve the problem, the status of fixed-parameter tractability of the problem remained unresolved for more than 10 years. The fixed-parameter tractability of the problem has been confirmed in Razgon, O'Sullivan "Almost 2-SAT is fixed-parameter tractable", ICALP 2008.

In this talk I will briefly introduce the area of Parameterized Complexity and overview main ideas of the fixed-parameter algorithm for the 2-CNF deletion problem. The talk is designed for the audience completely unfamiliar with the area of Parameterized Complexity.

Poker is a challenging problem for artificial intelligence research: multiple opponents (up to 10), stochastic element (cards being dealt), imperfect information (don't know the opponent's cards), deception (bluffing), user modeling (identifying player patterns), and risk management (betting decisions). Unlike the classic AI game, chess, poker is more relevant to real-world situations including negotiations, military strategy, and e-commerce. For over a decade, the University of Alberta Computer Poker Group has been working on building a high-performance poker program. This work has led us through multiple distinct phases of program design, each new idea "promising" to be the breakthrough to world-class play. Finally, we appear to be close. In a recent Man Versus Machine Match, University of Alberta programs narrowly defeated a team of world-class players. In this talk we will motivate the research, compare the different program designs, and discuss what it will take to raise the stakes in man-machine poker competitions.