[Theory] Theory Seminar

[Alexander Razborov]


We are trying to resurrect the Theory seminar, and our first speaker will be our own
Lorenzo Orecchia. Please note:

1. Different building and room.

2. No pre-seminar refreshments at the moment.

Legal:

This convening is open to all invitees who are compliant with UChicago vaccination requirements and, because of ongoing health risks, particularly to the unvaccinated, participants are expected to adopt the risk mitigation measures (masking and social distancing, etc.) appropriate to their vaccination status as advised by public health officials or to their individual vulnerabilities as advised by a medical professional. Public convening may not be safe for all and carries a risk for contracting COVID-19, particularly for those unvaccinated. Participants will not know the vaccination status of others and should follow appropriate risk mitigation measures.

%%%%%%%%%%%

Departments of Mathematics & Computer Science
Combinatorics & Theory Seminar

Tuesday, January 25
John Crerar Library 298 @3:30pm

Lorenzo Orecchia (U of C)

TITLE: Spectral graph algorithms beyond the Laplacian framework
SUBTITLE: Hamiltonian-based algorithms for vertex-based graph partitioning and hypergraph problems
 
ABSTRACT: Classical spectral graph theory is centered around the study of the quadratic forms of the graph Laplacian operator, through its structural relation to isoperimetric properties of the graph and his algorithmic connection with the heat diffusion process over the graph. In this talk, I will describe a generalization of this theory that focuses instead on bilinear forms of incidence operators and allows for more general structural results and novel algorithmic primitives. In particular, I will showcase a Hamiltonian analogue of the heat diffusion process that allows us to detect sparse vertex-based separators and describe its connection to the fastest-mixing markov chain over an unweighted undirected graph. This is joint work with Antares Chen and Erasmo Tani.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20220119/c9efca99/attachment.html>