Mathematical Aspects of P versus NP and its Variants (August 15, 2011)
 Saugata Basu
(Purdue University)  JM Landsberg
(Texas A&M University)  J Maurice Rojas
(Texas A&M University)
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 MulmuleySohoni 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 followup lectures scheduled impromptu as needed.
P vs NP Report: Published Paper
Link to Abstracts


Date/Time  Talk  Speaker 
Monday, Aug 1  
9:009:30  Workshop Registration  
9:3010:30  Holographic Algorithms  Leslie Valiant, Harvard University 
10:3011:00  Coffee Break  
11:0012:00  An Introduction to Geometric Complexity Theory  Josh Grochow, University of Chicago 
12:001:30  Break for Lunch  
1:302:30  P = NP? Over a field (eg Z2, R, C )  Lenore Blum, Carnegie Melon 
2:453:45  Dichotomy Theorems for Counting Problems  Jin Yi Cai, University of Wisconsin 
3:454:15  Coffee Break  
4:155:15  Transfer Results and Number Theoretic Conjectures  Peter Scheiblechner, Purdue University 
5:156:45  Welcoming Reception  
Tuesday, Aug 2  
9:0010:00  Complexity of Separational Variables  Leonid Gurvits, Los Alamos National Laboratory 
10:0010:30  Coffee Break  
10:3011:30  P versus NP in the BSSmodel  Michael Shub, CONICET, IMAS, Universidad de Buenos Aires and CUNY Graduate School 
11:4512:45  Shallow circuits with highpowered inputs.  Pascal Koiran, Ecole Normale Superieure de Lyon 
12:452:00  Break for Lunch  
2:003:00  Combinatorial approaches for the subgroup restriction problem.  Milind Sohoni, IIT 
3:154:15  Geometry of Orbits of Permanents and Determinants  Shrawan Kumar, UNC 
4:154:30  Coffee Break  
4:305:30  Kronecker coefficients and the determinant (Expository Talk) 
Jerzy Weyman, Northeastern 
Wednesday, Aug 3  
09:0010:00  Elementary Linear Algebra and Geometric Complexity Theory Joseph Landsberg, Texas A&M 

10:0010:20  Coffee Break  
10:2011:20  Immanants and Complexity Theory  Ke Ye, Texas A&M 
11:3012:30  Problem in geometric invariant theory arising from Geometric Complexity Theory  Jerzy Weyman, Northeastern 
12:302:00  Break for Lunch  
2:003:00  Analogues of Toda's Theorem  Thierry Zell, LenoirRhyne University 
Remainder of the day: outing  
Thursday, Aug 4  
9:0010:00  Complexity Problems for Diophantine Equations  Jeffrey Lagarias, University of Michigan 
10:0010:20  Coffee Break  
10:2011:20  Pfaffian Circuits  Jason Morton, Penn State 
11:3012:30  Elliptic curves and Hilbert's Tenth Problem  Kirsten Eisentrager, Penn State 
12:302:00  Break for Lunch  
2:003:00  Probability, Number Theory, and Computation  Eric Bach, University of Wisconsin 
3:154:15  Complexity of 4D Pascal Determinant(and Permanent)  Leonid Gurvits, Los Alamos National Laboratory 
4:154:45  Coffee Break  
4:455:45  How Number Theory Makes Things Easier (and Harder)  J. Maurice Rojas, Texas A&M 
Friday, Aug 5  
9:0010:00  BSS Analogues of Valiant's Problem  Saugata Basu, Purdue University 
10:0010:20  Coffee Break  
10:2011:20  Decision versus evaluation in algebraic complexity theory  Pascal Koiran, Ecole Normale Superieure de Lyon 
11:3012:30  Open problems session I: GCT and BSS  
12:302:00  Break for Lunch  
2:003:00  Quantum algorithms for number theoretic problems  Sean Hallgren, Penn State 
3:004:00  Followup lecture to Thursday (to be scheduled Thursday) 

3:304:30  Open problems session II  
4:405:30  Part II: Combinatorial approaches for the subgroup restriction problem  Milind Sohoni, IIT 