24 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" ...
user avatar
  • 5,712
10 votes

On derandomizing polynomial identity testing

[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 ...
user avatar
  • 4,400
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 ...
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, ...
user avatar
  • 1,986
8 votes
Accepted

Randomized identity-testing for high degree polynomials?

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 ...
user avatar
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$ ...
user avatar
  • 5,712
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 ...
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 ...
user avatar
6 votes
Accepted

Complexity of multi-linear polynomial computing Boolean function

If I understand your question correctly, the answer is no (independently from the field, assuming $\mathsf{VP}\neq\mathsf{VNP}$).
user avatar
  • 4,400
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 ...
user avatar
6 votes

Does approximation degree of AND depend on error?

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 ...
user avatar
6 votes

Does approximation degree of AND depend on error?

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 \...
user avatar
  • 2,743
6 votes

What do we know about checking real-stability of multivariate complex polynomials?

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 ...
user avatar
6 votes
Accepted

Is there a polynomial time algorithm for creating a set of vectors in general position?

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 ...
user avatar
6 votes

Gröbner bases in TCS?

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
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 ...
user avatar
  • 166
5 votes

Root finding in [0,1]

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)$.
user avatar
5 votes
Accepted

Idea for a white-box PIT deterministic algorithm in polynomial time

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 ...
user avatar
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 ...
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 ...
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 [...
user avatar
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) = ...
user avatar
  • 8,228
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'...
user avatar
  • 5,261
4 votes

Classes of boolean functions where reasonable lower bounds on approximate degree is unknown?

If I understand correctly you are asking about the relationship between the degree necessary for exact representation and the degree necessary for approximate representation. The seminal paper by ...
user avatar
  • 7,469
4 votes
Accepted

Root finding in [0,1]

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)$)....
user avatar
  • 9,378
4 votes

Alternative proofs of Schwartz–Zippel lemma

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 ...
user avatar
  • 190
4 votes

Is there a polynomial time algorithm for creating a set of vectors in general position?

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,$...
user avatar
  • 1,986
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 ...
user avatar
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 ...
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$ ...
user avatar
  • 1,422

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