Jason Morton

We have begun planning for a large Algebraic Statistics conference June 8-15, 2012 at Penn State. The meeting will include tutorials over the weekend followed by a week of invited and contributed talks, and a poster session. Details are on the conference website.

I'll be speaking at the inaugural ICERM topical workshop, on Mathematical Aspects of P versus NP and its Variants, which meets August 1-5, 2011. It is organized by Saugata Basu, JM Landsberg, and J Maurice Rojas. From the description:

This workshop will bring together computer scientists and mathematicians to examine the P v. NP problem and its variants from the perspectives of algebra, geometry, and number theory, and to introduce the mathematical aspects of these questions to a larger audience. Diverse researchers working on different aspects of these problems will clarify connections between different approaches.

There will be two main topics: Analogues of P v. NP (e.g., Valiant's conjectures, the Mulmuley-Sohoni Conjecture, the BSS model, and other computational models); and Algebraic, Number Theoretic, and Geometric Aspects of P v. NP (e.g., Holographic algorithms, characterizations of NP in terms of sheaf cohomology, sparse polynomials, and other arithmetic approaches).

• Susan Margulies (Rice University/Penn State)
• Location: Friday 4/22 at 12:20pm, 216 McAllister
• Hilbert's Nullstellensatz and Linear Algebra: An Algorithm for Determining Combinatorial Infeasibility

Unlike linear models, systems of multivariate polynomial equations over the complex numbers or finite fields can be compactly used to model combinatorial problems. In this way, a problem is feasible (e.g. a graph is 3-colorable, Hamiltonian, etc.) if and only if a given system of polynomial equations has a solution. In the work of M. Laurent, J. Lasserre and P. Parrilo, Y. Nesterov, and others, continuous optimization problems which are modeled by zero-dimensional radical ideals have been shown to have a finite sequence of semidefinite programs that converge to an optimal solution. For yes/no combinatorial decision problems (e.g., is a graph G 3-colorable?), we observed that Hilbert's Nullstellensatz gives a sequence of linear algebra problems that eventually determines feasibility. This has advantages as linear algebra is quite stable on computation and sparsity is well-understood.

In this talk, we present theoretical and experimental results on these sequences of large-scale, sparse, linear algebra relaxations to the combinatorial optimization problem. We show that the size of the smallest Nullstellensatz linear algebra system certifying that there is no stable set of size larger than the stability number of the graph grows as the stability number of the graph. We additionally describe ideas for optimizing the method, such as utilizing alternative forms of the Nullstellensatz, adding carefully-constructed polynomials to the system, branching and exploiting symmetry. Finally, in the case of 3-colorability, we use this method to successfully solve graph problem instances having thousands of nodes and tens of thousands of edges. Joint work with J.A De Loera, J. Lee, P.N. Malkin and S. Onn.