4 papers · 1 filter
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
Graph -coloring is one of the classic NP-complete problems. Previous work has studied its average time complexity, defined to be the average runtime of computing a -coloring…
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…