Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SPARSE POLYNOMIALS:
Reports tagged with Sparse polynomials:
TR99-027 | 17th July 1999
Marek Karpinski, Igor E. Shparlinski

On the computational hardness of testing square-freeness of sparse polynomials

We show that deciding square-freeness of a sparse univariate
polynomial over the integer and over the algebraic closure of a
finite field is NP-hard. We also discuss some related open
problems about sparse polynomials.

more >>>

TR10-023 | 23rd February 2010
Adam Klivans, Homin Lee, Andrew Wan

Mansour’s Conjecture is True for Random DNF Formulas

Revisions: 3

In 1994, Y. Mansour conjectured that for every DNF formula on $n$ variables with $t$ terms there exists a polynomial $p$ with $t^{O(\log (1/\epsilon))}$ non-zero coefficients such that $\E_{x \in \{0,1\}}[(p(x)-f(x))^2] \leq \epsilon$. We make the first progress on this conjecture and show that it is true for several natural ... more >>>


TR11-044 | 25th March 2011
Shubhangi Saraf, Sergey Yekhanin

Noisy Interpolation of Sparse Polynomials, and Applications

Let $f\in F_q[x]$ be a polynomial of degree $d\leq q/2.$ It is well-known that $f$ can be uniquely recovered from its values at some $2d$ points even after some small fraction of the values are corrupted. In this paper we establish a similar result for sparse polynomials. We show that ... more >>>


TR14-168 | 8th December 2014
Ilya Volkovich

Deterministically Factoring Sparse Polynomials into Multilinear Factors

We present the first efficient deterministic algorithm for factoring sparse polynomials that split into multilinear factors.
Our result makes partial progress towards the resolution of the classical question posed by von zur Gathen and Kaltofen in \cite{GathenKaltofen85} to devise an efficient deterministic algorithm for factoring (general) sparse polynomials.
We achieve ... more >>>


TR15-042 | 30th March 2015
Ilya Volkovich

Computations beyond Exponentiation Gates and Applications

In Arithmetic Circuit Complexity the standard operations are $\{+,\times\}$.
Yet, in some scenarios exponentiation gates are considered as well (see e.g. \cite{BshoutyBshouty98,ASSS12,Kayal12,KSS14}).
In this paper we study the question of efficiently evaluating a polynomial given an oracle access to its power.
That is, beyond an exponentiation gate. As ... more >>>


TR18-032 | 14th February 2018
Gil Cohen, Bernhard Haeupler, Leonard Schulman

Explicit Binary Tree Codes with Polylogarithmic Size Alphabet

This paper makes progress on the problem of explicitly constructing a binary tree code with constant distance and constant alphabet size.

For every constant $\delta < 1$ we give an explicit binary tree code with distance $\delta$ and alphabet size $(\log{n})^{O(1)}$, where $n$ is the depth of the tree. This ... more >>>


TR18-130 | 16th July 2018
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree

In this paper we study the problem of deterministic factorization of sparse polynomials. We show that if $f \in \mathbb{F}[x_{1},x_{2},\ldots ,x_{n}]$ is a polynomial with $s$ monomials, with individual degrees of its variables bounded by $d$, then $f$ can be deterministically factored in time $s^{\poly(d) \log n}$. Prior to our ... more >>>




ISSN 1433-8092 | Imprint