In 2019, Hao Huang gave an astoundingly short proof of a long-standing conjecture named for this quantity. For 10 points each:
[10h] That conjecture says that this quantity and its ‘block’ type are polynomial in each other. This quantity for a Boolean function is the largest number of bits such that flipping any one of them can flip the function’s output.
ANSWER: sensitivity [accept block sensitivity]
[10m] Block sensitivity is also polynomially related to query complexity, the minimum depth of one of these constructs that computes the function. These objects model a sequence of queries where each query depends on the answers to the previous ones.
ANSWER: decision trees [prompt on trees]
[10e] Deutsch’s algorithm in this field solves a query task in a single query. Other algorithms in this field include Shor’s algorithm for prime factorization, and this field can have exponential speedups over its classical counterpart.
ANSWER: quantum computing