Tata Institute of Fundamental Research
Linear Matroid Intersection is in Pseudo-deterministic NC
STCS Student Seminar
Speaker:
Sumanta Ghosh (IIT Bombay --> Caltech)
Organiser:
Prerona Chatterjee
Date:
Friday, 3 Sep 2021, 17:15 to 18:15
Venue:
(Scan to add to calendar)
Abstract:
A pseudo-deterministic NC algorithm for a search problem is an RNC algorithm that, for a given input, outputs a fixed solution with high probability. In this talk, we describe a pseudo-deterministic NC algorithm for the linear matroid intersection problem. Our work strengthens the RNC algorithm for the linear matroid intersection given by Narayanan, Saran and Vazirani (NSV'94). It also generalizes the pseudo-deterministic NC algorithm for the bipartite matching (due to Goldwasser and Grossman 2017) to linear matroid intersection.
It is a joint work with Rohit Gurjar.
Zoom link: https://zoom.us/j/93889521556?pwd=eEFJWVRtRHNpNlpZWmhNYTJGQTF6Zz09
| Speaker: | Sumanta Ghosh (IIT Bombay --> Caltech) |
| Organiser: | Prerona Chatterjee |
| Date: | Friday, 3 Sep 2021, 17:15 to 18:15 |
| Venue: |
(Scan to add to calendar)
Abstract:
A pseudo-deterministic NC algorithm for a search problem is an RNC algorithm that, for a given input, outputs a fixed solution with high probability. In this talk, we describe a pseudo-deterministic NC algorithm for the linear matroid intersection problem. Our work strengthens the RNC algorithm for the linear matroid intersection given by Narayanan, Saran and Vazirani (NSV'94). It also generalizes the pseudo-deterministic NC algorithm for the bipartite matching (due to Goldwasser and Grossman 2017) to linear matroid intersection.
It is a joint work with Rohit Gurjar.
Zoom link: https://zoom.us/j/93889521556?pwd=eEFJWVRtRHNpNlpZWmhNYTJGQTF6Zz09
It is a joint work with Rohit Gurjar.
Zoom link: https://zoom.us/j/93889521556?pwd=eEFJWVRtRHNpNlpZWmhNYTJGQTF6Zz09