The polynomials tag has no wiki summary.
1
vote
0answers
62 views
Verifying the minimum degree of a geometric predicate
Let $F = (f_1, \ldots, f_n)$ be a sequence of multivariate polynomials $f_i : \mathbb{R}^d \to \mathbb{R}$, and $g : \{0,1\}^n \to \{0,1\}$ a boolean function. Say the composition
...
7
votes
0answers
120 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}$ ...
9
votes
3answers
231 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 ...
17
votes
0answers
334 views
Approximate degree of $\textrm{AC}^0$
EDIT (v2): Added a section at the end on what I know about the problem.
Question
This question is mainly a reference request. I don't know much about the problem. I want to know if there has been ...
7
votes
1answer
209 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 ...
12
votes
2answers
205 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 ...
15
votes
0answers
300 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 ...
2
votes
1answer
118 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 ...
7
votes
0answers
108 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 ...
6
votes
1answer
168 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 ...
8
votes
1answer
316 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 ...
27
votes
10answers
1k 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 ...
16
votes
2answers
480 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 ...
5
votes
0answers
177 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 ...
11
votes
1answer
209 views
Explicit polynomials in 1 variable with superlogarithmic circuit complexity lower bounds?
By counting arguments, one can show that there exist polynomials of degree n in 1 variable (i.e., something of the form $a_n x^n + a_{n-1} x^{n-1} + \cdots + a_0)$ which have circuit complexity n. ...
3
votes
1answer
162 views
Applications of association schemes to complexity theory and other TCS
An association scheme is defined as a pair $(V, R_0,R_1, \ldots,R_{n+1})$ of a set $V$ and relations $R_i$ on $V$ such that
$(x,y) \in R_i$ implies $(y,x) \in R_i$ for all $x, y \in V$.
$R_0 = \{ ...
11
votes
2answers
264 views
Evaluating the multilinearization of an arithmetic circuit?
Let $p(x_1,\ldots,x_n)$ be a multi-variate polynomial with coefficients over a field $F$. The multilinearization of $p$, denoted by $\hat{p}$, is the result of repeatedly replacing each $x_i^d$ with ...
27
votes
2answers
542 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 ...
0
votes
1answer
385 views
How to compute ROOK Polynomials for NxM Matrices [closed]
How to compute ROOK Polynomials for NxM Matrices for k objects ?
4
votes
1answer
415 views
What is the running time of taking a limit?
I'm interested in finding the running time(s) for determining mathematical limits.
For instance, $\lim_{x \to 2} \frac{1}{x} = \frac{1}{2}$.
I'd like to know more about algorithms for determining ...
2
votes
0answers
234 views
Some problems involving polynomials of public and private variables over GF(2).
Suppose there are a set of low degree (less than some degree $z$) polynomials $P_0, P_1, ..., P_k$ each of which is defined over two types of variables, red variables ${v_r}_0, {v_r}_1, ..., {v_r}_n$ ...
34
votes
1answer
2k views
Multiplying n polynomials of degree 1
The problem is to compute the polynomial $(a_1 x + b_1) \times \cdots \times (a_n x + b_n)$. Assume that all coefficients fit in a machine word, i.e. can be manipulated in unit time.
You can do $O(n ...
