Alladi Ramakrishnan Hall

Algorithmic Methods in Circuit-Complexity

Satya Amar (Credit Seminar)

IMSc

In this talk, we'll explore how "good" algorithms for the MISSING-STRING problem translates to circuit lower bounds. Let MISSING-STRING be the total search problem where given a (non exhaustive/small) list of strings of a particular length N as input, the output should be an N-length word which is not there in the list. We start with some algorithms for the MISSING-STRING problem, which eventually lead to a version of time hierarchy theorem with non-uniform advice. Finally, as our main result, we will see how certain statements about relativizing circuit lower bounds for the complexity class \Sigma_2 E are equivalent to the existence of particular \Sigma_2 E turing machines in context of the MISSING-STRING problem.

This talk is based on the paper "On Oracles and Algorithmic Methods for Proving Lower Bounds" by Nikhil Vyas and Ryan Williams (2023).