Geometry and complexity theory Math 662
Meeting: MWF 10:20 - 11:10 Bloc 624


This class 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
geometry.
I will cover chapters 1-7 of these notes. That link is to a public version. After I lecture on sections I am updating the notes. The most recent version is here.

For those interested, there will be a seminar, independent of the class, that will cover chapters 8-10.


Background required: a strong background in linear algebra, e.g. Math 323
Instructor: Joseph (JM) Landsberg


 

 

 
E-mail: jml@math.tamu.edu please include "662" in the subject line when emailing me
 
my cv


E-mail. I will be contacting the class though the TAMU e-mail system. 

Prerequisites. Math 323 or permission of the instructor.

Course text.  class notes
Course description: This is a course in geometry and complexity theory

 


Grade complaints:
If you think a homework  was graded incorrectly you
have one week from the time the graded assignment was returned to you to bring the
issue to the instructor's attention. No complaints after that time will be considered.
 

Grading policy: Weekly homework assignments (100%)
Assignments will usually consist of 3 problems

Weekly homework assignments and announcements -
all from the
class notes unless otherwise noted.
Due 
Friday 9/9: 2.1.1.2, 2.1.1.5, 2.1.5.2
Due Monday 9/26: 2.2.2.2, 2.2.2.3, 2.3.2.3, 2.3.3.2, 2.3.3.8, 2.4.2.2
Due Wed. 10/5: 3.1.2.1, 3.1.3.1, 3.1.4.2, 3.2.1.4 (numbers from "live" simons662.pdf version)
Due Mon. 10/17: 3.3.1.1, 3.4.3.3, 3.4.6.3, 3.4.9.1 (numbers from "live" simons662.pdf version)
Due Mon. 10/31: 4.3.2.2, 4.3.2.3, 4.3.2.4 (numbers from "live" simons662.pdf version)
Due Mon. 11/7: 4.7.1.1, 4.8.5.1, 4.8.5.2 (numbers from "live" simons662.pdf version) 
Due Mon. 11/14: 5.1.3.7, 5.1.4.2, 5.1.4.6    (numbers from "live" simons662.pdf version) 
Due Mon. 11/28: 5.3.1.4,5.3.1.6,5.3.1.7,5.4.2.6    (numbers from "live" simons662.pdf version) 
Due Wed. 12/7: 6.1.4.3, 6.2.3.1, 6.3.2.1   (numbers from "live" simons662.pdf version)  
 
 
Policy regarding absences related to injury or illness: All such absences will be excused
if sufficient documentation is provided as per University policy and
the instructor will help the student make up any missed material.
 

Americans with Disabilities Act (ADA) Policy Statement

The following ADA Policy Statement (part of the Policy on Individual Disabling Conditions) was submitted to the University Curriculum Committee by the Department of Student Life. The policy statement was forwarded to the Faculty Senate for information.

The Americans with Disabilities Act (ADA) is a federal anti-discrimination statute that provides comprehensive civil rights protection for persons with disabilities. Among other things, this legislation requires that all students with disabilities be guaranteed a learning environment that provides for reasonable accommodation of their disabilities. If you believe you have a disability requiring an accommodation, please contact Disability Services, currently located in the Disability Services building at the Student Services at White Creek complex on west campus or call 979-845-1637. For additional information, visit http://disability.tamu.edu.

Academic Integrity Statement

“An Aggie does not lie, cheat, or steal or tolerate those who do.” All syllabi shall contain a section that states the Aggie Honor Code and refers the student to the Honor Council Rules and Procedures on the web http://www.tamu.edu/aggiehonor