Sagnik Mukhopadhyay
Sagnik Mukhopadhyay
Home
Experience
Publications
Contact
Light
Dark
Automatic
Communication complexity
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
PDF
Cite
Slides
DOI
ECCC
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
PDF
Cite
Slides
Video
DOI
ECCC
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
PDF
Cite
Video
DOI
DOI
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
PDF
Cite
Slides
DOI
arXiv
Cite
×