arXiv:2004.14318 · Leibniz international proceedings in informatics

The Approximate Degree of Bipartite Perfect Matching

Gal Beniamini

Published Apr 29, 2020• 2 citations

Abstract

The approximate degree of a Boolean function is the least degree of a real multilinear polynomial approximating it in the $\ell_\infty$-norm over the Boolean hypercube. We show that the approximate degree of the Bipartite Perfect Matching function, which is the indicator over all bipartite graphs having a perfect matching, is $\widetildeΘ(n^{3/2})$. The upper bound is obtained by fully characterizing the unique multilinear polynomial representing the Boolean dual of the perfect matching function, over the reals. Crucially, we show that this polynomial has very small $\ell_1$-norm -- only exponential in $Θ(n \log n)$. The lower bound follows by bounding the spectral sensitivity of the perfect matching function, which is the spectral radius of its cut-graph on the hypercube \cite{aaronson2020degree, huang2019induced}. We show that the spectral sensitivity of perfect matching is exactly $Θ(n^{3/2})$.

DOI: 10.4230/lipics.ccc.2022.1

Related papers

The Dual Polynomial of Bipartite Perfect Matching

Gal Beniamini

Apr 29, 20202 citations

Comparing the Sensitivity and Degree of Boolean Functions via the Hypercube

Anne-Caroline Rupp

Jun 1, 20260 citations

Algorithmic Polynomials

Alexander A. Sherstov

arXiv:1801.04607Jan 14, 20180 citations

Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities

Mark Bun, Justin Thaler

arXiv:1302.6191Feb 25, 20131 citation

A General Composition Theorem for Approximate Degree

Samruddhi Pednekar, Supartha Podder

cs.CCCross-listedarXiv:2609.30139Sep 25, 20260 citations

On the degree of polynomials that approximate symmetric Boolean functions (preliminary version)

Ramamohan Paturi

In this paper, we provide matching (up to a constant factor) upper and lower bounds on the degree of polynomials that represent symmetric boolean functions with an error 1/3. Let Γ(f)=min{|2k–n+1|:fk ≠ fk+ 1 and 0 ≤ k ≤ n – 1} where fi is the value of f on inputs with exactly i 1's. We prove that the minimum degree over all the approximating polynomials of f is Θ((n(n-Γ(f))).5). We apply the techniques and tools from approximation theory to derive this result.

ACM Symposium on Theory of Computing (STOC)Jan 1, 1992152 citations

arXiv:2004.14318 · Leibniz international proceedings in informatics

The Approximate Degree of Bipartite Perfect Matching

Gal Beniamini

Published Apr 29, 2020• 2 citations

arXiv HTML PDF

Abstract

The approximate degree of a Boolean function is the least degree of a real multilinear polynomial approximating it in the

\ell_\infty

-norm over the Boolean hypercube. We show that the approximate degree of the Bipartite Perfect Matching function, which is the indicator over all bipartite graphs having a perfect matching, is

\widetildeΘ(n^{3/2})

. The upper bound is obtained by fully characterizing the unique multilinear polynomial representing the Boolean dual of the perfect matching function, over the reals. Crucially, we show that this polynomial has very small

\ell_1

-norm -- only exponential in

Θ(n \log n)

. The lower bound follows by bounding the spectral sensitivity of the perfect matching function, which is the spectral radius of its cut-graph on the hypercube \cite{aaronson2020degree, huang2019induced}. We show that the spectral sensitivity of perfect matching is exactly

Θ(n^{3/2})

DOI: 10.4230/lipics.ccc.2022.1

Related papers

The Dual Polynomial of Bipartite Perfect Matching

Gal Beniamini

We obtain a description of the Boolean dual function of the Bipartite Perfect Matching decision problem, as a multilinear polynomial over the Reals. We show that in this polynomial, both the number of monomials and the magnitude of their coefficients are at most exponential in $\mathcal{O}(n \log n)$ . As an application, we obtain a new upper bound of $\mathcal{O}(n^{1.5} \sqrt{\log n})$ on the approximate degree of the bipartite perfect matching function, improving the previous best known bound of $\mathcal{O}(n^{1.75})$ . We deduce that, beyond a $\mathcal{O}(\sqrt{\log n})$ factor, the polynomial method cannot be used to improve the lower bound on the bounded-error quantum query complexity of bipartite perfect matching.We obtain a description of the Boolean dual function of the Bipartite Perfect Matching decision problem, as a multilinear polynomial over the Reals. We show that in this polynomial, both the number of monomials and the magnitude of their coefficients are at most exponential in $\mathcal{O}(n \log n)$. As an application, we obtain a new upper bound of $\mathcal{O}(n^{1.5} \sqrt{\log n})$ on the approximate degree of the bipartite perfect matching function, improving the previous best known bound of $\mathcal{O}(n^{1.75})$. We deduce that, beyond a $\mathcal{O}(\sqrt{\log n})$ factor, the polynomial method cannot be used to improve the lower bound on the bounded-error quantum query complexity of bipartite perfect matching.

