Algebraic decision trees
This is not a recent technique, but one that is quite powerful for certain problems.
The algebraic decision tree model is a powerful generalization of comparison trees. In this model, an algorithm is modeled as a non-uniform family of decision trees, one for each input size $n$. Specifically, a $d$th-order algebraic decision tree is a rooted ternary tree with the following structure:
Each non-leaf node $v$ is labeled with a multivariate query polynomial $q_v(x_1, \dots, x_n)$ of degree at most $d$. For example, in a comparison tree, every query polynomial has the form $x_i-x_j$ for some indies $i$ and $j$.
The edges leaving every non-leaf node are labeled $-1$, $0$, and $+1$.
Each leaf is labeled with a possible output description. For example, for the sorting problem, each leaf is labeled with a permutation of the set $\{1,2,\dots,n\}$. For decision problems, each leaf is labeled "yes" or "no".
Given an input vector $\vec{x}\in\mathbb{R}^n$, we compute by traversing a path downward from the root, branching according to the sign of the query polynomials in the visited nodes. The traversal eventually reaches a leaf; the label of that leaf is the output. The "running time" of the algorithm is defined to be the length of the traversed path; thus, the worst-case running time is the depth of the decision tree.
Note in particular that each query polynomial may have $\Omega(n^d)$ distinct terms; nevertheless, the model assumes that we can evaluate the sign of any query polynomial in constant time.
For each leaf $\ell$, let $R(\ell) \subseteq \mathbb{R}^n$ denote the set of input vectors for which execution reaches $\ell$. By construction, $R(\ell)$ is a semi-algebraic subset of $\mathbb{R}^n$ defined by at most $t = \text{depth}(\ell)$ polynomial inequalities of degree at most $d$, for some constant $d$. A classical theorem independently proved by Petrovskiĭ and Oleĭnik, Thom, and Milnor implies that such a semi-algebraic set has at most $(dt)^{O(n)}$ components.
Suppose we want to decide if the input vector lies in a subset $W\subseteq\mathbb{R}^n$. We can make this decision using a $d$th order decision tree with depth $t$ only if $W$ has at most $3^t (dt)^{O(n)}$ components. Equivalently, we have the lower bound $t = \Omega(\log \#W - n\log d)$.
For example, suppose we want to determine whether all $n$ coordinates of the input vector are distinct. The set $W$ of "yes" instances has exactly $n!$ components, one for each permutation of size $n$, so we immediately have a lower bound of $\Omega(n\log n)$.
Note that this lower bound strengthens the classical $\Omega(n\log n)$ comparison lower bound for sorting in two ways. First, the model of computation allows much more complex queries than comparisons at unit cost. Second, and more importantly, the lower bound applies to a decision problem—there are only two distinct outputs, so the naïve information-theoretic bound is trivial.
Extensions of this argument use more interesting complexity measures than the number of components, such as higher Betti numbers, the Euler characteristic, volume, or number of lower-dimensional faces. In all cases, generalizations of the Petrovskiĭ-Oleĭnik-Thom-Milnor theorem imply that each set $R(\ell)$ has "complexity" at most $(dt)^{O(n)}$.
This lower-bound technique has two significant downsides. First, consider any problem that can be solved with a family of algebraic decision trees with polynomial depth. The Petrovskiĭ-Oleĭnik-Thom-Milnor theorem and its generalizations imply that the semi-algebraic sets that define such a problem have complexity at most $n^{O(n)}$. Thus, this technique cannot be used to prove lower bounds bigger than $n\log n$ in this model, for any problem that can be solved in polynomial time.
It is possible to prove $\Omega(n^2)$ lower bounds for certain NP-hard problems, but for similar reasons, there is no hope of anything better. In fact, Meyer auf der Heide proved that some NP-hard problems can actually be solved using linear decision trees with only polynomial depth; specifically, Knapsack can be solved in $O(n^4\log n)$ "time". Meyer auf der Heide's algorithm was later adapted by Meiser to any problem whose solution space is the union of cells in an arrangement of $2^{O(n)}$ hyperplanes in $\mathbb{R}^n$. Thus, it is impossible to prove lower bounds bigger than $n^4\log n$ in this model, for any such problem. An example of such a problem is $k$-SUM (Do any $k$ elements of this set sum to zero?) for any constant $k$; the fastest uniform algorithm for $k$-SUM runs in roughly $O(n^{k/2})$ time. Actually executing Meier auf der Heide's algorithm would require repeatedly solving several NP-hard problems to find the appropriate $O(n^4\log n)$ query polynomials; this construction time is free in the lower-bound model.
Hooray for double-negative results!
