2026 New England Theory Day

Graph k-coloring is one of the classic NP-complete problems. Previous work has studied its average-case complexity, defined as the average runtime over all k-colorable graphs on n vertices, required to compute a k-coloring. A highly influential result of Dyer and Frieze from 1989 gave an algorithm with O(n^2) average runtime for constant k. This quadratic runtime appeared natural (and possibly even optimal) since almost all k-colorable graphs have Theta(n^2) edges. Reading the entire adjacency matrix takes Theta(n^2) time, so any improvement must avoid inspecting the whole input. This was later improved by Kucera in 1995 to average runtime O(n^2/k) for every k < n^c where c \in (0, 1/2). Nevertheless, in the most interesting case of k = O(1), the best-known bound remained quadratic in n. The true average complexity of the k-coloring problem has remained elusive for the last three decades.

We break the longstanding quadratic barrier. Our main result shows that the exact average-case complexity of this fundamental problem is Theta(nk) for every 2 < k < n^{c’} and c’ \in (0, 1/36). For k = O(1), this reveals the average sublinear nature of k-colorability: the average-case complexity is linear in n, and thus sublinear in the size of the input. The matching lower bound applies to every algorithm that correctly k-colors every k-colorable input.

Our proofs draw on ideas from sublinear and local algorithms and also yield a local computation algorithm (LCA) for k-coloring with average-case probe complexity poly(k). A key ingredient is an efficiently checkable certificate of unique colorability for small random cores, based on degree and codegree conditions. This certificate allows the algorithm to propagate colors correctly without inspecting the entire graph.

Ronitt Rubinfeld is an Edwin Sibley Webster Professor at MIT’s Electrical Engineering and Computer Science department, where she has been on the faculty since 2004. She graduated from the University of Michigan with a degree in Computer Engineering, and from the University of California, Berkeley with a Ph.D. in Computer Science in 1990. After postdoctoral positions at Princeton University and the Hebrew University in Jerusalem, she held faculty positions at Cornell University and Tel Aviv University, and has been a member of the research staff at NEC Research Institute. Her work has received the Symposium on Theory of Computing 30 years Test of Time award. Ronitt Rubinfeld was an ONR Young Investigator, a Sloan Fellow, a Guggenheim fellow and an invited speaker at the International Congress of Mathematicians in 2006. She is a fellow of the Association for Computing Machinery, a fellow of the American Academy of Arts and Sciences and a member of the National Academy of Sciences.

Randomized greedy algorithms are among the simplest and most effective methods for approximating maximum matchings, yet their performance on general graphs remains much less well understood than in the bipartite setting. In this talk, I will present recent progress on vertex-iterative randomized greedy matching algorithms for general graphs, focusing on Ranking and FRanking. I will describe new structural ideas and a unified analysis framework that yield improved approximation guarantees for these algorithms, including a 0.56 approximation ratio for Ranking and a 0.539 approximation ratio for FRanking. I will also discuss how the absence of short odd cycles leads to significantly stronger guarantees. More broadly, these results imply improved bounds for related models, including oblivious and fully online matching. The talk is based on joint work with Mohammad Roghani, Mohammad Saneian, and Tao Yu (SODA 2026), and on joint work with Tao Yu (STOC 2026).

Mahsa Derakhshan is an assistant professor in the Khoury College of Computer Sciences at Northeastern University. Her research focuses on designing algorithms under uncertainty, including uncertainty arising from stochastic inputs, limited information, and strategic behavior, with particular interests in matching problems, online algorithms, and market design. She received her Ph.D. in computer science from the University of Maryland in 2021 and held postdoctoral positions at Princeton University and UC Berkeley before joining Northeastern.

In the “query access model” of algorithm design, we have access to the input data only via restricted interfaces. This study is motivated, at times, due to restrictions in certain applications; perhaps more relevant to this audience, it provides a lens to focus on the powers and limitations of algorithmic ideas. In the past few years, there has been some focused interest on the question of understanding connectivity of graphs when we have access to it only via “CUT queries”: in this access model we know the vertices of a graph, but not its edges; at unit cost we can query a subset of vertices and obtain the cut size. The cut induced by the subset, recall, is the edges with exactly one endpoint in the subset.

In this talk, I will expand on the abstract above, and try to chart out the state of the art. I will explain the broad techniques, and also some technical challenges where we are stuck.

I will mostly be talking about other people’s work; if I do talk about works where I have contributed, then they will be those with my recently graduated student Hang Liao whose thesis was on this topic.

Deeparnab Chakrabarty is an associate professor of computer science at Dartmouth College where he has taught since 2017. Before that, he was a researcher at Microsoft Research Bangalore. His research interests are broadly in algorithms, with a special interest in optimization and sublinear algorithms.

Private set intersection (PSI) enables two parties, each holding a private set of elements, to compute the intersection of their sets without revealing anything beyond the intersection. As a special case of secure multi-party computation, PSI has found many applications and shown early success in practice. In this talk, I will first give an overview of the limitations of standard PSI protocols in terms of functionality, security, and scalability. Next, I will discuss recent advances in developing new models and techniques to address these challenges.

Peihan Miao is the John E. Savage Assistant Professor in the Department of Computer Science at Brown University. Her research interests lie in cryptography, theory, and security, with a focus on secure multi-party computation. She received her PhD from the University of California, Berkeley. She is a recipient of the NSF CAREER Award, Meta Privacy Enhancing Technologies Award, Google Research Scholar Award, and Amazon Research Award.