Mathematical Aspects of P versus NP and its Variants (August 1-5, 2011)

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).

The workshop will emphasize the "work" aspect, so there will be few scheduled lectures, with extensive discussion periods, and follow-up lectures scheduled impromptu as needed.

P vs NP Report: Published Paper Link to Abstracts

Video Archive

Dates	Title	Organizers
August 1-5, 2011	Mathematical Aspects of P versus NP and its Variants	Saugata Basu, JM Landsberg, J Maurice Rojas

Video Links
Description	Speaker	Video	Abstract	Slides
BSS Analogues of Valiant's Problem	Saugata Basu, Purdue University
Elementary Linear Algebra and Geometric Complexity Theory	Joseph Landsberg, Texas A&M
Decision versus evaluation in algebraic complexity theory	Pascal Koiran, Ecole Normale Superieure de Lyon
Kronecker coefficients and the determinant (Expository Talk)	Jerzy Weyman, Northeastern
Combinatorial approaches for the subgroup restriction problem	Milind Sohoni, IIT
Pfaffian Circuits	Jason Morton, Penn State
Transfer Results and Number Theoretic Conjectures	Peter Scheiblechner, Purdue University
How Number Theory Makes Thigns easier (and Harder)	J. Maurice Rojas, Texas A&M
P versus NP in the BSS-model	Michael Shub, CONICET, IMAS, Universidad de Buenos Aires and CUNY Graduate School
Elliptic curves and Hilbert's Tenth Problem	Kirsten Eisentrager, Penn State
Problem in geometric invariant theory arising from Geometric Compexity Theory	Jerzy Weyman, Northeastern
Geometry of Orbits of Permanents and Determinants	Shrawan Kumar, UNC
Shallow circuits with high-powered inputs	Pascal Koiran, Ecole Normale Superieure de Lyon
An Introduction to Geometric Complexity Theory	Josh Grochow, University of Chicago
Dichotomy Theorems for Counting Problems	Jin Yi Cai, University of Wisconsin
Analogues of Toda's Theorem	Thierry Zell, Lenoir-Rhyne University
Complexity Problems for Diophantine Equations	Jeffrey Lagarias, University of Michigan