Upper and lower bounds on unrestricted black-box complexity of jumpn,ℓ

Maxim Buzdalov; Mikhail Kever; Benjamin Doerr

doi:10.1007/978-3-319-16468-7_18

Upper and lower bounds on unrestricted black-box complexity of jump_n,ℓ

Maxim Buzdalov
, Mikhail Kever
, Benjamin Doerr

St. Petersburg National Research University of Information Technologies

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

Résumé

We analyse the unrestricted black-box complexity of Jump_n,ℓ 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.

langue originale	Anglais
titre	Evolutionary Computation in Combinatorial Optimization - 15th European Conference, EvoCOP 2015, Proceedings
rédacteurs en chef	Gabriela Ochoa, Francisco Chicano
Editeur	Springer Verlag
Pages	209-221
Nombre de pages	13
ISBN (Electronique)	9783319164670
Les DOIs	https://doi.org/10.1007/978-3-319-16468-7_18
état	Publié - 1 janv. 2015
Evénement	15th European Conference on Evolutionary Computation in Combinatorial Optimization, EvoCOP 2015 - Copenhagen, Danemark Durée: 8 avr. 2015 → 10 avr. 2015

Série de publications

Nom	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9026
ISSN (imprimé)	0302-9743
ISSN (Electronique)	1611-3349

Une conférence

Une conférence	15th European Conference on Evolutionary Computation in Combinatorial Optimization, EvoCOP 2015
Pays/Territoire	Danemark
La ville	Copenhagen
période	8/04/15 → 10/04/15

Accès au document

10.1007/978-3-319-16468-7_18

Contient cette citation

Buzdalov, M., Kever, M., & Doerr, B. (2015). Upper and lower bounds on unrestricted black-box complexity of jump_n,ℓ Dans G. Ochoa, & F. Chicano (eds.), Evolutionary Computation in Combinatorial Optimization - 15th European Conference, EvoCOP 2015, Proceedings (p. 209-221). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol 9026). Springer Verlag. https://doi.org/10.1007/978-3-319-16468-7_18

Buzdalov, Maxim ; Kever, Mikhail ; Doerr, Benjamin. / Upper and lower bounds on unrestricted black-box complexity of jump_n,ℓ Evolutionary Computation in Combinatorial Optimization - 15th European Conference, EvoCOP 2015, Proceedings. Editeur / Gabriela Ochoa ; Francisco Chicano. Springer Verlag, 2015. p. 209-221 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{0958c2885477405e894d7095970ffe48,

title = "Upper and lower bounds on unrestricted black-box complexity of jumpn,ℓ ",

abstract = "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.",

author = "Maxim Buzdalov and Mikhail Kever and Benjamin Doerr",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; 15th European Conference on Evolutionary Computation in Combinatorial Optimization, EvoCOP 2015 ; Conference date: 08-04-2015 Through 10-04-2015",

year = "2015",

month = jan,

day = "1",

doi = "10.1007/978-3-319-16468-7\_18",

language = "English",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "209--221",

editor = "Gabriela Ochoa and Francisco Chicano",

booktitle = "Evolutionary Computation in Combinatorial Optimization - 15th European Conference, EvoCOP 2015, Proceedings",

}

Buzdalov, M, Kever, M & Doerr, B 2015, Upper and lower bounds on unrestricted black-box complexity of jump_n,ℓ Dans G Ochoa & F Chicano (eds), Evolutionary Computation in Combinatorial Optimization - 15th European Conference, EvoCOP 2015, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), VOL. 9026, Springer Verlag, p. 209-221, 15th European Conference on Evolutionary Computation in Combinatorial Optimization, EvoCOP 2015, Copenhagen, Danemark, 8/04/15. https://doi.org/10.1007/978-3-319-16468-7_18

Upper and lower bounds on unrestricted black-box complexity of jump_n,ℓ . / Buzdalov, Maxim; Kever, Mikhail; Doerr, Benjamin.
Evolutionary Computation in Combinatorial Optimization - 15th European Conference, EvoCOP 2015, Proceedings. Ed. / Gabriela Ochoa; Francisco Chicano. Springer Verlag, 2015. p. 209-221 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol 9026).

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

TY - GEN

T1 - Upper and lower bounds on unrestricted black-box complexity of jumpn,ℓ

AU - Buzdalov, Maxim

AU - Kever, Mikhail

AU - Doerr, Benjamin

PY - 2015/1/1

Y1 - 2015/1/1

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-319-16468-7_18

DO - 10.1007/978-3-319-16468-7_18

M3 - Conference contribution

AN - SCOPUS:84925046296

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 209

EP - 221

BT - Evolutionary Computation in Combinatorial Optimization - 15th European Conference, EvoCOP 2015, Proceedings

A2 - Ochoa, Gabriela

A2 - Chicano, Francisco

PB - Springer Verlag

T2 - 15th European Conference on Evolutionary Computation in Combinatorial Optimization, EvoCOP 2015

Y2 - 8 April 2015 through 10 April 2015

ER -

Buzdalov M, Kever M, Doerr B. Upper and lower bounds on unrestricted black-box complexity of jump_n,ℓ Dans Ochoa G, Chicano F, rédacteurs en chef, Evolutionary Computation in Combinatorial Optimization - 15th European Conference, EvoCOP 2015, Proceedings. Springer Verlag. 2015. p. 209-221. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-16468-7_18