Derandomizing Algorithms for Combinatorial Optimization Problems
Implementing Organization
Indian Institute Of Technology Bombay (IITB), Maharashtra
Principal Investigator
Dr. Rohit Gurjar
Indian Institute Of Technology Bombay (IITB), Maharashtra
Project Overview
The derandomization question lies at the intersection of algorithm design and lower bounds. Some of our recent works were on derandomizing the famous Isolation Lemma for various combinatorial families. Some of these implied derandomizations of known algebraic algorithms for various combinatorial optimization problems. While in some other works, we got a parallel equivalence between search and decision versions. PIs propose to pursue two lines of investigation - (i) obtaining new algorithmic results based on our derandomization of the Isolation Lemma in the most general setting and (ii) derandomize known algebraic algorithms for various combinatorial problems.
Source
Source
Science and Engineering Research Board (SERB), DST 2022-23
Indian Institute Of Technology Bombay (IITB), Maharashtra
Accessibility Controls