Apr 29, 20202 citations

Comparing the Sensitivity and Degree of Boolean Functions via the Hypercube

Anne-Caroline Rupp

This thesis studies three complexity measures of total Boolean functions f:{0,1}n → {0,1}: maximum sensitivity s(f), polynomial degree deg(f), and spectral sensitivity λ(f), where λ(f) is defined as the spectral norm of the adjacency matrix of the sensitivity graph. Building on the results of Aaronson et al., we examine the inequality chain √s(f) ≤ λ(f) ≤ deg(f) and investigate whether all three quantities can be simultaneously equal. The first part of the thesis reverse engineers the equality cases of the two known inequalities to isolate necessary extremal conditions on both the Fourier structure of f and the local geometry of its sensitivity graph. The second part develops Python-based exhaustive and constrained searches to test the first nontrivial candidate profiles. We compute full distributions of s(f), deg(f), and λ(f) for all Boolean functions on n=3 and n=4, showing in particular that no function realizes the candidate (s(f), λ(f), deg(f)) = (4,2,2) at n=4. We then use Möbius-based and CSP-based enumeration to study all real-degree-≤2 Boolean functions through higher dimensions, obtaining repeated evidence that s(f) ≤ 3 in this family and thereby excluding the (4,2,2) case in the tested range. Together, the theoretical and computational results support the view that the simultaneous tightness of √s(f) = λ(f) = deg(f) is obstructed by strong structural incompatibilities beyond the trivial degree-1 case.This thesis studies three complexity measures of total Boolean functions f:{0,1}n → {0,1}: maximum sensitivity s(f), polynomial degree deg(f), and spectral sensitivity λ(f), where λ(f) is defined as the spectral norm of the adjacency matrix of the sensitivity graph. Building on the results of Aaronson et al., we examine the inequality chain √s(f) ≤ λ(f) ≤ deg(f) and investigate whether all three quantities can be simultaneously equal. The first part of the thesis reverse engineers the equality cases of the two known inequalities to isolate necessary extremal conditions on both the Fourier structure of f and the local geometry of its sensitivity graph. The second part develops Python-based exhaustive and constrained searches to test the first nontrivial candidate profiles. We compute full distributions of s(f), deg(f), and λ(f) for all Boolean functions on n=3 and n=4, showing in particular that no function realizes the candidate (s(f), λ(f), deg(f)) = (4,2,2) at n=4. We then use Möbius-based and CSP-based enumeration to study all real-degree-≤2 Boolean functions through higher dimensions, obtaining repeated evidence that s(f) ≤ 3 in this family and thereby excluding the (4,2,2) case in the tested range. Together, the theoretical and computational results support the view that the simultaneous tightness of √s(f) = λ(f) = deg(f) is obstructed by strong structural incompatibilities beyond the trivial degree-1 case.

Jun 1, 20260 citations

Algorithmic Polynomials

Alexander A. Sherstov

