Sami Davies


Sami Davies
Research Scientist
Simons Institute and UC Berkeley

samidavies [at] berkeley.edu
davies [at] berkeley.edu
I am a research scientist in Theoretical Computer Science at the Simons Institue and Berkeley.

I like problems in combinatorial optimization---think hypergraph matchings, scheduling, clustering, etc.

I was a post-doc at Northwestern for 2 years. In June 2021, I graduated with my Ph.D. in math from the University of Washington, where I worked between the Department of Mathematics and the theory group in the Allen School. I was advised by Thomas Rothvoss.

News

Sep 1

Today, I start as a research scientist at Simons/ Berkeley!

Aug 1

More on correlation clustering with Ben and Heather! We showed that with a small tweak, our fast, combinatorial algorithm that worked for the Min Max objective actually produces a constant factor approximate solution for all \ell_p norms.

Jun 1

Two papers accepted to this year’s ICML! One is on learning-augmented Ford-Fulkerson, where we use learned predictions to improve the run-time of Ford-Fulkerson methods, both theoretically and empirically. The other is on a combinatorial, fast algorithm for Min Max Correlation Clustering.

Feb 1

Heading to a Dagstuhl workshop on scheduling this coming week.

Oct 15

Getting ready to head to EECS Rising Stars in Austin!

Jul 15

Really excited to release this new paper with Josh Brakensiek on robust tensor factorization! We became interested in this while exploring the 3-coloring problem during our internships at MSR, enjoy!

Jun 15

I’ll be giving a talk at the TCS Women Meeting at STOC this year as part of the Rising Star talks.

Papers

One Partition Approximating All \ell_p-norm Objectives in Correlation Clustering
in sub, August 2023
Fast Combinatorial Algorithms for Min Max Correlation Clustering
ICML 2023, January 2023
Predictive Flows for Faster Ford-Fulkerson
ICML 2023, October 2022
Robust Factorizations and Colorings of Tensor Graphs
arxiv 2022, July 2022
Balancing Flow Time and Energy Consumption
SPAA 2022, May 2022
Lower Bounds on the Total Variation Distance Between Mixtures of Two Gaussians
ALT 2022, September 2021
On the Hardness of Scheduling With Non-Uniform Communication Delays
SODA 2022, May 2021
[bibtex]
Approximate Trace Reconstruction
ISIT 2021, December 2020
Scheduling with Communication Delays via LP Hierarchies and Clustering II Weighted Completion Times on Related Machines
SODA 2021, October 2020
Scheduling with Communication Delays via LP Hierarchies and Clustering
FOCS 2020, April 2020
Reconstructing Traces from Trees
COLT 2019, March 2019
[slides]
A Tale of Santa Claus, Hypergraphs and Matroids
SODA 2020, July 2018
[slides]
Algorithms for finding knight's tours on Aztec diamonds
Involve, a Journal of Mathematics, May 2017

Personal, but work related

Current and Past Obsessions
  • I love to climb. The past 2 years, I’ve been focusing on bouldering and have found such a great community within it.

  • I’m vegan. I love to bake, cook, and drink matcha lattes.

  • In a prior life, I ran a lot. I still run sometimes with my menace of a dog. At UW, I made a lot of friends and ran a lot with Race Condition Running.

  • I completed my 200 RYT in the summer of 2019. I taught yoga classes at UW for a year or so.

Inclusivity & Engagement
  • I was a mentor with the Washington Directed Reading Program during the following quarters: Spring 2019, Fall 2020, Winter 2021. I lead projects with undergraduates outside of the WDRP during the Fall 2019 and Winter 2020 quarters.
  • I co-taught the course Math in Society to an amazing groups of people during the Summer of 2018 through FEPPS. FEPPS provides college education for incarcerated women, trans-identifying, and gender nonconforming people in Washington. I have tutored and done other work through FEPPS, as well.