[math-ias] IAS TCS/DM Seminars -- Week of November 19, 2012

[Dottie Phares]

INSTITUTE FOR ADVANCED STUDY
School of Mathematics
Princeton, NJ 08540
 
Theoretical Computer Science/Discrete Math Seminars
Week of November 19, 2012
 
 
 
 
Monday, November 19
 
Computer Science/Discrete Mathematics Seminar I
Topic:                    A Complete Dichotomy Rises from the Capture of
Vanishing Signatures
Speaker:               Jin-Yi Cai, University of Wisconsin
Time/Room:         11:15am - 12:15pm/S-101
Abstract:               See below
 
 
 
Tuesday, November 20
 
Computer Science/Discrete Mathematics Seminar II
Topic:                    On the Complexity of Matrix Multiplication and
Other Tensors
Speaker:               Joseph Landsberg, Texas A&M University
Time/Room:         10:30am - 12:30pm/S-101
Abstract:               See below
 
 
 
1             A Complete Dichotomy Rises from the Capture of Vanishing
Signatures
               Jin-Yi Cai
 
Holant Problems are a broad framework to describe counting problems. The
framework generalizes
counting Constraint Satisfaction Problems and partition functions of Graph
Homomorphisms.
 
We prove a complexity dichotomy theorem for Holant problems over an
arbitrary set of complex-valued
symmetric constraint functions $\mathcal{F}$, also called signatures, on
Boolean variables. This
extends and unifies all previous dichotomies for Holant problems on
symmetric signatures (taking
values without a finite modulus).
 
The dichotomy theorem has an explicit tractability criterion.
A Holant problem defined by $\mathcal{F}$ is solvable in polynomial time if
it satisfies this
tractability criterion, and is \#P-hard otherwise.
The proof of this theorem utilizes many previous dichotomy theorems on
Holant problems and Boolean
\#CSP. Holographic transformations play an indispensable role, not only as a
proof technique, but
also in the statement of the dichotomy criterion.
 
 
 
2             On the Complexity of Matrix Multiplication and Other Tensors
               Joseph Landsberg
 
Many problems from complexity theory can be phrased in terms of tensors. I
will begin by reviewing
basic properties of tensors and discussing several measures of the
complexity of a tensor. I'll then
focus on the complexity of matrix multiplication. Since March 2012 there
have been significant
advances in our understanding of the complexity of matrix multiplication.
This progress was made
possible via tools from algebraic geometry and representation theory, and
I'll explain why such
techniques are useful without assuming any prior background in them.
 
 
 
 
 
Computer Science/Discrete Math Seminars can be found on our web page:






http://www.math.ias.edu/csdm






http://www.math.ias.edu

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://imap.math.ias.edu/mailman/private/all/attachments/20121113/9bda9da7/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Nov19_CSDM.pdf
Type: application/pdf
Size: 2882 bytes
Desc: not available
URL: <http://imap.math.ias.edu/mailman/private/all/attachments/20121113/9bda9da7/attachment-0001.pdf>