@inproceedings{c9d68accfa494502aff6207954d858b1,

title = "Black-box complexity of the binary value function",

abstract = "The binary value function, or BinVal, has appeared in several studies in theory of evolutionary computation as one of the extreme examples of linear pseudo-Boolean functions. Its unbiased black-box complexity was previously shown to be at most ?log2 n? + 2, where n is the problem size. We augment it with an upper bound of log2 n+2.42141558-o(1), which is more precise for roughly a half of values of n. We also present a lower bound of log2 n + 1.1186406 - o(1) and provide an algorithm to compute the exact black-box complexity of BinVal for a given n.",

keywords = "BinVal, Linear functions, Unbiased black-box complexity",

author = "Nina Bulanova and Maxim Buzdalov",

note = "Publisher Copyright: {\textcopyright} 2019 Copyright held by the owner/author(s). Publication rights licensed to ACM.; 2019 Genetic and Evolutionary Computation Conference, GECCO 2019 ; Conference date: 13-07-2019 Through 17-07-2019",

year = "2019",

month = jul,

day = "13",

doi = "10.1145/3319619.3322070",

language = "English",

series = "GECCO 2019 Companion - Proceedings of the 2019 Genetic and Evolutionary Computation Conference Companion",

publisher = "Association for Computing Machinery",

pages = "423--424",

booktitle = "GECCO 2019 Companion - Proceedings of the 2019 Genetic and Evolutionary Computation Conference Companion",

address = "United States of America",

}