Sagnik Mukhopadhyay
Sagnik Mukhopadhyay
Home
Experience
Publications
Contact
Project
Light
Dark
Automatic
Simulation theorem
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
Cite
×