1 citations · 1 across the 3 of their papers we have counts for
3 papers
cs.DS2022
Almost 3-Approximate Correlation Clustering in Constant Rounds
Soheil Behnezhad, Moses Charikar, Weiyun Ma +1
We study parallel algorithms for correlation clustering. Each pair among objects is labeled as either "similar" or "dissimilar". The goal is to partition the objects into arbit…
cs.CC2020★ 1 cited
The Power of Many Samples in Query Complexity
Andrew Bassilakis, Andrew Drucker, Mika Göös +3
The randomized query complexity of a boolean function is famously characterized (via Yao's minimax) by the least number of queries needed to dis…
cs.DS2020
New lower bounds for Massively Parallel Computation from query complexity
Moses Charikar, Weiyun Ma, Li-Yang Tan
Roughgarden, Vassilvitskii, and Wang (JACM 18) recently introduced a novel framework for proving lower bounds for Massively Parallel Computation using techniques from boolean funct…