# Tagged Questions

The tag has no usage guidance.

15 views

### Optimal evaluation of polynomials / rational functions

A common way to compute the value a polynomial is to write it in Horner form. However, this isn't always the fastest way to evaluate it. Setting aside concerns of numerical precision, take the ...
87 views

### Algebraic dependence of roots of irreducibles over a finite field

I asked this question in Math SE too, but I have since modified it to make it more suited here. Also, in hindsight, the question itself was more algorithmic and was a better fit here. http://math....
61 views

### Approximating circuits with polynomial of low degree, can't understand small detail in the proof

I'm looking at the proof of this lemma: Lemma For every integer $t>0$, there exists a (proper) polynomial of total degree $(2t)^d$ that differs with $C$ on at most $size(C) 2^{n-t}$ inputs Where ...
49 views

### Identity testing of margins of boolean functions

Consider a boolean function $f(\vec{x},\vec{y})$, we define an (integer-valued) function $g(\vec{x})=\sum_{\vec{y}}f(\vec{x},\vec{y})$, i.e., $g$ can be considered as a (sort of) margin of $f$. The ...
109 views

139 views

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

Just a warning, I am an amateur and this algorithm probably doesn't work. A high level description of the algorithm: Be $f(x_1,...,x_n)$ a polynomial, $n$ the number of variables and $d$ is the ...
299 views

186 views

### Counting small terms in a determinant calculation over polynomials (counting spanning trees by weight)

I have a $n\times n$ matrix $A$. It's terms are $a_{ij}=-x^{w_{ij}}$ if $i\neq j$ and $a_{ii}=\sum_{j=0}^{n+1} x^{w_{ij}}$ on the diagonal. The matrix is symmetric as $w_{ij}=w_{ji}$. Numbers $w_{ij}$ ...
507 views

### Find the remainder of a large fixed polynomial when divided by a small unknown polynomial

Assume we operate in a finite field. We are given a large fixed polynomial p(x) (of, say, degree 1000) over this field. This polynomial is known beforehand and we are allowed to do computation using a ...
504 views

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

EDIT (v2): Added a section at the end on what I know about the problem. EDIT (v3): Added discussion on threshold degree at the end. Question This question is mainly a reference request. I don't ...
250 views

### What are some results on algorithms that estimate polynomials over a given set of points?

There seem to be many randomized algorithms for polynomial identity testing, checking whether or not a given polynomial is zero. Are there any results of algorithms that do some sort of estimation of ...
321 views

### What's the bias of random polynomials with low degree over GF(2)?

I have a question concerning low-degree polynomials and probability: What is the (assyptotic behavior of the) probability that a random* polynomial, $p$, over GF(2), with degree $\le d$ and n ...
337 views

### Looking for an operator on polynomials

I have a small, self-contained, math question, whose motivation is from theoretical computer science (specifically, list decoding of algebraic codes, derivative/multiplicity codes, etc). I wonder ...
133 views

### Parallel algorithms to find the optimum of polynomials

Are there any non-trivial parallel algorithms to find the optimum (local or global) of polynomials? By trivial, I mean something which is an obvious application of a serial algorithm. For example, one ...
128 views

### Computing the Fourier-Walsh coefficients of an arithmetic circuit

Given an $f$-fan in arithmetic circuit of depth $d$ over $GF(q)$ (for some prime $q$) and the set of variables $(x_1,\ldots,x_n)$, what is the state of the art upper bound for calculating the Fourier-...
223 views

### Results in computer science via the Stepanov method

I recently attended a Workshop on Pseudorandomness in Chennai Mathematical Institute on Pseudorandomness. Venkat Guruswami made the following beautiful statement in passing during his talk (on coding ...
433 views

### Systematic studies of sum of quadratic polynomials squared

I'm wondering if there exists systematic studies of sums of quadratic forms squared, similar to the quadratic forms, which is practically reflected in eigenvalue decomposition (that has huge practical ...
2k views

### Gröbner bases in TCS?

Does anyone know of interesting applications of Gröbner bases to theoretical computer science? Gröbner bases are used to solve multi-variate polynomial equations, an NP-hard problem in general. I was ...
664 views

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

Suppose we have polynomials $p_1,...,p_m$ of degree at most $n$, $n>m$, such that the total number of nonzero coefficients is $n$ (i.e., the polynomials are sparse). I am interested in an efficient ...
199 views

### Is there an interpretation of the degree of the polynomial computed by the arithmetization of a boolean formula?

If I understand this correctly, arithmetizating a formula is a way of "interpolating" a polynomial in such a way that polynomial evaluated on 0's and 1's corresponds to "unsatisfiable" if it is a root,...