## #StackBounty: #np-hardness #approximation-hardness #np-complete #coding-theory For what parameters is minimum distance hard?

### Bounty: 100

It has been shown by Vardy that minimum distance of a code is NP-hard (see Alexander Vardy, “The Intractability of Computing the Minimum Distance of a Code,” IEEE Trans. Inf. Thy., Vol. 43 pp. 1757–1766.) Similar and related results were also proved in the following : Berlekamp, McEliece and Van Tilborg [On the inherent intractability of certain coding problems, IEEE Trans. Information Theory, 24 (1978)] and by Dumer, Micciancio and Sudan. The former showing hardness in the case of binary codes whereas the later shows a similar result for approximation version.
Most of these show worst case hardness knowing no additional information about code (other than k and n).
In particular, these problems assume no bounds on rate or distance.
Certainly, a "promise" version could be easier as a trivial example consider a promise that code family is of some bounded constant distance. Clearly a brute algorithm by enumeration would find minimum distance in poly time.
As far as I see the DMS reduction works only for codes with minimum distance that is linear in the dimension.
Has the problem been studies for different d (sublinear) either in exact or approximate version?

Get this bounty!!!

## #StackBounty: #cc.complexity-theory #counting-complexity #approximation-hardness #polynomials #finite-fields \$#\$P hardness of computin…

### Bounty: 100

Consider polynomials $$f: {0, 1}^{n} rightarrow {0, 1}$$ over $$mathbb{F}_2$$ (addition and multiplication are taken modulo $$2$$.) Consider integers $$x in {0,1}^{n}$$, written in binary. Let $$mathbb{Z}$$ be the set of all integers.

Define
begin{align} mathrm{gap}(f) &= sum_{x in {0, 1}^{n}} (-1)^{f(x)} \ &= |{x : f(x) = 0}| – |{x : f(x) = 1}|. end{align}

According to this paper, and this paper (Proposition $$6$$), we know two things about $$mathrm{gap}(f)$$:

1. It is (in the worst case) #P-hard to exactly compute $$|{x : f(x) = 0}|$$, and hence, $$mathrm{gap}(f)$$, when $$f$$ is a polynomial of degree at most $$3$$.
2. $$|{x : f(x) = 0}|$$ and $$mathrm{gap}(f)$$ can be computed in polynomial time when $$f$$ is a polynomial of degree at most $$2$$.

Now, define a new quantity
begin{align} mathrm{weightedgap}(f) &= sum_{x in {0, 1}^{n}} w_{x} (-1)^{f(x)},~text{where} end{align}
begin{align} w =(w_0, w_1, ldots, w_{2^{n}-1}) ~text{is some fixed weight function such that}\~~w_i neq w_j~~text{for}~i neq j~~text{and}~~text{each}~~w_iin mathbb{Z}~~text{where}~~i, j in {0, 1}^{n}. end{align}

Let $$f$$ be a degree $$2$$ polynomial.

I have two related questions:

1. For every choice of such a weight function (which is known
beforehand and which satisfies the constraints mentioned), what is the worst-case hardness of
exactly computing this quantity?
2. For every choice of such a weight function (which is known
beforehand and which satisfies the constraints mentioned), what is the worst-case hardness of
approximating this quantity, upto an inverse polynomial multiplicative error?

Note that we have only one input here — an efficient description of the degree $$2$$ function $$f$$. The weight function is not a part of the input.

I think both my computations are #P-hard. But I could not do a formal reduction.

Note that, unlike in the unweighted version, computing $$|{x : f(x) = 0}|$$ does not allow us to compute $$mathrm{weightedgap}(f)$$: we need to look at the actual values of the function in $$mathcal{O}(2^{n})$$ places. So, I think it is very unlikely that we can do this in polynomial time.

EDIT $$1$$: This paper talks of #P-hardness of computing general weighted sums, but nothing specifically for degree $$2$$ polynomials.

EDIT $$2$$: Theorem $$9$$ of this paper seems close to what we need. Maybe some close variant of Theorem $$9$$ is sufficient?

Get this bounty!!!

## #StackBounty: #cc.complexity-theory #counting-complexity #approximation-hardness #polynomials #finite-fields \$#\$P hardness of computin…

### Bounty: 100