The approximate degree of a Boolean function $f(x_{1},x_{2},\ldots,x_{n})$ is the minimum degree of a real polynomial that approximates $f$ pointwise within $1/3$ . Upper bounds on approximate degree have a variety of applications in learning theory, differential privacy, and algorithm design in general. Nearly all known upper bounds on approximate degree arise in an existential manner from bounds on quantum query complexity. We develop a first-principles, classical approach to the polynomial approximation of Boolean functions. We use it to give the first constructive upper bounds on the approximate degree of several fundamental problems: - $O\bigl(n^{\frac{3}{4}-\frac{1}{4(2^{k}-1)}}\bigr)$ for the $k$ -element distinctness problem; - $O(n^{1-\frac{1}{k+1}})$ for the $k$ -subset sum problem; - $O(n^{1-\frac{1}{k+1}})$ for any $k$ -DNF or $k$ -CNF formula; - $O(n^{3/4})$ for the surjectivity problem. In all cases, we obtain explicit, closed-form approximating polynomials that are unrelated to the quantum arguments from previous work. Our first three results match the bounds from quantum query complexity. Our fourth result improves polynomially on the $Θ(n)$ quantum query complexity of the problem and refutes the conjecture by several experts that surjectivity has approximate degree $Ω(n)$ . In particular, we exhibit the first natural problem with a polynomial gap between approximate degree and quantum query complexity.The approximate degree of a Boolean function $f(x_{1},x_{2},\ldots,x_{n})$ is the minimum degree of a real polynomial that approximates $f$ pointwise within $1/3$. Upper bounds on approximate degree have a variety of applications in learning theory, differential privacy, and algorithm design in general. Nearly all known upper bounds on approximate degree arise in an existential manner from bounds on quantum query complexity. We develop a first-principles, classical approach to the polynomial approximation of Boolean functions. We use it to give the first constructive upper bounds on the approximate degree of several fundamental problems: - $O\bigl(n^{\frac{3}{4}-\frac{1}{4(2^{k}-1)}}\bigr)$ for the $k$-element distinctness problem; - $O(n^{1-\frac{1}{k+1}})$ for the $k$-subset sum problem; - $O(n^{1-\frac{1}{k+1}})$ for any $k$-DNF or $k$-CNF formula; - $O(n^{3/4})$ for the surjectivity problem. In all cases, we obtain explicit, closed-form approximating polynomials that are unrelated to the quantum arguments from previous work. Our first three results match the bounds from quantum query complexity. Our fourth result improves polynomially on the $Θ(n)$ quantum query complexity of the problem and refutes the conjecture by several experts that surjectivity has approximate degree $Ω(n)$. In particular, we exhibit the first natural problem with a polynomial gap between approximate degree and quantum query complexity.

arXiv:1801.04607Jan 14, 20180 citations

Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities

Mark Bun, Justin Thaler

The $ε$ -approximate degree of a Boolean function $f: \{-1, 1\}^n \to \{-1, 1\}$ is the minimum degree of a real polynomial that approximates $f$ to within $ε$ in the $\ell_\infty$ norm. We prove several lower bounds on this important complexity measure by explicitly constructing solutions to the dual of an appropriate linear program. Our first result resolves the $ε$ -approximate degree of the two-level AND-OR tree for any constant $ε> 0$ . We show that this quantity is $Θ(\sqrt{n})$ , closing a line of incrementally larger lower bounds. The same lower bound was recently obtained independently by Sherstov using related techniques. Our second result gives an explicit dual polynomial that witnesses a tight lower bound for the approximate degree of any symmetric Boolean function, addressing a question of Špalek. Our final contribution is to reprove several Markov-type inequalities from approximation theory by constructing explicit dual solutions to natural linear programs. These inequalities underly the proofs of many of the best-known approximate degree lower bounds, and have important uses throughout theoretical computer science.The $ε$-approximate degree of a Boolean function $f: \{-1, 1\}^n \to \{-1, 1\}$ is the minimum degree of a real polynomial that approximates $f$ to within $ε$ in the $\ell_\infty$ norm. We prove several lower bounds on this important complexity measure by explicitly constructing solutions to the dual of an appropriate linear program. Our first result resolves the $ε$-approximate degree of the two-level AND-OR tree for any constant $ε> 0$. We show that this quantity is $Θ(\sqrt{n})$, closing a line of incrementally larger lower bounds. The same lower bound was recently obtained independently by Sherstov using related techniques. Our second result gives an explicit dual polynomial that witnesses a tight lower bound for the approximate degree of any symmetric Boolean function, addressing a question of Špalek. Our final contribution is to reprove several Markov-type inequalities from approximation theory by constructing explicit dual solutions to natural linear programs. These inequalities underly the proofs of many of the best-known approximate degree lower bounds, and have important uses throughout theoretical computer science.

arXiv:1302.6191Feb 25, 20131 citation

A General Composition Theorem for Approximate Degree

Samruddhi Pednekar, Supartha Podder

A longstanding open question in Boolean function complexity asks whether approximate degree composes multiplicatively under block composition. Although a general multiplicative upper bound is known, matching lower bounds have previously been established only for restricted classes of functions. We resolve this question for all total Boolean functions by proving the matching lower bound. Together with Sherstov's upper bound, our result shows that, for every pair of total Boolean functions $f:\{0,1\}^n\to\{0,1\}$ and $g:\{0,1\}^m\to\{0,1\}$ , $\widetilde{deg}(f\circ g) = Θ\!\left( \widetilde{deg}(f)\,\widetilde{deg}(g) \right),$ where $\widetilde{deg}$ denotes constant-error approximate degree. We also consider the analogous question for exact quantum query complexity and give a counterexample showing that multiplicative composition fails in this setting.A longstanding open question in Boolean function complexity asks whether approximate degree composes multiplicatively under block composition. Although a general multiplicative upper bound is known, matching lower bounds have previously been established only for restricted classes of functions. We resolve this question for all total Boolean functions by proving the matching lower bound. Together with Sherstov's upper bound, our result shows that, for every pair of total Boolean functions $f:\{0,1\}^n\to\{0,1\}$ and $g:\{0,1\}^m\to\{0,1\}$, \[ \widetilde{deg}(f\circ g) = Θ\!\left( \widetilde{deg}(f)\,\widetilde{deg}(g) \right), \] where $\widetilde{deg}$ denotes constant-error approximate degree. We also consider the analogous question for exact quantum query complexity and give a counterexample showing that multiplicative composition fails in this setting.

