I explore fundamental NP-hard problems in computer science through the design of approximation algorithms and the generation of hard problem instances.
My research focuses on Steiner network problems, including Prize-Collecting Steiner Forest and k-MST, where we improved key approximation guarantees.
And on quiet planting for k-SAT, where we developed methods to construct indistinguishable hard instances with multiple solutions.
Ali Ahmadi is a third-year PhD student under the supervision of MohammadTaghi Hajiaghayi. His research focuses on theoretical computer science, particularly on designing algorithms and data structures to solve fundamental problems in graph theory. He is focused on Steiner problems and the generation of hard instances and estabilishing lower bound