Consider polynomials $$f: {0, 1}^{n} rightarrow {0, 1}$$ over $$mathbb{F}_2$$ (addition and multiplication are taken modulo $$2$$.) Consider integers $$x in {0,1}^{n}$$, written in binary. Let $$mathbb{Z}$$ be the set of all integers.

Define
begin{align} mathrm{gap}(f) &= sum_{x in {0, 1}^{n}} (-1)^{f(x)} \ &= |{x : f(x) = 0}| – |{x : f(x) = 1}|. end{align}

According to this paper, and this paper (Proposition $$6$$), we know two things about $$mathrm{gap}(f)$$:

1. It is (in the worst case) #P-hard to exactly compute $$|{x : f(x) = 0}|$$, and hence, $$mathrm{gap}(f)$$, when $$f$$ is a polynomial of degree at most $$3$$.
2. $$|{x : f(x) = 0}|$$ and $$mathrm{gap}(f)$$ can be computed in polynomial time when $$f$$ is a polynomial of degree at most $$2$$.

Now, define a new quantity
begin{align} mathrm{weightedgap}(f) &= sum_{x in {0, 1}^{n}} w_{x} (-1)^{f(x)},~text{where} end{align}
begin{align} w =(w_0, w_1, ldots, w_{2^{n}-1}) ~text{is some fixed weight function such that}\~~w_i neq w_j~~text{for}~i neq j~~text{and}~~text{each}~~w_iin mathbb{Z}~~text{where}~~i, j in {0, 1}^{n}. end{align}

Let $$f$$ be a degree $$2$$ polynomial.

I have two related questions:

1. For every choice of such a weight function (which is known
beforehand and which satisfies the constraints mentioned), what is the worst-case hardness of
exactly computing this quantity?
2. For every choice of such a weight function (which is known
beforehand and which satisfies the constraints mentioned), what is the worst-case hardness of
approximating this quantity, upto an inverse polynomial multiplicative error?

Note that we have only one input here — an efficient description of the degree $$2$$ function $$f$$. The weight function is not a part of the input.

I think both my computations are #P-hard. But I could not do a formal reduction.

Note that, unlike in the unweighted version, computing $$|{x : f(x) = 0}|$$ does not allow us to compute $$mathrm{weightedgap}(f)$$: we need to look at the actual values of the function in $$mathcal{O}(2^{n})$$ places. So, I think it is very unlikely that we can do this in polynomial time.

EDIT: This paper talks of #P-hardness of computing general weighted sums, but nothing specifically for degree $$2$$ polynomials

Get this bounty!!!

## #StackBounty: #cc.complexity-theory #counting-complexity #approximation-hardness #polynomials #finite-fields \$#\$P hardness of computin…

### Bounty: 100

Consider polynomials $$f: {0, 1}^{n} rightarrow {0, 1}$$ over $$mathbb{F}_2$$ (addition and multiplication are taken modulo $$2$$.) Consider integers $$x in {0,1}^{n}$$, written in binary. Let $$mathbb{Z}$$ be the set of all integers.

Define
begin{align} mathrm{gap}(f) &= sum_{x in {0, 1}^{n}} (-1)^{f(x)} \ &= |{x : f(x) = 0}| – |{x : f(x) = 1}|. end{align}

According to this paper, and this paper (Proposition $$6$$), we know two things about $$mathrm{gap}(f)$$:

1. It is (in the worst case) #P-hard to exactly compute $$|{x : f(x) = 0}|$$, and hence, $$mathrm{gap}(f)$$, when $$f$$ is a polynomial of degree at most $$3$$.
2. $$|{x : f(x) = 0}|$$ and $$mathrm{gap}(f)$$ can be computed in polynomial time when $$f$$ is a polynomial of degree at most $$2$$.

Now, define a new quantity
begin{align} mathrm{weightedgap}(f) &= sum_{x in {0, 1}^{n}} w_{x} (-1)^{f(x)},~text{where} end{align}
begin{align} w =(w_0, w_1, ldots, w_{2^{n}-1}) ~text{is some fixed weight function such that}\~~w_i neq w_j~~text{for}~i neq j~~text{and}~~text{each}~~w_iin mathbb{Z}~~text{where}~~i, j in {0, 1}^{n}. end{align}

Let $$f$$ be a degree $$2$$ polynomial.

I have two related questions:

