6 problems

Let $B_N$ be the hyperoctahedral group and let $V=V_{((N-1),(1))}$ be its natural representation. Let $T(B_N,V)$ be the tensor product graph, let $I(V)$ denote its identity represe…

Let $p:\{-1,1\}^n\to\mathbb{R}$ be a polynomial of degree at most $d$. Its Fourier completely bounded $d$-norm is denoted by $\|p\|_{\operatorname{fcb},d}$, and…

Let $p:\{-1,1\}^n\to\mathbb{R}$ be a polynomial of degree at most $d$, with supremum norm $\|p\|_\infty\leq 1$. A variable $i$ has influence $\operatorname{Inf}_i(p)$, and…

Let $f_1,f_2,\ldots,f_k:\{0,1\}^n\rightarrow\{-1,1\}$ be Boolean functions, and define their $k$-fold forrelation by … For even $k=O(1)$ and constant error $\epsilon$, Aaronson–Amb…

Let $K$ be the convex set in the query model under discussion, and suppose that an optimization oracle is implemented using separation or membership queries when the algorithm know…

Let $f$ be a monotone graph property on graphs with $n$ vertices, and consider its bounded-error quantum query complexity, the minimum number of quantum oracle queries required by…