Charlie in Theory

Charlie Anne Carlson

Assistant Professor · she/her

I am an Assistant Professor in the Department of Computer Science and Engineering at the University at Buffalo. I work in theoretical computer science and discrete mathematics.

Previously, I was a postdoctoral researcher at SLMath and at UC Santa Barbara, where I worked with Eric Vigoda. I received my Ph.D. from the University of Colorado Boulder in 2023, advised by Alexandra Kolla, and my M.S. from the University of Illinois Urbana-Champaign.

Photo of Charlie Anne Carlson

Research

My research centers on approximate counting, spectral graph theory, and combinatorial optimization. I am also interested in Markov chains, randomized and approximation algorithms, extremal graph theory, smoothed analysis, and statistical physics.

If you can frame a problem as something related to graph coloring, I’m interested.

Preprints

  1. Approximation Algorithms for Quantum Max-d-Cut

    Charlie Carlson, Zackary Jorquera, Alexandra Kolla, Steven Kordonowy, and Stuart Wayland

    Preprint arXiv

  2. A quantum advantage over classical for local max cut

    Charlie Carlson, Zackary Jorquera, Alexandra Kolla, and Steven Kordonowy

    Preprint arXiv

Publications

  1. Hardness of Approximation for Shortest Path with Vector Costs

    Charlie Carlson, Yury Makarychev, and Ron Mosenzon

    SODA 2026 arXiv PDF Proceedings

  2. Flip Dynamics for Sampling Colorings: Improving (11/6 − ε) Using A Simple Metric

    Charlie Carlson and Eric Vigoda

    SODA 2025 arXiv PDF Proceedings

  3. Optimal Mixing for Randomly Sampling Edge Colorings on Trees Down to the Max Degree

    Charlie Carlson, Xiaoyu Chen, Weiming Feng, and Eric Vigoda

    SODA 2025 arXiv PDF Proceedings

  4. Algorithms for the Ferromagnetic Potts Model on Expanders

    Charlie Carlson, Ewan Davies, Nicolas Fraiman, Alexandra Kolla, Aditya Potukuchi, and Corrine Yap

    Combinatorics, Probability and Computing 2024 · FOCS 2022 arXiv PDF Journal

  5. A Spectral Approach to Approximately Counting Independent Sets in Dense Bipartite Graphs

    Charlie Carlson, Ewan Davies, Alexandra Kolla, and Aditya Potukuchi

    ICALP 2024 arXiv PDF Proceedings

  6. Efficient algorithms for the Potts model on small-set expanders

    Charlie Carlson, Ewan Davies, and Alexandra Kolla

    Chicago Journal of Theoretical Computer Science 2024 arXiv PDF Journal

  7. Improved Distributed Algorithms for Random Colorings

    Charlie Carlson, Daniel Frishberg, and Eric Vigoda

    OPODIS 2023 arXiv PDF

  8. Approximation Algorithms for Norm Multiway Cut

    Charlie Carlson, Jafar Jafarov, Konstantin Makarychev, Yury Makarychev, and Liren Shan

    ESA 2023 arXiv PDF Proceedings

  9. Computational Thresholds for the Fixed-Magnetization Ising Model

    Charlie Carlson, Ewan Davies, Alexandra Kolla, and Will Perkins

    STOC 2022 arXiv PDF

  10. Improving the Smoothed Complexity of FLIP for Max Cut Problems

    Ali Bibak, Charlie Carlson, and Karthekeyan Chandrasekaran

    ACM Transactions on Algorithms 2021 · SODA 2019 arXiv PDF

  11. Lower Bounds for Max-Cut in H-Free Graphs via Semidefinite Programming

    Charlie Carlson, Alexandra Kolla, Ray Li, Nitya Mani, Benny Sudakov, and Luca Trevisan

    SIAM Journal on Discrete Mathematics 2021 · LATIN 2020 arXiv PDF

  12. Spectral Aspects of Symmetric Matrix Signings

    Charlie Carlson, Karthekeyan Chandrasekaran, Hsien-Chih Chang, Naonori Kakimura, and Alexandra Kolla

    Discrete Optimization 2020 · MFCS 2019 arXiv PDF

  13. Optimal Lower Bounds for Sketching Graph Cuts

    Charlie Carlson, Alexandra Kolla, Nikhil Srivastava, and Luca Trevisan

    SODA 2019 arXiv PDF

  14. Search-and-Rescue Robots for Integrated Research and Education in Cyber-Physical Systems

    Orion Lawlor, Mike Moss, Steven Kibler, Charlie Carlson, Shaun Bond, and Seta Bogosyan

    ICELIE 2013 PDF

Teaching

Fall 2026

CSE 331 · Introduction to Algorithms

University at Buffalo

Fall 2025

CSE 331 · Introduction to Algorithms

University at Buffalo

Talks &
Workshops

Selected talks

  1. Sampling Colorings with Markov Chains

    ADYN Seminar · Algorithms, Dynamics, and Information Flow in Networks

  2. Sampling Colorings with Markov Chains

    University of Minnesota · CS&E Colloquium

  3. Sampling Colorings with Flip Dynamics

    SLMath · Connections Workshop: Probability and Statistics of Discrete Structures

    Watch the talk

  5. Sampling Colorings with Markov Chains

    University of Illinois Urbana-Champaign · Theory Seminar

Workshops & research visits

  1. June 2–6, 2025

  2. Spring 2025

    Probability and Statistics of Discrete Structures

    Postdoctoral researcher · SLMath, Berkeley

  3. October 8–9, 2024

    LucaFest@Simons

    Speaker · Simons Institute, Berkeley

  4. August 11–16, 2024

    Frontiers of Statistical Mechanics and Theoretical Computer Science

    Speaker · BIRS, Banff, Canada. Talk: “Sampling colorings (with Markov Chains).”

    Workshop report

  5. November 27–December 2, 2022

    Counting and Sampling: Algorithms and Complexity

    Participant · Schloss Dagstuhl, Germany

  6. August 8–12, 2022

    New tools for optimal mixing of Markov chains: Spectral independence and entropy decay

    Participant and speaker · UC Santa Barbara. Talk: “Fixed-Magnetization Ising Model” (August 12).

    Program

  7. Spring 2019

    Geometry of Polynomials

    Visiting graduate student · Simons Institute, Berkeley

  8. Fall 2017

    Bridging Continuous and Discrete Optimization

    Visiting graduate student · Simons Institute, Berkeley