1. For every choice of such a weight function (which is known
beforehand and which satisfies the constraints mentioned), what is the worst-case hardness of
exactly computing this quantity?
2. For every choice of such a weight function (which is known
beforehand and which satisfies the constraints mentioned), what is the worst-case hardness of
approximating this quantity, upto an inverse polynomial multiplicative error?

Note that we have only one input here — an efficient description of the degree $$2$$ function $$f$$. The weight function is not a part of the input.

I think both my computations are #P-hard. But I could not do a formal reduction.

Note that, unlike in the unweighted version, computing $$|{x : f(x) = 0}|$$ does not allow us to compute $$mathrm{weightedgap}(f)$$: we need to look at the actual values of the function in $$mathcal{O}(2^{n})$$ places. So, I think it is very unlikely that we can do this in polynomial time.

EDIT: This paper talks of #P-hardness of computing general weighted sums, but nothing specifically for degree $$2$$ polynomials

Get this bounty!!!

## #StackBounty: #cc.complexity-theory #counting-complexity #approximation-hardness #polynomials #finite-fields \$#\$P hardness of computin…

### Bounty: 100

Consider polynomials $$f: {0, 1}^{n} rightarrow {0, 1}$$ over $$mathbb{F}_2$$ (addition and multiplication are taken modulo $$2$$.) Consider integers $$x in {0,1}^{n}$$, written in binary. Let $$mathbb{Z}$$ be the set of all integers.

Define
begin{align} mathrm{gap}(f) &= sum_{x in {0, 1}^{n}} (-1)^{f(x)} \ &= |{x : f(x) = 0}| – |{x : f(x) = 1}|. end{align}

According to this paper, and this paper (Proposition $$6$$), we know two things about $$mathrm{gap}(f)$$:

1. It is (in the worst case) #P-hard to exactly compute $$|{x : f(x) = 0}|$$, and hence, $$mathrm{gap}(f)$$, when $$f$$ is a polynomial of degree at most $$3$$.
2. $$|{x : f(x) = 0}|$$ and $$mathrm{gap}(f)$$ can be computed in polynomial time when $$f$$ is a polynomial of degree at most $$2$$.

Now, define a new quantity
begin{align} mathrm{weightedgap}(f) &= sum_{x in {0, 1}^{n}} w_{x} (-1)^{f(x)},~text{where} end{align}
begin{align} w =(w_0, w_1, ldots, w_{2^{n}-1}) ~text{is some fixed weight function such that}\~~w_i neq w_j~~text{for}~i neq j~~text{and}~~text{each}~~w_iin mathbb{Z}~~text{where}~~i, j in {0, 1}^{n}. end{align}

Let $$f$$ be a degree $$2$$ polynomial.

I have two related questions:

1. For every choice of such a weight function (which is known
beforehand and which satisfies the constraints mentioned), what is the worst-case hardness of
exactly computing this quantity?
2. For every choice of such a weight function (which is known
beforehand and which satisfies the constraints mentioned), what is the worst-case hardness of
approximating this quantity, upto an inverse polynomial multiplicative error?

Note that we have only one input here — an efficient description of the degree $$2$$ function $$f$$. The weight function is not a part of the input.

I think both my computations are #P-hard. But I could not do a formal reduction.

Note that, unlike in the unweighted version, computing $$|{x : f(x) = 0}|$$ does not allow us to compute $$mathrm{weightedgap}(f)$$: we need to look at the actual values of the function in $$mathcal{O}(2^{n})$$ places. So, I think it is very unlikely that we can do this in polynomial time.

EDIT: This paper talks of #P-hardness of computing general weighted sums, but nothing specifically for degree $$2$$ polynomials

Get this bounty!!!

## #StackBounty: #cc.complexity-theory #counting-complexity #approximation-hardness #polynomials #finite-fields \$#\$P hardness of computin…

### Bounty: 100

Consider polynomials $$f: {0, 1}^{n} rightarrow {0, 1}$$ over $$mathbb{F}_2$$ (addition and multiplication are taken modulo $$2$$.) Consider integers $$x in {0,1}^{n}$$, written in binary. Let $$mathbb{Z}$$ be the set of all integers.

Define
begin{align} mathrm{gap}(f) &= sum_{x in {0, 1}^{n}} (-1)^{f(x)} \ &= |{x : f(x) = 0}| – |{x : f(x) = 1}|. end{align}

