# Questions tagged [polynomials]

The tag has no usage guidance.

7 questions
Filter by
Sorted by
Tagged with
2k views

### Alternative proofs of Schwartz–Zippel lemma

I'm only aware of two proofs of Schwartz–Zippel lemma. The first (more common) proof is described in the wikipedia entry. The second proof was discovered by Dana Moshkovitz. Are there any other ...
651 views

### What are some efficient algorithms for determining if a quadratic multivariate polynomial has a solution?

I know that in general, multivariate polynomial satisfiability is equivalent to 3-SAT; however, I'm wondering if there are any good techniques in the quadratic case, specifically if there is a ...
875 views

### Polynomial method for complexity results

Polynomial methods, say Combinatorial Nullstellensatz and Chevalley–Warning theorem are powerful tools in additive combinatorics. By representing a problem with proper polynomials, they can guarantee ...
308 views

### Complexity of multi-linear polynomial computing Boolean function

Let $f:\{0,1\}^{n}\longmapsto\{0,1\}$ be a Boolean function. As usual, let $C(f)$ denote circuit complexity of $f$, i.e, the size of the smallest Boolean circuit computing $f$. As we know that every ...
155 views

### A special case of the boolean multivariate quadratic polynomial problem

It's well known that in the general case, the boolean MQ problem: given $(f_1, \ldots, f_n) \in \mathbb{F}_2[x_1, \ldots, x_m]$ with $\deg(f_i) = 2$, can we find a solution $\vec{y}: f_i(\vec{y}) = 0$...