Organizing Committee
Abstract

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.

Image for "Mathematical Aspects of P versus NP and its Variants"
A recent construction of Rojas illustrating inputs to an NP-hard problem (real feasibility) admitting polynomial-time algorithms

P vs NP Report: Published Paper

Confirmed Speakers & Participants

Talks will be presented virtually or in-person as indicated in the schedule below.

  • Speaker
  • Poster Presenter
  • Attendee
  • Virtual Attendee

Workshop Schedule

Monday, August 1, 2011
TimeEventLocationMaterials
9:00 - 9:30am EDTWorkshop Registration11th Floor, 121 South Main Street 
9:30 - 10:30am EDTHolographic Algorithms - Leslie Valiant, Harvard University11th Floor Lecture Hall
10:30 - 11:00am EDTCoffee Break  
11:00 - 12:00pm EDTAn Introduction to Geometric Complexity Theory - Josh Grochow, University of Chicago11th Floor Lecture Hall
12:00 - 1:30pm EDTBreak for Lunch  
1:30 - 2:30pm EDTP = NP Over a field (eg Z2, R, C ) - Lenore Blum, Carnegie Melon11th Floor Lecture Hall 
2:45 - 3:45pm EDTDichotomy Theorems for Counting Problems - Jin Yi Cai, University of Wisconsin11th Floor Lecture Hall
3:45 - 4:15pm EDTCoffee Break  
4:15 - 5:15pm EDTTransfer Results and Number Theoretic Conjectures - Peter Scheiblechner, Purdue University11th Floor Lecture Hall
5:15 - 6:45pm EDTWelcoming Reception  
Tuesday, August 2, 2011
TimeEventLocationMaterials
9:00 - 10:00am EDTComplexity of Separational Variables - Leonid Gurvits, Los Alamos National Laboratory11th Floor Lecture Hall 
10:00 - 10:30am EDTCoffee Break  
10:30 - 11:30am EDTP versus NP in the BSS-model - Michael Shub, CONICET, IMAS, Universidad de Buenos Aires and CUNY Graduate School11th Floor Lecture Hall
11:45 - 12:45pm EDTShallow circuits with high-powered inputs - Pascal Koiran, Ecole Normale Superieure de Lyon11th Floor Lecture Hall
12:45 - 2:00pm EDTBreak for Lunch  
2:00 - 3:00pm EDTCombinatorial approaches for the subgroup restriction problem - Milind Sohoni, IIT11th Floor Lecture Hall
3:15 - 4:15pm EDTGeometry of Orbits of Permanents and Determinants - Shrawan Kumar, UNC 
4:15 - 4:30pm EDTCoffee Break  
4:30 - 5:00pm EDTKronecker coefficients and the determinant (Expository Talk) - Jerzy Weyman, Northeastern11th Floor Lecture Hall 
Wednesday, August 3, 2011
TimeEventLocationMaterials
9:00 - 10:00am EDTElementary Linear Algebra and Geometric Complexity Theory - Joseph Landsberg, Texas A&M11th Floor Lecture Hall 
10:00 - 10:20am EDTCoffee Break  
10:20 - 11:20am EDTImmanants and Complexity Theory - Ke Ye, Texas A&M11th Floor Lecture Hall
11:30 - 12:30pm EDTProblems in geometric invariant theory arising from Geometric Complexity Theory - Jerzy Weyman, Northeastern11th Floor Lecture Hall 
12:30 - 2:00pm EDTBreak for Lunch  
2:00 - 3:00pm EDTAnalogues of Toda's Theorem - Thierry Zell, Lenoir-Rhyne University11th Floor Lecture Hall
3:00 - 5:30pm EDTOuting for the remainder of the day  
Thursday, August 4, 2011
TimeEventLocationMaterials
9:00 - 10:00am EDTComplexity Problems for Diophantine Equations - Jeffrey Lagarias, University of Michigan11th Floor Lecture Hall
10:00 - 10:20am EDTCoffee Break  
10:20 - 11:20am EDTPfaffian Circuits - Jason Morton, Penn State11th Floor Lecture Hall
11:30 - 12:30pm EDTElliptic curves and Hilbert's Tenth Problem - Kirsten Eisentrager, Penn State11th Floor Lecture Hall
12:30 - 2:00pm EDTBreak for Lunch  
2:00 - 3:00pm EDTProbability, Number Theory, and Computation - Eric Bach, University of Wisconsin11th Floor Lecture Hall
3:15 - 4:15pm EDTComplexity of 4D Pascal Determinant (and Permanent) - Leonid Gurvits, Los Alamos National Laboratory11th Floor Lecture Hall
4:15 - 4:45pm EDTCoffee Break  
4:45 - 5:45pm EDTHow Number Theory Makes Things Easier and Harder - J. Maurice Rojas, Texas A&M11th Floor Lecture Hall 
Friday, August 5, 2011
TimeEventLocationMaterials
9:00 - 10:00am EDTBSS Analogues of Valiant's Problem - Saugata Basu, Purdue University11th Floor Lecture Hall 
10:00 - 10:20am EDTCoffee Break  
10:20 - 11:20am EDTDecision versus evaluation in algebraic complexity theory - Pascal Koiran, Ecole Normale Superieure de Lyon11th Floor Lecture Hall
11:30 - 12:30pm EDTOpen problems session I GCT and BSS  
12:30 - 2:00pm EDTBreak for Lunch  
2:00 - 3:00pm EDTQuantum algorithms for number theoretic problems - Sean Hallgren, Penn State11th Floor Lecture Hall
3:00 - 4:00pm EDTFollow-up lecture to Thursday (to be scheduled Thursday)11th Floor Lecture Hall 
3:30 - 4:30pm EDTOpen problems session II  
4:40 - 5:30pm EDTPart II Combinatorial approaches for the subgroup restriction problem - Milind Sohoni, IIT11th Floor Lecture Hall 