According to this paper, and this paper (Proposition $$6$$), we know two things about $$mathrm{gap}(f)$$:

1. It is (in the worst case) #P-hard to exactly compute $$|{x : f(x) = 0}|$$, and hence, $$mathrm{gap}(f)$$, when $$f$$ is a polynomial of degree at most $$3$$.
2. $$|{x : f(x) = 0}|$$ and $$mathrm{gap}(f)$$ can be computed in polynomial time when $$f$$ is a polynomial of degree at most $$2$$.

Now, define a new quantity
begin{align} mathrm{weightedgap}(f) &= sum_{x in {0, 1}^{n}} w_{x} (-1)^{f(x)},~text{where} end{align}
begin{align} w =(w_0, w_1, ldots, w_{2^{n}-1}) ~text{is some fixed weight function such that}\~~w_i neq w_j~~text{for}~i neq j~~text{and}~~text{each}~~w_iin mathbb{Z}~~text{where}~~i, j in {0, 1}^{n}. end{align}

Let $$f$$ be a degree $$2$$ polynomial.

I have two related questions:

1. For every choice of such a weight function (which is known
beforehand and which satisfies the constraints mentioned), what is the worst-case hardness of
exactly computing this quantity?
2. For every choice of such a weight function (which is known
beforehand and which satisfies the constraints mentioned), what is the worst-case hardness of
approximating this quantity, upto an inverse polynomial multiplicative error?

Note that we have only one input here — an efficient description of the degree $$2$$ function $$f$$. The weight function is not a part of the input.

I think both my computations are #P-hard. But I could not do a formal reduction.

Note that, unlike in the unweighted version, computing $$|{x : f(x) = 0}|$$ does not allow us to compute $$mathrm{weightedgap}(f)$$: we need to look at the actual values of the function in $$mathcal{O}(2^{n})$$ places. So, I think it is very unlikely that we can do this in polynomial time.

EDIT: This paper talks of #P-hardness of computing general weighted sums, but nothing specifically for degree $$2$$ polynomials

Get this bounty!!!

## #StackBounty: #cc.complexity-theory #counting-complexity #approximation-hardness #polynomials #finite-fields \$#\$P hardness of computin…

### Bounty: 100

Consider polynomials $$f: {0, 1}^{n} rightarrow {0, 1}$$ over $$mathbb{F}_2$$ (addition and multiplication are taken modulo $$2$$.) Consider integers $$x in {0,1}^{n}$$, written in binary. Let $$mathbb{Z}$$ be the set of all integers.

Define
begin{align} mathrm{gap}(f) &= sum_{x in {0, 1}^{n}} (-1)^{f(x)} \ &= |{x : f(x) = 0}| – |{x : f(x) = 1}|. end{align}

According to this paper, and this paper (Proposition $$6$$), we know two things about $$mathrm{gap}(f)$$:

1. It is (in the worst case) #P-hard to exactly compute $$|{x : f(x) = 0}|$$, and hence, $$mathrm{gap}(f)$$, when $$f$$ is a polynomial of degree at most $$3$$.
2. $$|{x : f(x) = 0}|$$ and $$mathrm{gap}(f)$$ can be computed in polynomial time when $$f$$ is a polynomial of degree at most $$2$$.

Now, define a new quantity
begin{align} mathrm{weightedgap}(f) &= sum_{x in {0, 1}^{n}} w_{x} (-1)^{f(x)},~text{where} end{align}
begin{align} w =(w_0, w_1, ldots, w_{2^{n}-1}) ~text{is some fixed weight function such that}\~~w_i neq w_j~~text{for}~i neq j~~text{and}~~text{each}~~w_iin mathbb{Z}~~text{where}~~i, j in {0, 1}^{n}. end{align}

Let $$f$$ be a degree $$2$$ polynomial.

I have two related questions:

1. For every choice of such a weight function (which is known
beforehand and which satisfies the constraints mentioned), what is the worst-case hardness of
exactly computing this quantity?
2. For every choice of such a weight function (which is known
beforehand and which satisfies the constraints mentioned), what is the worst-case hardness of
approximating this quantity, upto an inverse polynomial multiplicative error?

Note that we have only one input here — an efficient description of the degree $$2$$ function $$f$$. The weight function is not a part of the input.

I think both my computations are #P-hard. But I could not do a formal reduction.

