Difference between revisions of "Category:Evasive function"
(Created page with "== Definition == A function <math>f:\{-1,1\}^n \to \{-1,1\}</math> is called '''evasive''' if its deterministic decision tree complexity is exactly <math>n</math>.") |
m (→Definition) |
||
| Line 1: | Line 1: | ||
== Definition == | == Definition == | ||
A function <math>f:\{-1,1\}^n \to \{-1,1\}</math> is called '''evasive''' if its deterministic decision tree complexity is exactly <math>n</math>. | A function <math>f:\{-1,1\}^n \to \{-1,1\}</math> is called '''evasive''' if its deterministic decision tree complexity is exactly <math>n</math>. | ||
| + | |||
| + | TODO: add content from here: https://arxiv.org/pdf/cs/0205031.pdf | ||
Latest revision as of 10:26, 20 March 2022
Definition
A function [math]f:\{-1,1\}^n \to \{-1,1\}[/math] is called evasive if its deterministic decision tree complexity is exactly [math]n[/math].
TODO: add content from here: https://arxiv.org/pdf/cs/0205031.pdf
