Events by date

Title: Complexity Measures on the Symmetric Group and Beyond

Abstract:

A classical result in complexity theory states that a degree-d Boolean function on the hypercube can be computed using a decision tree of depth poly(d). Conversely, a Boolean function computed by a decision tree of depth d has degree at most d. Thus degree and decision tree complexity are polynomially related. Many other complexity measures of Boolean functions on the hypercube are polynomially related to the degree (e.g., approximate degree, certificate complexity, block sensitivity), and last year Huang famously added sensitivity to the list. Can we prove similar results for Boolean functions on other combinatorial domains?