Note that, unlike in the unweighted version, computing $$|{x : f(x) = 0}|$$ does not allow us to compute $$mathrm{weightedgap}(f)$$: we need to look at the actual values of the function in $$mathcal{O}(2^{n})$$ places. So, I think it is very unlikely that we can do this in polynomial time.

EDIT: This paper talks of #P-hardness of computing general weighted sums, but nothing specifically for degree $$2$$ polynomials

Get this bounty!!!

## #StackBounty: #cc.complexity-theory #counting-complexity #approximation-hardness #polynomials #finite-fields \$#\$P hardness of computin…

### Bounty: 100

Consider polynomials $$f: {0, 1}^{n} rightarrow {0, 1}$$ over $$mathbb{F}_2$$ (addition and multiplication are taken modulo $$2$$.) Consider integers $$x in {0,1}^{n}$$, written in binary. Let $$mathbb{Z}$$ be the set of all integers.

Define
begin{align} mathrm{gap}(f) &= sum_{x in {0, 1}^{n}} (-1)^{f(x)} \ &= |{x : f(x) = 0}| – |{x : f(x) = 1}|. end{align}

According to this paper, and this paper (Proposition $$6$$), we know two things about $$mathrm{gap}(f)$$:

1. It is (in the worst case) #P-hard to exactly compute $$|{x : f(x) = 0}|$$, and hence, $$mathrm{gap}(f)$$, when $$f$$ is a polynomial of degree at most $$3$$.
2. $$|{x : f(x) = 0}|$$ and $$mathrm{gap}(f)$$ can be computed in polynomial time when $$f$$ is a polynomial of degree at most $$2$$.

Now, define a new quantity
begin{align} mathrm{weightedgap}(f) &= sum_{x in {0, 1}^{n}} w_{x} (-1)^{f(x)},~text{where} end{align}
begin{align} w =(w_0, w_1, ldots, w_{2^{n}-1}) ~text{is some fixed weight function such that}\~~w_i neq w_j~~text{for}~i neq j~~text{and}~~text{each}~~w_iin mathbb{Z}~~text{where}~~i, j in {0, 1}^{n}. end{align}

Let $$f$$ be a degree $$2$$ polynomial.

I have two related questions:

1. For every choice of such a weight function (which is known
beforehand and which satisfies the constraints mentioned), what is the worst-case hardness of
exactly computing this quantity?
2. For every choice of such a weight function (which is known
beforehand and which satisfies the constraints mentioned), what is the worst-case hardness of
approximating this quantity, upto an inverse polynomial multiplicative error?

Note that we have only one input here — an efficient description of the degree $$2$$ function $$f$$. The weight function is not a part of the input.

I think both my computations are #P-hard. But I could not do a formal reduction.

Note that, unlike in the unweighted version, computing $$|{x : f(x) = 0}|$$ does not allow us to compute $$mathrm{weightedgap}(f)$$: we need to look at the actual values of the function in $$mathcal{O}(2^{n})$$ places. So, I think it is very unlikely that we can do this in polynomial time.

EDIT: This paper talks of #P-hardness of computing general weighted sums, but nothing specifically for degree $$2$$ polynomials

Get this bounty!!!

## #StackBounty: #cc.complexity-theory #counting-complexity #approximation-hardness #polynomials #finite-fields \$#\$P hardness of computin…

### Bounty: 100

Consider polynomials $$f: {0, 1}^{n} rightarrow {0, 1}$$ over $$mathbb{F}_2$$ (addition and multiplication are taken modulo $$2$$.) Consider integers $$x in {0,1}^{n}$$, written in binary. Let $$mathbb{Z}$$ be the set of all integers.

Define
begin{align} mathrm{gap}(f) &= sum_{x in {0, 1}^{n}} (-1)^{f(x)} \ &= |{x : f(x) = 0}| – |{x : f(x) = 1}|. end{align}

According to this paper, and this paper (Proposition $$6$$), we know two things about $$mathrm{gap}(f)$$:

1. It is (in the worst case) #P-hard to exactly compute $$|{x : f(x) = 0}|$$, and hence, $$mathrm{gap}(f)$$, when $$f$$ is a polynomial of degree at most $$3$$.
2. $$|{x : f(x) = 0}|$$ and $$mathrm{gap}(f)$$ can be computed in polynomial time when $$f$$ is a polynomial of degree at most $$2$$.

