1 citations · 1 across the 4 of their papers we have counts for
Showing 2020Show all
2 papers · 1 filter
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…