research
∙
09/13/2020
Breaking the n-Pass Barrier: A Streaming Algorithm for Maximum Weight Bipartite Matching
Given a weighted bipartite graph with n vertices and m edges, the 𝑚𝑎𝑥𝑖𝑚𝑢...
share
research
∙
03/02/2020
Connected Components on a PRAM in Log Diameter Time
We present an O(log d + loglog_m/n n)-time randomized PRAM algorithm for...
research
∙
01/17/2020
Simpler Partial Derandomization of PPSZ for k-SAT
We give a simpler derandomization of the best known k-SAT algorithm PPSZ...
research
∙
06/01/2019