Skip to main content
Search
Utility navigation
Calendar
Contact
Login
MAKE A GIFT
Main navigation
Home
Programs & Events
Research Programs
Workshops & Symposia
Public Lectures
Research Pods
Internal Program Activities
Algorithms, Society, and the Law
People
Scientific Leadership
Staff
Current Long-Term Visitors
Research Fellows
Postdoctoral Researchers
Scientific Advisory Board
Governance Board
Industry Advisory Council
Affiliated Faculty
Science Communicators in Residence
Law and Society Fellows
Participate
Apply to Participate
Plan Your Visit
Location & Directions
Postdoctoral Research Fellowships
Law and Society Fellowships
Science Communicator in Residence Program
Circles
Breakthroughs Workshops and Goldwasser Exploratory Workshops
Support
Annual Fund
Funders
Industrial Partnerships
News & Videos
News
Videos
About
Image
Algebraic Methods
Program
Lower Bounds in Computational Complexity
Location
Calvin Lab auditorium
Date
Monday, Dec. 3
–
Friday, Dec. 7, 2018
Back to calendar
Breadcrumb
Home
Workshop & Symposia
Schedule
Secondary tabs
The Workshop
Schedule
Videos
Click on the titles of individual talks for abstract, slides and archived video.
Monday, Dec. 3, 2018
9:30
–
9:50 a.m.
Coffee and Check-In
9:50
–
10 a.m.
Opening Remarks
10
–
11 a.m.
Invariant Theory for Computer Scientists
Avi Wigderson (Institute for Advanced Study, Princeton)
11
–
11:30 a.m.
Break
11:30 a.m.
–
12:30 p.m.
The GCT Program: Recent Developments and Some Concrete Open Problems
Ketan Mulmuley (The University of Chicago)
12:30
–
2:30 p.m.
Lunch
2:30
–
3:15 p.m.
Geometric Complexity Theory: No Occurrence Obstructions for Determinant vs Permanent
Peter Bürgisser (Technical University of Berlin)
3:15
–
3:35 p.m.
Break
3:35
–
4:20 p.m.
Orbits of Monomials and Factorization into Products of Linear Forms
Pascal Koiran (École Normale Supérieure de Lyon)
4:20
–
5:05 p.m.
Proof Complexity Lower Bounds from Graph Expansion and Combinatorial Games
Jakob Nordström (University of Copenhagen & Lund University)
Tuesday, Dec. 4, 2018
9:30
–
10 a.m.
Coffee and Check-In
10
–
11 a.m.
Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
Virginia Williams (Massachusetts Institute of Technology)
11
–
11:30 a.m.
Break
11:30 a.m.
–
12 p.m.
Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree
Vishwas Bhargava (Rutgers University)
12
–
12:30 p.m.
An Instance of Symbolic Determinant Identity Testing via *-algebras
Youming Qiao (University of Technology, Sydney)
12:30
–
2:30 p.m.
Lunch
2:30
–
3:15 p.m.
Kronecker and Plethysm Coefficients in Geometric Complexity Theory: Permanent vs Determinant and Matrix Powering
Greta Panova (University of Pennsylvania)
3:15
–
3:35 p.m.
Break
3:35
–
4:20 p.m.
Recent Progress on Representation Theoretic Multiplicities in GCT
Christian Ikenmeyer (University of Warwick)
4:20
–
5:05 p.m.
Generalized Matrix Completion and Algebraic Natural Proofs
Markus Bläser (Universität des Saarlandes)
5:05
–
6:30 p.m.
Reception
Wednesday, Dec. 5, 2018
9:30
–
10 a.m.
Coffee and Check-In
10
–
11 a.m.
Proper Learning Algorithms from Lower Bounds for Arithmetic Circuits
Neeraj Kayal (Microsoft Research India)
11
–
11:30 a.m.
Break
11:30 a.m.
–
12 p.m.
Fine-Grained Algorithms and Complexity of Solving Polynomial Systems of Equations
Ryan Williams (Massachusetts Institute of Technology)
12
–
12:30 p.m.
An Improved Depth Reduction for Syntactically Multilinear Circuits
Mrinal Kumar (Harvard University)
12:30
–
2:30 p.m.
Lunch
2:30
–
3:15 p.m.
Reconstruction of Non-Degenerate Homogeneous Depth Three Circuits
Chandan Saha (Indian Institute of Science)
3:15
–
3:35 p.m.
Break
3:35
–
4:20 p.m.
A PSPACE Construction of a Hitting Set for the Closure of Small Algebraic Circuits
Michael Forbes (University of Illinois at Urbana-Champaign)
4:20
–
5:05 p.m.
Algebraic Dependence is Not Hard (& Filling the GCT Chasm)
Nitin Saxena (IIT Kanpur)
5:05
–
6 p.m.
Open Problem Session
Thursday, Dec. 6, 2018
9:30
–
10 a.m.
Coffee and Check-In
10
–
10:30 a.m.
Analyzing Alternating Minimization Algorithms Using Algebraic Methods
Ankit Garg (Princeton University)
10:30
–
11 a.m.
PIT Questions in Invariant Theory
Rafael Mendes de Oliveira (University of Waterloo)
11
–
11:30 a.m.
Break
11:30 a.m.
–
12 p.m.
Complete Derandomization of Identity Testing of Read-Once Formulas
Ilya Volkovich (University of Michigan)
12
–
12:30 p.m.
Formal Series and Non-Commutative Computations
Guillaume Malod (Université Paris Diderot)
12:30
–
2:30 p.m.
Lunch
2:30
–
3:15 p.m.
Barriers for Rank Methods in Arithmetic Complexity
Klim Efremenko (Ben Gurion University)
3:15
–
3:35 p.m.
Break
3:35
–
4:20 p.m.
Generic vs Symbolic Behaviour, and Power Series Expansion
Visu Makam (Institute for Advanced Study)
4:20
–
5:05 p.m.
Near-Optimal Bootstrapping of Hitting Sets
Ramprasad Saptharishi (Tata Institute of Fundamental Research, Mumbai)
Friday, Dec. 7, 2018
9:30
–
10 a.m.
Coffee and Check-In
10
–
11 a.m.
Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications
Nutan Limaye (Indian Institute of Technology Bombay)
11
–
11:30 a.m.
Break
11:30 a.m.
–
12:30 p.m.
Complexity of Separation of Variables and Splitting of Monomials
Leonid Gurvits (City University of New York)
12:30
–
2:30 p.m.
Lunch
2:30
–
3:15 p.m.
Torus Quotients in the Grassmannian
K. V. Subrahmanyam (Chennai Mathematical Institute)
3:15
–
3:35 p.m.
Break
3:35
–
4:20 p.m.
Fast Exact Algorithms Using Hadamard Product of Polynomials
Vikraman Arvind (Institute of Mathematical Sciences)
Share this page
Copy URL of this page
link to homepage
Close
Main navigation
Home
Programs & Events
Research Programs
Workshops & Symposia
Public Lectures
Research Pods
Internal Program Activities
Algorithms, Society, and the Law
People
Scientific Leadership
Staff
Current Long-Term Visitors
Research Fellows
Postdoctoral Researchers
Scientific Advisory Board
Governance Board
Industry Advisory Council
Affiliated Faculty
Science Communicators in Residence
Law and Society Fellows
Participate
Apply to Participate
Plan Your Visit
Location & Directions
Postdoctoral Research Fellowships
Law and Society Fellowships
Science Communicator in Residence Program
Circles
Breakthroughs Workshops and Goldwasser Exploratory Workshops
Support
Annual Fund
Funders
Industrial Partnerships
News & Videos
News
Videos
About
Utility navigation
Calendar
Contact
Login
MAKE A GIFT
link to homepage
Close
Search