Research

Research Interests: 

My research interests span various areas of theoretical computer science and discrete mathematics. My primary focus lies in approximate counting, spectral graph theory, and combinatorial optimization. I am also deeply interested in approximation algorithms, randomized algorithms, extremal graph theory, and smooth analysis. Beyond these, I find many topics intriguing—if you frame a problem as a graph coloring challenge, I’m almost guaranteed to be captivated. 

Preprints:

• Approximation Algorithms for Quantum Max-d-Cut. Charlie Carlson, Zackary Jorquera, Alexandra Kolla, Steven Kordonowy, Stuart Wayland. [arXiv:2309.10957]

• A quantum advantage over classical for local max cut. Charlie Carlson, Zackary Jorquera, Alexandra Kolla, and Steven Kordonowy. [arXiv:2304.08420]

Publications:

• Flip Dynamics for Sampling Colorings: Improving (11/6—ε) Using A Simple Metric. Charlie Carlson and Eric Vigoda. (SODA 2025) [arXiv:2407.04870].

• 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:2407.04576]

• 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 20254) [arXiv:2204.01923]

• A Spectral Approach to Approximately Counting Independent Sets in Dense Bipartite Graphs. Charlie Carlson, Ewan Davies, Alexandra Kolla, and Aditya Potukuchi. (ICALP 2024)  [arXiv:2307.09533]

• Improved Distributed Algorithms for Random Colorings. Charlie Carlson, Daniel Frishberg, and Eric Vigoda. (OPODIS 2023) [arXiv:2309.07859]

• Approximation Algorithms for Norm Multiway Cut. Charlie Carlson, Jafar Jafarov, Konstantin Makarychev, Yury Makarychev, and Liren Shan. (ESA 2023) [arXiv:2308.08373]

• Computational Thresholds for the Fixed-Magnetization Ising Model. Charlie Carlson, Ewan Davies, Alexandra Kolla, and Will Perkins. (STOC 2022) [arXiv:2111.03033]

• Improving the Smoothed complexity of FLIP for Max Cut Problems. Ali Bibak, Charles Carlson, and Karthekeyan Chandrasekaran. (TALG 2021 and SODA 2019) [arXiv:1807.05665]

• Lower Bounds for Max-Cut in H-Free Graphs via Semidefinite Programming. Charles Carlson, Alexandra Kolla, Ray Li, Nitya Mani, Benny Sudakov, and Luca Trevisan. (LATIN 2020 and SIAM Journal on Discrete Mathematics 2021) [arXiv:1810.10044]

• Spectral Aspects of Symmetric Matrix Signings. Charles Carlson, Karthekeyan Chandrasekaran, Hsien-Chih Chang, Naonori Kakimura, and Alexandra Kolla. (MFCS 2019 and Discrete Optimization 2020) [arXiv:1611.03624]

• Optimal Lower Bounds for Sketching Graph Cuts. Charlie Carlson, Alexandra Kolla, Nikhil Srivastava, Luca Trevisan. (SODA 2019) 

• 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)