Speaker: |
Kshitij Gajjar (National University of Singapore) |

Organiser: |
Shubhada Agrawal |

Date: |
Friday, 5 Nov 2021, 17:15 to 18:15 |

Venue: |

(Scan to add to calendar)

This problem has several applications, namely in computational biology, DNA storage systems, speech recognition, social choice theory, and classification. Surprisingly, no poly(n)-time algorithm is known for this problem, even when there are only 4 voters. In this talk, I will present a 1.5-approximation algorithm for this problem, whose runtime is poly(n) time when the number of voters is a constant. This is joint work with Diptarka Chakraborty (NUS) and Agastya Vibhuti Jha (EPFL).

Zoom link: https://zoom.us/j/93889521556?pwd=eEFJWVRtRHNpNlpZWmhNYTJGQTF6Zz09