Tata Institute of Fundamental Research
Monotone Depth Lower Bounds using Communication Complexity
STCS Student Seminar
Speaker:
Sreejata Kishor Bhattacharya
Organiser:
Varun Ramanathan
Date:
Friday, 25 Aug 2023, 16:00 to 17:00
Venue:
A-201
(Scan to add to calendar)
Abstract:
We shall show that any monotone circuit (with fan-in 2) which determines if a graph has a perfect matching must have depth $\Omega(n)$. This shows that efficient deterministic parallel algorithms for the perfect matching problem must use negation. To do so, we shall use tools from communication complexity: more specifically, we shall show that such a circuit will imply a low-cost communication protocol for set-disjointness, which is known to be hard.
| Speaker: | Sreejata Kishor Bhattacharya |
| Organiser: | Varun Ramanathan |
| Date: | Friday, 25 Aug 2023, 16:00 to 17:00 |
| Venue: | A-201 |
(Scan to add to calendar)
Abstract:
We shall show that any monotone circuit (with fan-in 2) which determines if a graph has a perfect matching must have depth $\Omega(n)$. This shows that efficient deterministic parallel algorithms for the perfect matching problem must use negation. To do so, we shall use tools from communication complexity: more specifically, we shall show that such a circuit will imply a low-cost communication protocol for set-disjointness, which is known to be hard.