# Questions tagged [polynomials]

The tag has no usage guidance.

118 questions
Filter by
Sorted by
Tagged with
82 views

### Multipoint evaluation in Lagrange basis

Setup. Let $\mathbb{F}$ be a finite field with a multiplicative subgroup $E = \{e_1, \dots, e_k\}$ of order $k$. Given a list $y = y_1, \dots, y_k\in \mathbb{F}$ let $p$ be the unique polynomial of ...
182 views

### Polynomial Identity Testing for $\prod \sum \prod$

I am reading a survey on polynomial identity testing by Saxena. On page 6 he writes that PIT for depth-3 circuits of the form $\prod \sum \prod$ is trivial. He gives no citation and as such I believe ...
52 views

• 23
156 views

• 13.1k
97 views

### Sparsity Bounds for Probabilistic Polynomials

Has there been any research done on proving sparsity lower bounds for probabilistic polynomials (over the Reals) for Majority? A probabilistic polynomial is a distribution of polynomials $D$ such that ...
• 71
255 views

### Extracting coefficients of polynomials given by straight line programs

Consider a straight line program of length $L$ that takes one input $x \in \mathbb{R}$ and computes a polynomial $p(x)$, using only addition, multiplication (including multiplication by constants). ...
• 3,263
198 views

• 1,242
243 views

• 1,145
252 views

### Testing emptiness property complexity in Sum of Squares Proof systems

Take the set $$\mathcal T=\{f_1(x_1,\dots,x_n)=\dots=f_m(x_1,\dots,x_n)=0, h_1(x_1,\dots,x_n)\geq a_1,\dots,h_t(x_1,\dots,x_n)\geq a_t\}$$ where h_1(x_1,\dots,x_n),\dots,h_t(x_1,\dots,x_n)\in\mathbb ...
• 539
1 vote