[theory students] Return of Theory Seminar (but now with a sensible time)! Thursdays 9:45-10:45am

[Sandeep Silwal <silwal@xxxxxxxxxxx>]

Hi everyone, 

Please ignore my previous message yesterday. We have picked a new time.

Theory seminar returns after a winter hiatus!

Next Thursday February 13, 9:45-10:45 am in CS 3310 we will have our very own Ben Young giving a talk. 

Title: The Converse of the Real Orthogonal Holant Theorem and Symmetric Tensor Diagonalization

Abstract: 

The orthogonal Holant theorem is a powerful reduction tool for studying the computational complexity of counting problems. It states that any two sets F and G of tensors equivalent under an orthogonal change of basis are Holant-indistinguishable, meaning every signature grid (tensor network) has the same value whether its signatures come from F or G, and hence Holant(F) and Holant(G) have the same complexity. In this work, we prove the converse of this theorem, resolving a partially open conjecture of Xia (2010): if any two sets of real-valued tensors are Holant-indistinguishable, then they are equivalent under an orthogonal change of basis.

The converse is a powerful tool for deriving algebraic relationships between sets of tensors from combinatorial relationships. In particular, we recover Lovasz's well-known result that homomorphism counts from all graphs determine a graph up to isomorphism and give a combinatorial characterization of sets of real symmetric tensors that are simultaneously 'diagonalizable' (generalizing the notion of simultaneously diagonalizable matrices), extending the result of Boralevi,  Draisma, Horobet, and Robeva (2017).

Hope to see you there and please let me know if you are interested in presenting this semester! It will be Thursdays at 9:45-10:45am.

Best,

Sandeep