Lecture Videos

Combinatorial approaches for the subgroup restriction problem

Milind Sohoni
Indian Institute of Technology
August 5, 2011
Mathematical Aspects of P versus NP and its Variants
Play

Decision versus evaluation in algebraic complexity theory

Pascal Koiran
Ecole Normale Superior of Lyon
August 5, 2011
Mathematical Aspects of P versus NP and its Variants
Play

BSS Analogues of Valiant's Problem

Saugata Basu
Purdue University
August 5, 2011
Mathematical Aspects of P versus NP and its Variants
Play

Elliptic curves and Hilbert's Tenth Problem

Kirsten Eisentraeger
Pennsylvania State University
August 4, 2011
Mathematical Aspects of P versus NP and its Variants
Play

Pfaffian Circuits

Jason Morton
Pennsylvania State University
August 4, 2011
Mathematical Aspects of P versus NP and its Variants
Play

Complexity Problems for Diophantine Equations

Jeffrey Lagarias
University of Michigan
August 4, 2011
Mathematical Aspects of P versus NP and its Variants
Play

Analogues of Toda's Theorem

Thierry Zell
Lenoir-Rhyne
August 3, 2011
Mathematical Aspects of P versus NP and its Variants
Play

Problem in geometric invariant theory arising from Geometric Compexity Theory

Jerzy Weyman
Northeastern University
August 3, 2011
Mathematical Aspects of P versus NP and its Variants
Play

Elementary Linear Algebra and Geometric Complexity Theory

Joseph Landsberg
Texas A & M University
August 3, 2011
Mathematical Aspects of P versus NP and its Variants
Play

Kronecker coefficients and the determinant (Expository Talk)

Jerzy Weyman
Northeastern University
August 2, 2011
Mathematical Aspects of P versus NP and its Variants
Play

Geometry of Orbits of Permanents and Determinants

Shrawan Kumar
University of North Carolina
August 2, 2011
Mathematical Aspects of P versus NP and its Variants
Play

Shallow circuits with high-powered inputs

Pascal Koiran
Ecole Normale Superior of Lyon
August 2, 2011
Mathematical Aspects of P versus NP and its Variants
Play

P versus NP in the BSS-model

Michael Shub
Instituto Argentino de Matemática (IAM), CONICET
August 2, 2011
Mathematical Aspects of P versus NP and its Variants
Play

Transfer Results and Number Theoretic Conjectures

Peter Scheiblechner
Rheinische Friedrich-Wilhelms-Universität Bonn
August 1, 2011
Mathematical Aspects of P versus NP and its Variants
Play

Dichotomy Theorems for Counting Problems

Jin Yi Cai
University of Wisconsin
August 1, 2011
Mathematical Aspects of P versus NP and its Variants
Play

An Introduction to Geometric Complexity Theory

Josh Grochow
University of Chicago
August 1, 2011
Mathematical Aspects of P versus NP and its Variants
Play