25 votes
Accepted

How "hard" is it to maximize a polynomial function subject to linear constraints?

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" ...
Gamow's user avatar
  • 5,772
23 votes
Accepted

Algebraic equivalent of SAT?

This is standard and widely used in computer science theory. There are many references that use boolean polynomials with False -> 0 and True -> 1, or in other words, a polynomial over GF(2) used ...
D.W.'s user avatar
  • 12k
12 votes

Algebraic equivalent of SAT?

I think what you are asking about is also known as "polynomial calculus" in proof complexity and SAT solving. It was introduced in [1, 2] to investigate whether coNP can be separated from NP ...
Martin Berger's user avatar
10 votes

Evaluating symmetric polynomials

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 ...
Iddo Tzameret's user avatar
9 votes
Accepted

a polynomial representation of boolean functions

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, ...
kodlu's user avatar
  • 2,070
8 votes
Accepted

Finding a positive point for a collection of polynomials

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$ ...
Gamow's user avatar
  • 5,772
7 votes
Accepted

Maintaining the value of a polynomial over a dynamically updated input

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 ...
Joshua Grochow's user avatar
7 votes

Hardness of finding roots of a degree $2$ polynomials over $\mathbb{F}_2$

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 ...
Andrew Morgan's user avatar
6 votes
Accepted

Existence of solution for a system of multi-variate polynomial equations and in-equations

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 ...
Emil Jeřábek's user avatar
5 votes
Accepted

Approximate degree of $\textrm{AC}^0$

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 ...
A.N.'s user avatar
  • 166
5 votes
Accepted

A special case of the boolean multivariate quadratic polynomial problem

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 ...
Klaus Draeger's user avatar
5 votes

Maintaining the value of a polynomial over a dynamically updated input

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 ...
David Eppstein's user avatar
5 votes
Accepted

Complexity of counting integer roots of multivariate polynomials in a polyhedron?

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 [...
Joshua Grochow's user avatar
5 votes
Accepted

Cost of Numerically Solving a System of P polynomials, each of V variables, and degree D to a Specific Accuracy

If the coefficients are roots of rational numbers, then they are in particular algebraic numbers. This means that you can encode the coefficients as additional polynomial constraints. So overall, you'...
Shaull's user avatar
  • 5,571
5 votes
Accepted

What is the polynomial representation of the Hamming weight function?

Here is the polynomial representation of any such function $f$: For any $y\in \{-1,1\}^n$, define polynomial $I_y(x) = 2^{-n}\prod_{i=1}^n 1+y_i x_i.$ Then for all $x\in\{-1,1\}^n$ we have $I_y(x) = ...
Neal Young's user avatar
  • 10.1k
4 votes
Accepted

Razborov-Smolensky polynomial argument on $\textrm{ACC}[q]$ where $q$ is a prime power

For the record, let me summarize what’s mentioned in the comments. It is a folklore fact that if $q=p^k$, then $\mathrm{AC}^0[p]=\mathrm{AC}^0[q]$. More specifically, $\mathit{MOD}_q$ gates are ...
Emil Jeřábek's user avatar
4 votes

Razborov-Smolensky polynomial argument on $\textrm{ACC}[q]$ where $q$ is a prime power

The result appears as Theorem 7 in the following paper by Smolensky: Smolensky, Roman. "On representations by low-degree polynomials." Proceedings of 1993 IEEE 34th Annual Foundations of Computer ...
Cyrus Rashtchian's user avatar
4 votes
Accepted

Extracting coefficients of polynomials given by straight line programs

This would contradict SETH by using a known hardness result for subset sum: https://arxiv.org/abs/1704.04546. In this paper it is shown that the subset sum problem with $n$ integers and target $T$ ...
Laakeri's user avatar
  • 1,767
3 votes
Accepted

Complexity of finding approximate solutions for systems of polynomial equations

The problem is complete for the existential theory of the reals ($\exists\mathbb{R}$). This implies that the problem is NP-hard and can be decided in PSPACE, and there are consequences for the ...
user66277's user avatar
  • 131
3 votes

What is the polynomial representation of the Hamming weight function?

These are given by the very widely studied Krawtchouk polynomials (a.k.a. the Fourier transform of the Hamming sphere): https://en.wikipedia.org/wiki/Kravchuk_polynomials
Mahdi Cheraghchi's user avatar
3 votes
Accepted

If a root||nonce Proof-of-Work certificate is prime, can it be used in any other interesting proofs?

Heuristically: Yes, I suspect this probably works, if the system of equations is committed to in advance (well before mining works), and if the system of equations is small enough. You'll need the ...
D.W.'s user avatar
  • 12k
3 votes

Hardness of finding roots of a degree $2$ polynomials over $\mathbb{F}_2$

It's not NP-hard, unless P=NP. There is a polynomial-time algorithm to determine whether a single quadratic polynomial $f(x_1,\dots,x_n)$ has any zeros over $\mathbb{F}_2$, and if it does, to output ...
D.W.'s user avatar
  • 12k
3 votes

Representing OR with polynomials

Yuval and Henry have given two different proofs of this fact. Here's a third proof. First, as in Yuval's answer we restrict our attention to multilinear polynomials. Now you have already exhibited a ...
Robin Kothari's user avatar
3 votes
Accepted

Lower bound for the Schwartz–Zippel lemma in Polynomial Hashing

I think a pragmatic approach would be to use a PRF (see also here) instead of a polynomial hash, because then you can say that the collision probability is $1/M$ (unless someone figures out how to ...
D.W.'s user avatar
  • 12k
3 votes

Coefficients of a determinant of a matrix of univariate polynomials is in $GapL$

Theorem 3.2 in this paper: https://doi.org/10.1007/s00224-003-1077-7 says this: Let B be an n × n matrix, whose entries are each polynomials of degree n in Z[x], where the coefficients of each ...
Eric Allender's user avatar
2 votes

Optimal evaluation of polynomials / rational functions

In Knuth Vol II Theorem E on page 494 he presents an algorithm that can evaluate a polynomial using $\frac{n}{2} + 2$ multiplications. The theoretical minimum is $\frac{n}{2}$, assuming generic ...
Remco Bloemen's user avatar
2 votes

Bivariate low-degree polynomial testing of Polishchuk-Spielman

If I understand it correctly, Gauss's lemma implies that that $P$ and $E$ have a non-trivial common factor over $\mathbb{F}[x,y]$. But in the beginning of the proof of Lemma 8 they assume without ...
Igor Shinkar's user avatar
  • 1,917
2 votes

How to find a non-zero point of a non-zero polynomial of low degree?

This does not directly answer your question, but if $f$ is $n$-variate, and is known to have partial degrees at most $D$ and at most $T$ terms, and $\mathbb{F}$ is known to contain an element $\omega$ ...
user41530's user avatar
2 votes

Computing sum of sparse polynomials squared in O(n log n) time?

Just wanted to note the natural approximation algorithm. This doesn't take advantage of sparsity though. You could use a random sequence $(\sigma_i)_{i\in[n]}$ Taking $X=\sum_i \sigma_i p_i(x)$ we ...
Thomas Ahle's user avatar

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