A fundamental problem in circuit complexity is to find explicit functions that require large depth to compute. When considering the natural DeMorgan basis of \{\text{OR},\text{AND}\}, where negations incur no cost, the best known depth lower bounds for an explicit function in NP have the form (3-o(1))\log_2 n, established by H{\aa}stad ... more >>>