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

Organizing Committee

A recent construction of Rojas illustrating inputs to an NP-hard problem (real feasibility) admitting polynomial-time algorithms


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

Date/Time Talk Speaker
Monday, Aug 1
9:00-9:30 Workshop Registration
9:30-10:30 Holographic Algorithms Leslie Valiant, Harvard University
10:30-11:00 Coffee Break
11:00-12:00 An Introduction to Geometric Complexity Theory Josh Grochow, University of Chicago
12:00-1:30 Break for Lunch
1:30-2:30 P = NP? Over a field (eg Z2, R, C ) Lenore Blum, Carnegie Melon
2:45-3:45 Dichotomy Theorems for Counting Problems Jin Yi Cai, University of Wisconsin
3:45-4:15 Coffee Break
4:15-5:15 Transfer Results and Number Theoretic Conjectures Peter Scheiblechner, Purdue University
5:15-6:45 Welcoming Reception
Tuesday, Aug 2
9:00-10:00 Complexity of Separational Variables Leonid Gurvits, Los Alamos National Laboratory
10:00-10:30 Coffee Break
10:30-11:30 P versus NP in the BSS-model Michael Shub, CONICET, IMAS, Universidad de Buenos Aires and CUNY Graduate School
11:45-12:45 Shallow circuits with high-powered inputs. Pascal Koiran, Ecole Normale Superieure de Lyon
12:45-2:00 Break for Lunch
2:00-3:00 Combinatorial approaches for the subgroup restriction problem. Milind Sohoni, IIT
3:15-4:15 Geometry of Orbits of Permanents and Determinants Shrawan Kumar, UNC
4:15-4:30 Coffee Break
4:30-5:30 Kronecker coefficients and the determinant
(Expository Talk)
Jerzy Weyman, Northeastern
Wednesday, Aug 3
09:00-10:00 Elementary Linear Algebra and Geometric Complexity Theory
Joseph Landsberg, Texas A&M
10:00-10:20 Coffee Break
10:20-11:20 Immanants and Complexity Theory Ke Ye, Texas A&M
11:30-12:30 Problem in geometric invariant theory arising from Geometric Complexity Theory Jerzy Weyman, Northeastern
12:30-2:00 Break for Lunch
2:00-3:00 Analogues of Toda's Theorem Thierry Zell, Lenoir-Rhyne University
Remainder of the day: outing
Thursday, Aug 4
9:00-10:00 Complexity Problems for Diophantine Equations Jeffrey Lagarias, University of Michigan
10:00-10:20 Coffee Break
10:20-11:20 Pfaffian Circuits Jason Morton, Penn State
11:30-12:30 Elliptic curves and Hilbert's Tenth Problem Kirsten Eisentrager, Penn State
12:30-2:00 Break for Lunch
2:00-3:00 Probability, Number Theory, and Computation Eric Bach, University of Wisconsin
3:15-4:15 Complexity of 4D Pascal Determinant(and Permanent) Leonid Gurvits, Los Alamos National Laboratory
4:15-4:45 Coffee Break
4:45-5:45 How Number Theory Makes Things Easier (and Harder) J. Maurice Rojas, Texas A&M
Friday, Aug 5
9:00-10:00 BSS Analogues of Valiant's Problem Saugata Basu, Purdue University
10:00-10:20 Coffee Break
10:20-11:20 Decision versus evaluation in algebraic complexity theory Pascal Koiran, Ecole Normale Superieure de Lyon
11:30-12:30 Open problems session I: GCT and BSS
12:30-2:00 Break for Lunch
2:00-3:00 Quantum algorithms for number theoretic problems Sean Hallgren, Penn State
3:00-4:00 Follow-up lecture to Thursday
(to be scheduled Thursday)
3:30-4:30 Open problems session II  
4:40-5:30 Part II: Combinatorial approaches for the subgroup restriction problem Milind Sohoni, IIT