Complexity of Turing self-reducibility of Clique problem? I'm interested in the complexity of self reducibility of a variant clique problem. Namely, the NP-complete problem HALF Clique: given a graph on $N$ nodes, Is there a clique of size $N/2$ in the graph?

How hard is it to reduce an instance of HALF CLIQUE of input size $2N$ to an instance of size $N$ using Turing reduction? Is there a Cook reduction? I'm looking for references for upper bounds and lower bounds on the complexity of Turing reductions of this type.
This is not a reference, but an NP-complete problem cannot have a polynomial-time self-reduction which halves the input size unless NP has a nO(log n)-time algorithm, even if we allow Turing reductions.

Suppose there is a p(n)-time Turing reduction from an NP-complete problem L to itself such that given an input of length n, the reduction only makes queries to strings of length at most n/2.  Then you can convert this reduction to a standalone deterministic algorithm for L by using recursion.  By writing down a recurrence relation for the running time of this deterministic algorithm, it is not hard to see that it runs in time nO(log n).