Name
Abstract | ||
|---|---|---|
We study the complexity of deciding whether a given homogeneous multivariate polynomial has a nontrivial root over a finite field. Given a homogeneous algebraic circuit $C$ that computes an $n$-variate polynomial $p(x)$ of degree $d$ over a finite field $\mathbb{F}_q$, we wish to determine if there exists a nonzero $x \in \F_q^n$ with $C(x) = 0$. For constant $n$ there are known algorithms for doing this efficiently. However for linear $n$, the problem becomes \NP hard. In this paper, using interesting algebraic techniques, we show that if $d$ is prime and $n d/2$, the problem can be solved over sufficiently large finite fields in randomized polynomial time. We complement this result by showing that relaxing any of these constraints makes the problem intractable again. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1109/CCC.2008.36 | IEEE Conference on Computational Complexity |
Keywords | Field | DocType |
homogeneous algebraic circuit,detecting rational points,interesting algebraic technique,nontrivial root,variate polynomial,finite fields,finite field,large finite field,randomized polynomial time,homogeneous multivariate polynomial,construction industry,testing,linear algebra,np hard problem,algebra,polynomials,rational point,galois fields,history,circuits,gaussian processes,computational complexity | Polynomial identity testing,Discrete mathematics,Combinatorics,Finite field,Algebraic number,Polynomial,Chevalley–Warning theorem,Homogeneous polynomial,Time complexity,Mathematics,Computational complexity theory | Conference |
ISSN | Citations | PageRank |
1093-0159 | 2 | 0.41 |
References | Authors | |
6 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Swastik Kopparty | 1 | 384 | 32.89 |
| Sergey Yekhanin | 2 | 983 | 52.33 |