Edward Pyne

activity

20212026

most citedBeyond Worst Case Local Computation Algorithms

1 citations · 1 across the 5 of their papers we have counts for

collaborators

Showing 2026Show all

2 papers · 1 filter

cs.DS2026

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 $G$ on $n$ vertices and $ε > 0$ , our algorithm outputs an…

cs.DS2026

Graph k-Coloring in Average Sublinear Time

Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld +2

Graph $k$ -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 $k$ -coloring…