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