Edward Pyne

collaborators

Showing cs.DSShow all

3 papers · 1 filter

cs.DS2025

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 $s \to t$ connectivity running…

cs.DS2025

A Fast Coloring Oracle for Average Case Hypergraphs

Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld +2

Hypergraph $2$ -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…

cs.DS2021

Local Access to Random Walks

Amartya Shankha Biswas, Edward Pyne, Ronitt Rubinfeld

For a graph $G$ on $n$ vertices, naively sampling the position of a random walk of at time $t$ requires work $Ω (t)$ . We desire local access algorithms supporting $\text{position}(G…