[theory students] Return of Theory Seminar! Monday Feb 10, 12-1pm in CS 3310: Ben Young

[Sandeep Silwal <silwal@xxxxxxxxxxx>]

Hi everyone, 

Theory seminar returns after a winter hiatus! Sorry about the late start, a recent deadline bogged me down. 

Next Monday February 10, 12-1pm 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 Mondays at 12-1pm. 

Best,

Sandeep