Question
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
Summary
| 2023 UMN COOT | 08/19/2023 | Y | 3 | 10.00 | 100% | 0% | 0% |
Data
| Jeff Weiner Fan Club | BHSU | 0 | 0 | 10 | 10 |
| Our Job is Buzz | Palestrina Sawayama | 0 | 0 | 10 | 10 |
| Weird Klaus Barbie | doubleplusnegfive | 0 | 0 | 10 | 10 |