Organizing Committee
Purdue University
Texas A & M University
Texas A & M University
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.
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.
A recent construction of Rojas illustrating inputs to an NP-hard problem (real feasibility) admitting polynomial-time algorithms
Loading...
Loading participant list in background...
Workshop Schedule
Monday, August 01, 2011
9:00 - 9:30 AM EDT
Workshop Registration
Location: 11th Floor, 121 South Main Street
10:30 - 11:00 AM EDT
Coffee Break
12:00 - 1:30 PM EDT
Break for Lunch
1:30 - 2:30 PM EDT
P = NP Over a field (eg Z2, R, C ) - Lenore Blum, Carnegie Melon
Location: 11th Floor Lecture Hall
3:45 - 4:15 PM EDT
Coffee Break
5:15 - 6:45 PM EDT
Welcoming Reception
Tuesday, August 02, 2011
9:00 - 10:00 AM EDT
Complexity of Separational Variables - Leonid Gurvits, Los Alamos National Laboratory
Location: 11th Floor Lecture Hall
10:00 - 10:30 AM EDT
Coffee Break
Lecture Videos
Josh Grochow
University of Chicago
August 1, 2011 • 12:00 AM
Thierry Zell
Lenoir-Rhyne
August 3, 2011 • 12:00 AM
Saugata Basu
Purdue University
August 5, 2011 • 12:00 AM
Milind Sohoni
Indian Institute of Technology
August 5, 2011 • 12:00 AM
Jeffrey Lagarias
University of Michigan
August 4, 2011 • 12:00 AM
Pascal Koiran
Ecole Normale Superior of Lyon
August 5, 2011 • 12:00 AM
Jin Yi Cai
University of Wisconsin
August 1, 2011 • 12:00 AM
Joseph Landsberg
Texas A & M University
August 3, 2011 • 12:00 AM
Kirsten Eisentraeger
Pennsylvania State University
August 4, 2011 • 12:00 AM
Shrawan Kumar
University of North Carolina
August 2, 2011 • 12:00 AM
Jerzy Weyman
Northeastern University
August 2, 2011 • 12:00 AM
Michael Shub
Instituto Argentino de Matemática (IAM), CONICET
August 2, 2011 • 12:00 AM
Jason Morton
Pennsylvania State University
August 4, 2011 • 12:00 AM
Jerzy Weyman
Northeastern University
August 3, 2011 • 12:00 AM
Pascal Koiran
Ecole Normale Superior of Lyon
August 2, 2011 • 12:00 AM
Peter Scheiblechner
Rheinische Friedrich-Wilhelms-Universität Bonn
August 1, 2011 • 12:00 AM