ICERM - Home

Organizing Committee

Saugata Basu
Purdue University

Joseph Landsberg
Texas A & M University

Joseph Rojas
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.

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

Loading participant list in background...

Lecture Videos

An Introduction to Geometric Complexity Theory

Josh Grochow

University of Chicago

August 1, 2011 • 12:00 AM

Mathematical Aspects of P versus NP and its Variants

Aug 1 - 5, 2011

Organizing Committee

Abstract

Lecture Videos

An Introduction to Geometric Complexity Theory

Analogues of Toda's Theorem

BSS Analogues of Valiant's Problem

Combinatorial approaches for the subgroup restriction problem

Complexity Problems for Diophantine Equations

Decision versus evaluation in algebraic complexity theory

Dichotomy Theorems for Counting Problems

Elementary Linear Algebra and Geometric Complexity Theory

Elliptic curves and Hilbert's Tenth Problem

Geometry of Orbits of Permanents and Determinants

Kronecker coefficients and the determinant (Expository Talk)

P versus NP in the BSS-model

Pfaffian Circuits

Problem in geometric invariant theory arising from Geometric Compexity Theo...

Shallow circuits with high-powered inputs

Transfer Results and Number Theoretic Conjectures

Mathematical Aspects of P versus NP and its Variants

Aug 1 - 5, 2011

Organizing Committee

Abstract

Confirmed Speakers & Participants

Lecture Videos

An Introduction to Geometric Complexity Theory

Analogues of Toda's Theorem

BSS Analogues of Valiant's Problem

Combinatorial approaches for the subgroup restriction problem

Complexity Problems for Diophantine Equations

Decision versus evaluation in algebraic complexity theory

Dichotomy Theorems for Counting Problems

Elementary Linear Algebra and Geometric Complexity Theory

Elliptic curves and Hilbert's Tenth Problem

Geometry of Orbits of Permanents and Determinants

Kronecker coefficients and the determinant (Expository Talk)

P versus NP in the BSS-model

Pfaffian Circuits

Problem in geometric invariant theory arising from Geometric Compexity Theo...

Shallow circuits with high-powered inputs

Transfer Results and Number Theoretic Conjectures

Confirmed Speakers & Participants