On lower bounds for circuit complexity and algorithms for satisfiability

This work is devoted to explore the novel method of proving circuit lower bounds for the class NEXP by Ryan Williams. Williams is able to show two circuit lower bounds: A conditional lower bound which says that NEXP does not have polynomial size circuits if there exists better-than-trivial algorithms for CIRCUIT SAT and an inconditional lower bound which says that NEXP does not have polynomial size circuits of the class ACC^0. We put special emphasis on the first result by exposing, in as much as of a self-contained manner as possible, all the results from complexity theory that Williams use in his proof. In particular, the focus is put in an efficient reduction from non-deterministic computations to satisfiability of Boolean formulas. The second result is also studied, although not as thoroughly, and some pointers with regards to the relationship of Williams' method and the known complexity theory barriers are given