Lower Bounds on Circuit Depth for the Largest Independent Set Problem

Boolean circuits is a classical family of algorithms used to investigate algorithmic tractability and hardness of various algorithmic decision and search problems. A lot of efforts have been devoted in the past to establishing lower bounds on the depth of polynomial size circuits solving various hard combinatorial optimization problems. A state of the art result in this direction is one by Rossman who shows that any poly-size circuit solving the decision version of the largest clique problem (equivalently the largest independent set problem) must have depth at least c_n\log n/\log\log n), for some sequence c_n converging to zero as the size of the graph n diverges to infinity. We establish a stronger lower bound of \Omega(\log n/\log\log n), though for the search as opposed to the decision problem. Specifically we show that any poly-size circuit which produces an independent set larger than half-optimum in sparse random graph must have at least the stated depth.

Our proof is based on using the multi-overlap version of the overlap gap property, which is known to be exhibited by large independent sets in sparse random graphs, coupled with Linial-Mansour-Nisan theorem.

Joint work with Aukosh Jagannath, Alex Wein