Meta-algorithms versus circuit lower bounds

Computational complexity theory and algorithms are two major areas in theoretical computer science. Computational complexity theorists study the inherent difficulty of computational problems, and classify problems based on computational resources needed. In particular, complexity theorists intend to prove lower bounds, that is, showing certain problems are not solvable under specific resource bounds. On the other hand, algorithm designers wish to discover efficient algorithms solving particular problems. Traditionally, researchers in the two areas have different goals and use different techniques. However, several recent breakthroughs indicate fundamental connections in between. In particular, new lower bounds were proved via designing efficient algorithms, and reversely, known lower bound proofs were exploited to design efficient algorithms. In this thesis, we focus on the connections between algorithms and lower bounds, which lead to discoveries of new algorithms and lower bounds. For small-size boolean formulas, we get new satisfiability counting algorithms. The algorithm is based on a simplified proof of the property that formula size shrinks with high probability under certain random restrictions. This approach is further adapted to get satisfiability algorithms and average-case lower bounds for small linear-size boolean circuits. We also show that circuit lower bound proofs based on the method of random restrictions yield non-trivial compression algorithms for easy boolean functions from the corresponding circuit classes. In the reverse, we show that the existence of non-trivial compression algorithms would imply circuit lower bounds for non-deterministic exponential time. In the end, we introduce the notion of weakly-uniform circuits, and generalize previous known lower bounds against uniform circuits to weakly-uniform circuits.