From the 1 of 5 linked papers with an AI index.
5 papers
Graph Spectral Sparsification is in Catalytic Logspace
Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld
We give a catalytic logspace algorithm for the problem of graph spectral sparsification. Given an undirected graph on vertices and , our algorithm outputs an…
Graph k-Coloring in Average Sublinear Time
Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld +2
The paper presents an algorithm that colors k‑colorable graphs in expected O(nk) time, breaking the long‑standing quadratic average‑case barrier and achieving linear time for const…
Characterizing the Distinguishability of Product Distributions through Multicalibration
Cassandra Marcussen, Aaron Putterman, Salil Vadhan
Given a sequence of samples promised to be drawn from one of two distributions , a well-studied problem in statistics is to decide dis…
A Fast Coloring Oracle for Average Case Hypergraphs
Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld +2
Hypergraph -colorability is one of the classical NP-hard problems. Person and Schacht [SODA'09] designed a deterministic algorithm whose expected running time is polynomial over…
Beyond Worst Case Local Computation Algorithms
Amartya Shankha Biswas, Ruidi Cao, Cassandra Marcussen +4
We initiate the study of Local Computation Algorithms on average case inputs. In the Local Computation Algorithm (LCA) model, we are given probe access to a huge graph, and asked t…