Algorithms & Randomness Center (ARC)

Rekha R. Thomas (University of Washington)

Monday, September 26, 2022

Klaus 1116 - 11:00 am

Title:  Graphical Designs 

Abstract:

Graphical designs on undirected graphs are discrete analogs of spherical designs. They provide quadrature rules on graphs in the sense that a design consists of a subset of vertices with prescribed weights so that the weighted average of a class of graph functions on these vertices is also the global average of the functions on the graph. Depending on the allowed weights, and class of functions to be averaged, one obtains different types of designs. An important question about designs is how to compute them and optimize over

them. In this talk I will explain how positively weighted designs can be organized on the faces of a polytope and using this connection, one can compute the smallest designs in several families of graphs. Designs also connect to random walks on graphs and other well-studied graph entities.

----------------------------------

Speaker's Webpage

Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836 and  http://arc.gatech.edu/node/121

Click here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu