15 citations · 58 across the 17 of their papers we have counts for
5 papers · 1 filter
Fast Low-Space Algorithms for Subset Sum
Ce Jin, Nikhil Vyas, Ryan Williams
We consider the canonical Subset Sum problem: given a list of positive integers and a target integer with for all , determine if there is an $S \s…
An Improved Sketching Algorithm for Edit Distance
Ce Jin, Jelani Nelson, Kewen Wu
We provide improved upper bounds for the simultaneous sketching complexity of edit distance. Consider two parties, Alice with input and Bob with input , that sha…
Fast and Simple Modular Subset Sum
Kyriakos Axiotis, Arturs Backurs, Karl Bringmann +4
We revisit the Subset Sum problem over the finite cyclic group for some given integer . A series of recent works has provided near-optimal algorithms for this pro…
A Massively Parallel Algorithm for Minimum Weight Vertex Cover
Mohsen Ghaffari, Ce Jin, Daan Nilis
We present a massively parallel algorithm, with near-linear memory per machine, that computes a -approximation of minimum-weight vertex cover in ro…
Improved MPC Algorithms for MIS, Matching, and Coloring on Trees and Beyond
Mohsen Ghaffari, Christoph Grunau, Ce Jin
We present round scalable Massively Parallel Computation algorithms for maximal independent set and maximal matching, in trees and more generally graphs of bounded…