Office: Blocker 601H
Office hours: TBA
TAMU math dept homepage
Supported by NSF grant DMS-1405368
Teaching Fall 2016:
Geometry and complexity theory Math 689
Meeting: MWF 10:20 - 11:10 Bloc 160
This will cover central problems in theoretical computer science from
a geometric perspective. Topics in computer science: the complexity of matrix multiplication,
both upper and lower bounds, Valiant's conjecture on permanent v.
determinant and variants, the problem of explicitness: how to find
hay in a haystack. Geometry that will be covered: rank
and border rank of tensors, basic representation theory and algebraic
I will follow these notes, which will
be rewritten in more polished form over the summer.
Background required: a strong background in linear algebra, e.g. Math 323
Fall 2014 I served as Chancellor's Professor at the Simons Institute for the Theory of Computing, UC Berkeley,
I organize and co-organize:My CV (last updated 1/16)
Geometry seminar, meeting Mondays 3-4 Blocker 220 and Fridays 4-5pm Blocker 117.
Working seminar for post-docs and graduate students meeting Thursdays, Blocker 624,
Everyone is welcome to the seminars, graduate students
are particularly encouraged to attend.
TAMU seminar calendar
My travel plans
I am on the editorial board of Foundation of Computational Mathematics, Differential Geometry and its Applications,
and Linear Algebra and its Applications.
PAPERS/PREPRINTS in past 5 years
An explicit description of the irreducible components of the set of matrix pencils with bounded normal rank (with F. De Teran and F. Dopico) On the geometry of border rank algorithms for matrix multiplication and other tensors with symmetry (with M. Michalek) On the geometry of border rank algorithms for n x 2 by 2 x 2 matrix multiplication (with N. Ryder, to appear in Exper. Math.)
Permanent vs determinant: an exponential lower bound assuming
symmetry and a potential path towards Valiant's conjecture (with N. Ressayre)
On minimal free resolutions and the method of shifted partial derivatives in complexity theory (with K. Efremenko, H. Schenck and J. Weyman) Abelian Tensors (with Mateusz Michalek, to appear in JMPA) Connections between conjectures of Alon-Tarsi, Hadamard-Howe, and integrals over the special unitary group (with S. Kumar, Discrete Math. 2015) Complexity of linear circuits and geometry (with F. Gesmundo, G. Hauenstein and C. Ikenmeyer, FOCM 2016) Geometric Complexity Theory: an introduction for geometers (Ann. U. Ferrara 2015)
Computer aided methods for lower bounds on the border rank (with G. Hauenstein and C. Ikenmeyer, Exper. Math. 2013)
Explicit tensors of border rank at least 2n-2 (J. Pure. Appl. Alg. 2015)
New lower bounds for the rank of matrix multiplication (SICOMP, 2014)
Padded polynomials, their cousins, and geometric complexity theory (with H. Kadish, Communications in Algebra 2014) New lower bounds for the border rank of matrix multiplication (with G. Ottaviani, Theory of Computing 2015) On the third secant variety (with J. Buczynski, JAC 2014) On the geometry of Tensor Network States (with Y. Qi and K. Ye, QIC, 2012) Equations for secant varieties of Veronese and other varietites (with G. Ottaviani, Annali di Matematica Pura e Applicata, 2013) Fubini-Griffiths-Harris rigidity of homogeneous varieties (with C. Robles, IMRN 2013) Determinental equations for secant varieties and the Eisenbud-Koh-Stillman conjecture (with J. Buczynski and A. Ginesky, J.London Math. Soc. 2013)
Hypersurfaces with degenerate duals and the Geometric Complexity Theory Program (with L. Manivel and N. Ressayre, CMH 2013) P versus NP and geometry ( J. Symb. Comp.2010, MEGA 2009 special issue)
Ranks of tensors and a generalization of secant varieties (with J. Buczynski, LAA special issue on tensors 2013) An overview of mathematical issues arising in the Geometric complexity theory approach to VP \neq VNP (with P. Buergisser, L. Manivel and J. Weyman, SIAM J. Comp. 2011) Holographic algorithms without matchgates (with Jason Morton and Serguei Norine, LAA special issue on tensors 2013) Fubini-Griffiths-Harris rigidity and Lie algebra cohomology (with C. Robles, (Asian Math. J. 2013)
all articles (since 2006)
An introduction to Geometric Complexity Theory (Newsletter of the EMS 3/16)
Exterior differential systems, Lie algebra cohomology, and the rigidity of homogeneous varieties (2008) Differential geometry of submanifolds of projective space (2006) Exterior differential systems and billiards (2006) Representation theory and projective geometry (with L. Manivel), 2004
Tensors: Geometry and Applications.
AMS GSM 128. Click here to see table of contents and preface, and to order.
Click here for corrections and additions
Cartan For Beginners: Differential geometry via moving frames and exterior differential systems (with T. Ivey)AMS GSM 61 . To see the table of contents, preface, and selected pages click here
To order the book from the AMS, click here.
to see corrections to text, click here
Slides of recent talks:
Complexity theory and geometry (Berlin Mathematical School colloquium 2/15)
Perm v. det: an exponential lower bound assuming symmetry (Innovations in Theoretical Computer Science 1/16)
math reviews of all published papersLuke Oeding, PhD May 2009, Defining equations of the varietyof principal minors solved a conjecture of Holtz and Sturmfels.
Current students: Kashif Bari, Fulvio Gesmundo, and Yao Wang
Cameron Farnsworth, August 2016, THE POLYNOMIAL WARING PROBLEM AND THE DETERMINANT
Yonghui Guan, August 2016, EQUATIONS FOR CHOW VARIETIES, THEIR SECANT VARIETIES AND
OTHER VARIETIES ARISING IN COMPLEXITY THEORY
Curtis Porter, August 2016 THE LOCAL EQUIVALENCE PROBLEM FOR 7-DIMENSIONAL, 2-NONDEGENERATE CR
MANIFOLDS WHOSE CUBIC FORM IS OF CONFORMAL UNITARY TYPE
Yang Qi, PhD August 2013 Geometry of Feasible Spaces of Tensors
determined defining equations for the third secant variety of a triple Segre product and closedness of tensor network states
Ke Ye, PhD August 2012, IMMANANTS, TENSOR NETWORK STATES AND THE GEOMETRIC
COMPLEXITY THEORY PROGRAM determined symmetry groups of immanents, and closedness of tensor network states
Ming Yang, PhD Sept. 2012, On partial and generic uniqueness of block term tensor decompositions in signal processing, solving questions originating in signal processing.
Frederic Holweck, PhD fall 04, Dual varieties, simple singularities and simple Lie algebras
Here is a summary of his results in English
E. Allaud, PhD spring 03, thesis: Nongenericity of variations of Hodge structure for hypersurfaces of high degree,
published in Duke. Math. J.
New to the area? Here are some Brazos Valley links
Sungbook: A Collection of Korean Short Stories
available at Amazon (both paperback and kindle):