UCSB CS Theory Colloquium Series
Fall 2022
|
Wednesday, October 26, 3:30pm HFH 1132 Speaker: Charlie Carlson (Colorado) Title: Algorithms for the Ferromagnetic Potts model on expanders Abstract: The Potts model is a distribution over colorings of a graph and comes from the world of physics. In this model, every coloring (not necessarily proper) of a graph receives a weight that depends on its number of monochromatic edges. This model and several related models have received continued attention from mathematicians and computer scientists who aim to understand when the models can and can’t be efficiently approximated. It is known that approximating the Potts model is #BIS-hard. That is, it is as hard as approximately counting independent sets in bipartite graphs (#BIS). Some researchers believe that #BIS-hard problems have no efficient algorithms and not all #BIS-hard problems are as hard as counting independent sets in arbitrary graphs. There are ongoing research efforts to understand what conditions produce instances of #BIS-hard problems that have efficient algorithms. One condition considered is on the expansion of the graph in the model. In the Potts model case, we observe that expansion helps to bound the number of biochromatic edges in any coloring. This observation proves useful to several algorithmic techniques. Inspired by recent results, in this talk we consider approximating the Potts model on expander graphs when edges are influenced to be monochromatic (the ferromagnetic case). We introduce and discuss the Potts model, #BIS, expansion, the Polymer model, and results related to approximating the Potts model on expander graphs. Bio: Originally from the Alaskan Bush, Charlie was one of the first from her village to graduate college with a science degree. She finished two degrees at the University of Alaska Fairbanks and shortly after started working as a software engineer at Microsoft. Inspired to learn more about mathematics and computer science, she returned to academia and earned a Master of Science in computer science at the University of Illinois Urbana-Champaign (UIUC). At UIUC, she met her current Ph.D. advisor Alexandra Kolla and first started studying spectral graph theory and randomized algorithms. Later, while attending a research program at the Simons Institute for the Theory of Computing, she was introduced to approximate counting and statistical physics. With her advisor and several collaborators, she now works on algorithms for approximating spin models on graphs with different expansion assumptions. Her other research interests include combinatorial optimization, extremal graph theory and smooth analysis. Charlie will finish her Ph.D. at the University of Colorado Boulder in the Spring of 2023. When she’s not working on research directly, Charlie enjoys playing video games, solving puzzles, going for walks, programming, and spending time with fiancé and their two kittens, Mako and Sokka. As a proud indigenous, transgender, and queer woman, Charlie cares deeply about making academia a safe and welcoming space for everyone. |