cs.CCCross-listedarXiv:2609.30139Sep 25, 20260 citations

On the degree of polynomials that approximate symmetric Boolean functions (preliminary version)

Ramamohan Paturi

ACM Symposium on Theory of Computing (STOC)Jan 1, 1992152 citations

The approximate degree of a Boolean function is the least degree of a real multilinear polynomial approximating it in the

\ell_\infty

-norm over the Boolean hypercube. We show that the approximate degree of the Bipartite Perfect Matching function, which is the indicator over all bipartite graphs having a perfect matching, is

\widetildeΘ(n^{3/2})

\ell_1

-norm -- only exponential in

Θ(n \log n)

Θ(n^{3/2})

\mathcal{O}(n \log n)

. As an application, we obtain a new upper bound of

\mathcal{O}(n^{1.5} \sqrt{\log n})

on the approximate degree of the bipartite perfect matching function, improving the previous best known bound of

\mathcal{O}(n^{1.75})

. We deduce that, beyond a

\mathcal{O}(\sqrt{\log n})

factor, the polynomial method cannot be used to improve the lower bound on the bounded-error quantum query complexity of bipartite perfect matching.

The approximate degree of a Boolean function

f(x_{1},x_{2},\ldots,x_{n})

is the minimum degree of a real polynomial that approximates

f

pointwise within

1/3

. Upper bounds on approximate degree have a variety of applications in learning theory, differential privacy, and algorithm design in general. Nearly all known upper bounds on approximate degree arise in an existential manner from bounds on quantum query complexity. We develop a first-principles, classical approach to the polynomial approximation of Boolean functions. We use it to give the first constructive upper bounds on the approximate degree of several fundamental problems: -

O\bigl(n^{\frac{3}{4}-\frac{1}{4(2^{k}-1)}}\bigr)

for the

k

-element distinctness problem; -

O(n^{1-\frac{1}{k+1}})

for the

k

-subset sum problem; -

O(n^{1-\frac{1}{k+1}})

for any

k

-DNF or

k

-CNF formula; -

O(n^{3/4})

for the surjectivity problem. In all cases, we obtain explicit, closed-form approximating polynomials that are unrelated to the quantum arguments from previous work. Our first three results match the bounds from quantum query complexity. Our fourth result improves polynomially on the

Θ(n)

quantum query complexity of the problem and refutes the conjecture by several experts that surjectivity has approximate degree

Ω(n)

. In particular, we exhibit the first natural problem with a polynomial gap between approximate degree and quantum query complexity.

The

ε

-approximate degree of a Boolean function

f: \{-1, 1\}^n \to \{-1, 1\}

is the minimum degree of a real polynomial that approximates

f

to within

ε

in the

\ell_\infty

norm. We prove several lower bounds on this important complexity measure by explicitly constructing solutions to the dual of an appropriate linear program. Our first result resolves the

ε

-approximate degree of the two-level AND-OR tree for any constant

ε> 0

. We show that this quantity is

Θ(\sqrt{n})

, closing a line of incrementally larger lower bounds. The same lower bound was recently obtained independently by Sherstov using related techniques. Our second result gives an explicit dual polynomial that witnesses a tight lower bound for the approximate degree of any symmetric Boolean function, addressing a question of Špalek. Our final contribution is to reprove several Markov-type inequalities from approximation theory by constructing explicit dual solutions to natural linear programs. These inequalities underly the proofs of many of the best-known approximate degree lower bounds, and have important uses throughout theoretical computer science.

f:\{0,1\}^n\to\{0,1\}

and

g:\{0,1\}^m\to\{0,1\}

\widetilde{deg}(f\circ g) = Θ\!\left( \widetilde{deg}(f)\,\widetilde{deg}(g) \right),

where

\widetilde{deg}

denotes constant-error approximate degree. We also consider the analogous question for exact quantum query complexity and give a counterexample showing that multiplicative composition fails in this setting.