# Tag Info

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" ...
• 5,712

### 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 ...
• 4,400

### 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 ...
• 1,899
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, ...
• 1,986
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 ...
• 14.8k
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$ ...
• 5,712
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 ...
• 35.7k

### 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 ...
• 1,419
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}$).
• 4,400
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 ...
• 14.8k

### 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 ...
• 13.3k

• 35.7k