- Time Hier, Space Hier- Diagonalization. I would call that Non-Alg.
- Cooks Theorem: this is an ALGORITHM to transform a Non Det TM and a string x to a Boolean Formula.
- All reductions can be viewed as ALGORITHMS.
- Parity not in AC0: The Yao-Hastad proof can be viewed as a non-alg lower bound for the depth 1 or 2, and then a randomized ALGORITHM to transform depth d to depth d-1.
- Parity not in AC0: This is a Non-Alg lower bounds--- you show that parity has some property (not being able to be approx by low degree polys) and then you show that AC0 cannot deal with this property.
- Comm Complexity: The det lower bound on EQ is a Non-Alg lower bound. I think the randomized lower bound on DISJOINT is a Non-Alg lower bounds. Many others lower bounds are reductions to these two, and hence are algorithms.
- Multiparty Comm Comp: I'll just mention one result: Chandra-Furst-Lipton's lower bounds on EXACT-N for k-player Number-on-Forehead. The lower bounds shows that if there is a protocol of t bits then some structure can be colored in a certain way. Then Ramsey Theory is used. Non-Alg Lower bound I think.
- Decision Tree Complexity (Comparisons): The lower bounds on SORTING and MAX, are non-Alg lower bounds. The following leave-counting lower bound for
2nd largest is sort-of a reduction to MAX but I still think its non-alg: First note that the lower bound for MAX is very strong- even the best case
requires n-1 comps. Hence any DT for MAX has roughly 2n-1 leaves.
T is a DT for 2nd largest. For all i=1,...,n let Ti be the subtree where xi WINS. This is a MAX tree for n-1 elements so has 2n-2 leaves. All these sets of leaves are disjoint so T has n2n-2 leaves.Hence T has height n+ log n + \Omega(1).)
- Decision Tree Complexity (Other queries): Algebraic Queries, k-ary queries have all been studied.
The Algebraic Queries lower bounds use number-of-component arguments and seem non-alg. Some of the k-ary query lower bounds use Ramsey Theory to reduce to the comparison case.
- Branching programs and other models often reduce to comm complexity. Is that an algorithm.
- Ryan Williams proof that NEXP is not in ACC is really, at its core, an algorithm that does slightly better than brute force.
My Final Opinion: The above is a random sample, but it seems to be that there are plenty of lower bounds that are non-alg lower bounds. However, as more and more lower bounds are known, more and more reductions will be used and hence there will be more algorithms.