1 citations · 1 across the 5 of their papers we have counts for
7 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
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…
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…
Improved Local Computation Algorithms for Constructing Spanners
Rubi Arviv, Lily Chung, Reut Levi +1
A spanner of a graph is a subgraph that preserves lengths of shortest paths up to a multiplicative distortion. For every , a spanner with size and stretch $(2k+1)…
Local Access to Random Walks
Amartya Shankha Biswas, Edward Pyne, Ronitt Rubinfeld
For a graph on vertices, naively sampling the position of a random walk of at time requires work . We desire local access algorithms supporting $\text{position}(G…