Sagnik Mukhopadhyay
Sagnik Mukhopadhyay
Home
Experience
Publications
Contact
Project
Light
Dark
Automatic
Query Complexity
Nearly Optimal Communication and Query Complexity of Bipartite Matching
We settle the complexities of the maximum-cardinality bipartite matching problem (BMM) up to poly-logarithmic factors in five models of computation: the two-party communication, AND query, OR query, XOR query, and quantum edge query models.
Joakim Blikstad
,
Jan van den Brand
,
Yuval Efron
,
Sagnik Mukhopadhyay
,
Danupon Nanongkai
Towards Better Separation between Deterministic and Randomized Query Complexity
We show that there exists a Boolean function $F$ which observes the following separations among deterministic query complexity $(D(F))$, randomized zero error query complexity $(R_0(F))$ and randomized one-sided error query complexity $(R_1(F))$: $R_1(F) = \widetilde{O}(\sqrt{D(F)})$ and $R_0(F)=\widetilde{O}(D(F))^{3/4}$.
Sagnik Mukhopadhyay
,
Swagato Sanyal
Cite
×