Now, define a new quantity
begin{align} mathrm{weightedgap}(f) &= sum_{x in {0, 1}^{n}} w_{x} (-1)^{f(x)},~text{where} end{align}
begin{align} w =(w_0, w_1, ldots, w_{2^{n}-1}) ~text{is some fixed weight function such that}\~~w_i neq w_j~~text{for}~i neq j~~text{and}~~text{each}~~w_iin mathbb{Z}~~text{where}~~i, j in {0, 1}^{n}. end{align}

Let $$f$$ be a degree $$2$$ polynomial.

I have two related questions:

1. For every choice of such a weight function (which is known
beforehand and which satisfies the constraints mentioned), what is the worst-case hardness of
exactly computing this quantity?
2. For every choice of such a weight function (which is known
beforehand and which satisfies the constraints mentioned), what is the worst-case hardness of
approximating this quantity, upto an inverse polynomial multiplicative error?

Note that we have only one input here — an efficient description of the degree $$2$$ function $$f$$. The weight function is not a part of the input.

I think both my computations are #P-hard. But I could not do a formal reduction.

Note that, unlike in the unweighted version, computing $$|{x : f(x) = 0}|$$ does not allow us to compute $$mathrm{weightedgap}(f)$$: we need to look at the actual values of the function in $$mathcal{O}(2^{n})$$ places. So, I think it is very unlikely that we can do this in polynomial time.

EDIT: This paper talks of #P-hardness of computing general weighted sums, but nothing specifically for degree $$2$$ polynomials

Get this bounty!!!

## #StackBounty: #cc.complexity-theory #counting-complexity #approximation-hardness #polynomials #finite-fields \$#\$P hardness of computin…

### Bounty: 100

Consider polynomials $$f: {0, 1}^{n} rightarrow {0, 1}$$ over $$mathbb{F}_2$$ (addition and multiplication are taken modulo $$2$$.) Consider integers $$x in {0,1}^{n}$$, written in binary. Let $$mathbb{Z}$$ be the set of all integers.

Define
begin{align} mathrm{gap}(f) &= sum_{x in {0, 1}^{n}} (-1)^{f(x)} \ &= |{x : f(x) = 0}| – |{x : f(x) = 1}|. end{align}

According to this paper, and this paper (Proposition $$6$$), we know two things about $$mathrm{gap}(f)$$:

1. It is (in the worst case) #P-hard to exactly compute $$|{x : f(x) = 0}|$$, and hence, $$mathrm{gap}(f)$$, when $$f$$ is a polynomial of degree at most $$3$$.
2. $$|{x : f(x) = 0}|$$ and $$mathrm{gap}(f)$$ can be computed in polynomial time when $$f$$ is a polynomial of degree at most $$2$$.

Now, define a new quantity
begin{align} mathrm{weightedgap}(f) &= sum_{x in {0, 1}^{n}} w_{x} (-1)^{f(x)},~text{where} end{align}
begin{align} w =(w_0, w_1, ldots, w_{2^{n}-1}) ~text{is some fixed weight function such that}\~~w_i neq w_j~~text{for}~i neq j~~text{and}~~text{each}~~w_iin mathbb{Z}~~text{where}~~i, j in {0, 1}^{n}. end{align}

Let $$f$$ be a degree $$2$$ polynomial.

I have two related questions:

1. For every choice of such a weight function (which is known
beforehand and which satisfies the constraints mentioned), what is the worst-case hardness of
exactly computing this quantity?
2. For every choice of such a weight function (which is known
beforehand and which satisfies the constraints mentioned), what is the worst-case hardness of
approximating this quantity, upto an inverse polynomial multiplicative error?

Note that we have one input here — an efficient description of the degree $$2$$ function $$f$$.

I think both my computations are #P-hard. But I could not do a formal reduction.

Note that, unlike in the unweighted version, computing $$|{x : f(x) = 0}|$$ does not allow us to compute $$mathrm{weightedgap}(f)$$: we need to look at the actual values of the function in $$mathcal{O}(2^{n})$$ places. So, I think it is very unlikely that we can do this in polynomial time.

EDIT: This paper talks of #P-hardness of computing general weighted sums, but nothing specifically for degree $$2$$ polynomials

Get this bounty!!!