1 citations · 1 across the 4 of their papers we have counts for
4 papers
Correlation Clustering Beyond the Pivot Algorithm
Soheil Behnezhad, Moses Charikar, Vincent Cohen-Addad +2
We study the classic correlation clustering in the dynamic setting. Given objects and a complete labeling of the object-pairs as either similar or dissimilar, the goal is to pa…
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…
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…
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…