Research

Mathematical Sciences

Title :

Derandomizing Algorithms for Combinatorial Optimization Problems

Area of research :

Mathematical Sciences

Principal Investigator :

Dr. Rohit Gurjar, Indian Institute Of Technology Bombay (IITB), Maharashtra

Timeline Start Year :

2023

Timeline End Year :

2026

Contact info :

Details

Executive Summary :

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.

Total Budget (INR):

6,60,000

Organizations involved