@article{
    GrOr05,
    author = "Griffiths, Evan and Orponen, Pekka",
    note = "",
    title = "Optimization, block designs and {N}o {F}ree {L}unch theorems",
    url = "http://dx.doi.org/10.1016/j.ipl.2004.12.015",
    journal = "Information Processing Letters",
    number = "2",
    abstract = "We study the precise conditions under which all optimization strategies for a given family of finite functions yield the same expected maximisation performance, when averaged over a uniform distribution of the functions. In the case of bounded-length searches in a family of Boolean functions, we provide tight connections between such ``No Free Lunch'' conditions and the structure of $t$-designs and $t$-wise balanced designs for arbitrary values $t$. As a corollary, we obtain a nontrivial family of $n$-variate Boolean functions that satisfies the ``No Free Lunch`` condition with respect tosearches of length $\Omega(n^{1/2}/\log^{1/2}n)$. Modifying the construction, we also obtain nontrivial ``No Free Lunch`` families of functions with large ranges.",
    month = "April",
    volume = "94",
    flags = "public",
    year = "2005",
    keywords = "theory of computation, combinatorial problems, optimization, No Free Lunch theorems, combinatorial designs",
    pages = "55--61"
}