30

Let $f\colon \{0,1\}^n \to \{0,1\}$ be a boolean function. If it has a polynomial representation $P$ then it has a multilinear polynomial representation $Q$ of degree $\deg Q \leq \deg P$: just replace any power $x_i^k$, where $k \geq 2$, by $x_i$. So we can restrict our attention to multilinear polynomials. Claim: The polynomials $\{ \prod_{i \in S} x_i : ...


26

Let $p$ be a polynomial such that for all $x\in \{0,1\}^n$, $p(x) = \sf{OR}(x)$. Consider the symmetrization of the polynomial $p$: $$q(k) = \frac{1}{\binom{n}{k}} \sum_{x: |x| = k} p(x).$$ Note that, since the OR function is a symmetric boolean function, we have that for $k = 1, 2, \ldots, n$, $q(k) = 1$, and $q(0) = 0$. Since $q-1$ is a non-zero ...


22

Your problem is NP-hard, even for polynomials of degree 2. The crucial reference is Theodore Motzkin and Ernst Strauss (1965) "Maxima for graphs and a new proof of a theorem of Turan" Canadian Journal of Mathematics 17, pp 533-540 Motzkin and Strauss consider an undirected graph $G=(V,E)$ with vertex set $V=\{1,2,\ldots,n\}$. They show that ...


11

There is a more general question on mathoverflow. I asked a similar question on CS.SE. jbapple provided a good answer. To quote "Necklaces, Convolutions, and X+Y", By Bremner et al. shows a $O\left(\frac{n^2(\lg \lg n)^3}{\lg^2 n}\right)$ algorithm for this problem on the real RAM and a $O(n \sqrt{n})$ algorithm in the nonuniform linear decision ...


10

I used a Gröbner basis to help find a short proof of a new dichotomy theorem for #CSP problems over 3-regular graphs with a single binary constraint function that has complex weights (arXiv version). There is natural equivalence relation over the set of constraint functions, namely, $f \sim g$ if $\#\operatorname{CSP}(f) = \#\operatorname{CSP}(g)$ for all ...


10

[tl;dr] A lot is known, and it is a very active area! [/tl;dr] It is important to specify the representation of the input polynomials, since it they are given as lists of coefficients or nonzero monomials, the problem is trivial. Thus one usually assumes the polynomials to be given as arithmetic circuits (a.k.a. straight-line programs). And the general case ...


10

The question seems quite open ended. Or perhaps you wish to have a precise characterization of the time-complexity of any possible symmetric polynomial over finite fields? In any case, at least to my knowledge, there are several well-known results about the time-complexity of computing symmetric polynomials: If $f$ is an elementary symmetric polynomial ...


9

You can decide if a quadratic polynomial $p: \mathbb{R}^n \rightarrow \mathbb{R}$ has real roots with some linear algebra. As you note, the general case should be hard. Observe first that $p(x) \neq 0$ for all $x \in \mathbb{R}^n$ if either $p(x) > 0$ or $p(x) < 0$ for all $x$ (this follows by continuity). So it is enough to be able to decide if $p(x) ...


9

In proof complexity the use of Gröbner bases has been proposed by Clegg, Edmonds, Impagliazzo to refute CNFs. There are cases in which this proof system outperforms Resolution exponentially but it does not seem to me that there is a real performance improvement for general instances. It is also true that many of the lower bounds for Resolution hold for ...


9

Well done on your independent discovery. This is a Hadamard matrix of Sylvester type, written in a different order. There is a massive literature on this topic. It is used in coding theory, cryptography, is directly related to Reed-Muller codes of degree 1, it can be used to obtain best affine approximations of functions, etc. Ryan O'Donnell's notes on ...


8

It’s not exactly clear to me what is the input of the problem and how do you enforce the restriction $p=2^{\Omega(n)}$, however, under any reasonable formulation the answer is no for multivariate polynomials unless NP = RP, due to the reduction below. Given a prime power $q$ in binary and a Boolean circuit $C$ (wlog using only $\land$ and $\neg$ gates), we ...


8

Yes, your problem is NP-hard, by reduction from THREE-SATISFIABILITY. THREE-SATISFIABILITY: Instance: Boolean variables $u_1,\ldots,u_n$; clauses $c_1,\ldots,c_m$ of length three over the $u_i$ Question: Does there exist a truth setting of the $u_i$ that makes all clauses $u_j$ true? For every Boolean variable $u_i$, introduce a corresponding real ...


7

Yes, assuming you want both $f_1(x)$ and $f_2(x)$ with integer coefficients. One of the reasons why LLL is so popular is precisely because it gives a polynomial time algorithm to factor polynomials with integer coefficients. For an excellent introduction, I recommend C. Yap's "Fundamental Problems in Algorithmic Algebra" (available online, for free), ...


7

For the question of when does $p=0 \Rightarrow q=0$, randomness can indeed help, as follows. First, factor $p$ (uses randomness when $p$ is given as a straight-line program; doesn't need randomness if $p$ is given as a coefficient vector). Let $\tilde{p}$ denote the square-free version of $p$ - that is, if $p=p_1^{k_1} p_2^{k_2} \dotsb p_\ell^{k_\ell}$ then $...


7

Your idea generalizes as follows: given an algebraic circuit (over the finite field) or Boolean circuit (computing the bit-wise representation of your finite field elements) computing $P$, then maintain the value at each gate in the circuit. When you change the $i$-th bit of $y$, simply propagate that change along the DAG of the circuit, starting from the ...


7

It's easy, and in fact I suspect your proof that the "degree-3 version is NP-hard" is flawed somewhere, since the degree-3 version is also easy. Here's the argument for degree-2: Suppose our constraint is $p(x) = 1$, and assume, since we're only interested in $p$ as a function, that it is reduced mod $x_i^2 = x_i$ (ie that it's multilinear). We can plug in ...


6

Grobner bases are used for the fastest list decoding algorithms for Reed-Solomon codes: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.320.1170&rep=rep1&type=pdf


6

Let me give some details for the Cauchy matrix construction, which is simple. Let $x = (x_1, \ldots, x_n)$, $y = (y_1, \ldots, y_m)$ be sequences of pairwise distinct numbers. The corresponding Cauchy matrix is $$ C = \begin{pmatrix} \frac{1}{x_1 - y_1} & \frac{1}{x_1 - y_2} & \ldots & \frac{1}{x_1 - y_m}\\ \frac{1}{x_2 - y_1} & \frac{1}{x_2 -...


6

Here is at least some upper bound: treat the polynomial $\mathbb{C}^n \to \mathbb{C}$ as $\mathbb{R}^{2n} \to \mathbb{R}^2$, and then ask in the first order theory of the reals if $p(x)=0$ implies that the imaginary part of each coordinate of $x$ is nonpositive. This can be solved in $\mathsf{PSPACE}$ (e.g. http://en.wikipedia.org/wiki/...


6

Firstly it is well-known that the approximate degree of $\mathrm{AND}$ is $O(\sqrt{n})$: Theorem 1. For all $n$ and $\varepsilon>0$, there exists a multilinear polynomial $p : \{\pm 1\}^n \to \mathbb{R}$ of degree $O(\sqrt{n}\log(1/\varepsilon))$ such that $|p(x)-\mathrm{AND}(x)|\leq \varepsilon$ for all $x \in \{\pm 1\}^n$. Proof. We use the Chebyshev ...


6

I believe the $\epsilon$-approximate degree of AND is known (up to constants) and is $\text{deg}_{\epsilon}(\text{AND}_n)= \Theta(\sqrt{n\log(1/\epsilon)})$. Indeed, the degree gets higher as you demand better approximations, eventually reaching $\Omega(n)$ once you want exponentially small error. This result has probably been reproved many times in the ...


6

If I understand your question correctly, the answer is no (independently from the field, assuming $\mathsf{VP}\neq\mathsf{VNP}$).


6

The question seems to be based on false premises, so let me try to deconfuse it. Solvability of systems of polynomial equations with integer coefficients is NP-hard over any fixed field (or integral domain). For instance, it is straightforward to reduce the satisfiability of a 3-CNF $\phi(x_1,\dots,x_k)$ to the solvability of a polynomial system including $\...


5

Here is an alternative to the answer by R B ; It is somewhat simpler, but has the disadvantage of an increase in degree. Simply take $g(x) = x^{2n}f(x)f(-x)f(1/x)f(-1/x)$.


5

The paper "Random low-degree polynomials are hard to approximate" by Ben-Eliezer, Hod, and Lovett answers your question. They show strong bounds on the correlation of random polynomials of degree $d$ with polynomials of degree at most $d-1$, by analyzing the bias of random polynomials. See their Lemma 2: the bias of a random degree-$d$ polynomial (up to some ...


5

Your question is equivalent to tail bounds on the weight distribution of Reed-Muller codes. Understanding weight distribution of Reed-Muller codes is an old and challenging question in coding theory, and several interesting results are known about it (the weight distribution is completely understood only for $d=1$ and $d=2$). As a great starting point, see "...


5

Would this work? What is wrong? No proof sketch that this is a polynomial time algorithm is given. The point where the algorithm might stop being a polynomial time algorithm is step 3: Being a univariate polynomial, it is trivial to normalise this polynomial and check if it is identically 0 or not. Even so normalising a univariate polynomial is ...


5

This case is still NP-hard. Suppose we have an instance of 3-SAT: $F=C_1\wedge\ldots\wedge C_n; C_i=L_{i,1}\vee L_{i,2}\vee L_{i,3}$, where each literal $L_{i,j}$ is either $V$ or $\neg V$ for some boolean variable $V\in Var$. We can translate this into an equivalent system of equations $f_{i,j}=0$ for $i=1,\dots,n$ and $1\le j\le 4$, where each $f_{i,j}$ ...


5

It's easy to modify your monomial-storing approach so that each update takes time only proportional to the number of changed monomials: just update the total polynomial value by adding the new value and subtracting the old value for each changed monomial. If you have a read-once formula for $P$ (i.e. every variable appears at a single leaf of the formula ...


5

The decision version of this problem is obviously in $\mathsf{NP}$, and Manders & Adleman showed that a specific case is NP-complete. Namely, even deciding whether there exists an integer $x \in [0, \gamma]$ such that $x^2 \cong \alpha \mod \beta$ (the input here is the triple $(\alpha,\beta,\gamma)$) is NP-complete, which is only one variable and degree ...


Only top voted, non community-wiki answers of a minimum length are eligible