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 ...


23

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

[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

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), ...


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

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

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

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

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

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

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

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

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 ...


4

Here is what I think S. Nikolov meant. Take an $m\times m$ Vandermonde matrix $V(x_1,\ldots,x_m)$ where $V_{i,j}=x_i^{j-1}$ for $1\leq i,j\leq m.$ Take any $1\leq j_1<j_2<\ldots<j_n\leq m,$ so we assume $n\leq m$ here. Then for any choice of $1\leq i_1<i_2<\ldots<i_n\leq m$ the $n\times n$ submatrix formed by $$[V_{i_t,j_s}]_{1\leq t,s\...


4

Not sure if this is the right SE forum for it, but the answer is yes. I'll give the reduction in two steps: $f(x)$ has a root iff $h(x)$ has a root in [-1,1] (scaling, i.e. $h(x)=f(\alpha \cdot x)$). $h(x)$ has a root in [-1,1] iff $g(x)$ has a root in [0,1] (simply define $g(x)=h(\frac{x+1}{2})$). Let's prove 1: Let's assume $f(x)$ is of degree $n$ and ...


4

Schwartz-Zippel lemma is a special case of a theorem of Noga Alon and Zoltan Füredi as shown in Section 4 of this paper: On Zeros of a Polynomial in a Finite Grid, and hence any new proof of that theorem gives a new proof of Schwartz-Zippel. As of now, I know six different proofs, two of which appear in the paper and others are referenced there. The Alon-...


4

A paper by Mark Bun and Justin Thaler has been posted on ECCC very recently (mid-March 2017) that precisely answers this question: "A Nearly Optimal Lower Bound on the Approximate Degree of AC0" They claim that for any $\delta > 0$, there exists a function $f$ in $\mathrm{AC}^0$ such that $\widetilde{\mathrm{deg}}_{1/3}(f) = \Omega(n^{1-\delta})$, nearly ...


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