Upper and Lower Bounds on Unrestricted Black-Box Complexity of Jump _n, ℓ

We analyse the unrestricted black-box complexity of Jumpn,ℓ functions. For upper bounds, we present three algorithms for small, medium and extreme values of ℓ We present a matrix lower bound theorem which is capable of giving better lower bounds than a general information theory approach if one is able to assign different types to queries and define relationships between them. Using this theorem, we prove lower bounds for Jump separately for odd and even values of n. For several cases, notably for extreme Jump, the first terms of lower and upper bounds coincide.