Sagnik Mukhopadhyay
Sagnik Mukhopadhyay
Home
Experience
Publications
Contact
Project
Light
Dark
Automatic
Communication complexity
Towards Understanding Challenges of Computation over Large Network
Hiring! I am looking for a motivated and mathematically inclined PhD student with previous experience in courses/modules in theoretical computer science. This position is based in the Department of Computer Science in the University of Sheffield and comes with full tuition fee and stipend.
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
Lifting Theorems for Equality
We show a deterministic simulation (or lifting) theorem for composed problems $f \circ \mathsf{Eq}_n$ where the inner function (the gadget) is Equality on $n$ bits. When $f$ is a total function on $p$ bits, it is easy to show via a rank argument that the communication complexity of $f\circ \mathsf{Eq}_n$ is $\Omega(deg(f) \cdot n)$.
Bruno Loff
,
Sagnik Mukhopadhyay
Simulation Beats Richness: New Data-Structure Lower Bounds
We develop a technique for proving lower bounds in the setting of asymmetric communication, a model that was introduced in the famous works of Miltersen (STOC'94) and Miltersen, Nisan, Safra and Wigderson (STOC'95).
Arkadev Chattopadhyay
,
Michal Koucký
,
Bruno Loff
,
Sagnik Mukhopadhyay
Lower Bounds for Elimination via Weak Regularity
We consider the problem of elimination in communication complexity, that was first raised by Ambainis et al. and later studied by Beimel et al. for its connection to the famous direct sum question.
Arkadev Chattopadhyay
,
Michal Koucký
,
Bruno Loff
,
Sagnik Mukhopadhyay
Tribes is Hard in Message-passing Model
We consider the point-to-point message passing model of communication in which there are $k$ processors with individual private inputs, each $n$-bit long. Each processor is located at the node of an underlying undirected graph and has access to private random coins.
Arkadev Chattopadhyay
,
Sagnik Mukhopadhyay
Cite
×