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…
Efficient Catalytic Graph Algorithms
James Cook, Edward Pyne
We give fast, simple, and implementable catalytic logspace algorithms for two fundamental graph problems. First, a randomized catalytic algorithm for connectivity running…
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…