Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > DUAL POLYNOMIALS:
Reports tagged with dual polynomials:
TR17-062 | 9th April 2017

#### Dual polynomials and communication complexity of XOR functions

We show a new duality between the polynomial margin complexity of $f$ and the discrepancy of the function $f \circ$ XOR, called an XOR function. Using this duality,
we develop polynomial based techniques for understanding the bounded error (BPP) and the weakly-unbounded error (PP) communication complexities of XOR functions. ... more >>>

TR17-169 | 24th October 2017
Mark Bun, Robin Kothari, Justin Thaler

#### The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials

The approximate degree of a Boolean function $f$ is the least degree of a real polynomial that approximates $f$ pointwise to error at most $1/3$. The approximate degree of $f$ is known to be a lower bound on the quantum query complexity of $f$ (Beals et al., FOCS 1998 and ... more >>>

TR19-082 | 2nd June 2019
Andrej Bogdanov, Nikhil Mande, Justin Thaler, Christopher Williamson

#### Approximate degree, secret sharing, and concentration phenomena

The $\epsilon$-approximate degree $\widetilde{\text{deg}}_\epsilon(f)$ of a Boolean function $f$ is the least degree of a real-valued polynomial that approximates $f$ pointwise to error $\epsilon$. The approximate degree of $f$ is at least $k$ iff there exists a pair of probability distributions, also known as a dual polynomial, that are perfectly ... more >>>

TR19-121 | 17th September 2019
Alexander A. Sherstov, Justin Thaler

#### Vanishing-Error Approximate Degree and QMA Complexity

The $\epsilon$-approximate degree of a function $f\colon X \to \{0, 1\}$ is the least degree of a multivariate real polynomial $p$ such that $|p(x)-f(x)| \leq \epsilon$ for all $x \in X$. We determine the $\epsilon$-approximate degree of the element distinctness function, the surjectivity function, and the permutation testing problem, showing ... more >>>

TR20-020 | 21st February 2020
Nikhil Mande, Justin Thaler, Shuchen Zhu

#### Improved Approximate Degree Bounds For $k$-distinctness

An open problem that is widely regarded as one of the most important in quantum query complexity is to resolve the quantum query complexity of the $k$-distinctness function on inputs of size $N$. While the case of $k=2$ (also called Element Distinctness) is well-understood, there is a polynomial gap between ... more >>>

ISSN 1433-8092 | Imprint