Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > POLYNOMIAL:
Reports tagged with polynomial:
TR04-070 | 22nd June 2004
Leonid Gurvits

Combinatorial and algorithmic aspects of hyperbolic polynomials

Let $p(x_1,...,x_n) =\sum_{ (r_1,...,r_n) \in I_{n,n} } a_{(r_1,...,r_n) } \prod_{1 \leq i \leq n} x_{i}^{r_{i}}$
be homogeneous polynomial of degree $n$ in $n$ real variables with integer nonnegative coefficients.
The support of such polynomial $p(x_1,...,x_n)$
is defined as $supp(p) = \{(r_1,...,r_n) \in I_{n,n} : a_{(r_1,...,r_n)} \neq 0 ... more >>>


TR07-081 | 10th August 2007
Andrej Bogdanov, Emanuele Viola

Pseudorandom bits for polynomials

We present a new approach to constructing pseudorandom generators that fool low-degree polynomials over finite fields, based on the Gowers norm. Using this approach, we obtain the following main constructions of explicitly computable generators $G : \F^s \to \F^n$ that fool polynomials over a prime field $\F$:
\begin{enumerate}
\item a ... more >>>


TR07-132 | 8th December 2007
Emanuele Viola

The sum of d small-bias generators fools polynomials of degree d

We prove that the sum of $d$ small-bias generators $L
: \F^s \to \F^n$ fools degree-$d$ polynomials in $n$
variables over a prime field $\F$, for any fixed
degree $d$ and field $\F$, including $\F = \F_2 =
{0,1}$.

Our result improves on both the work by Bogdanov and
Viola ... more >>>


TR09-035 | 26th March 2009
Nicola Galesi, Massimo Lauria

On the Automatizability of Polynomial Calculus

We prove that Polynomial Calculus and Polynomial Calculus with Resolution are not automatizable, unless W[P]-hard problems are fixed parameter tractable by one-side error randomized algorithms. This extends to Polynomial Calculus the analogous result obtained for Resolution by Alekhnovich and Razborov (SIAM J. Computing, 38(4), 2008).

more >>>

TR11-039 | 19th March 2011
Frederic Green, Daniel Kreymer, Emanuele Viola

In Brute-Force Search of Correlation Bounds for Polynomials

We report on some initial results of a brute-force search for determining the maximum correlation between degree-$d$ polynomials modulo $p$ and the $n$-bit mod $q$ function. For various settings of the parameters $n,d,p,$ and $q$, our results indicate that symmetric polynomials yield the maximum correlation. This contrasts with the previously-analyzed ... more >>>


TR12-144 | 6th November 2012
Rocco Servedio, Emanuele Viola

On a special case of rigidity

We highlight the special case of Valiant's rigidity
problem in which the low-rank matrices are truth-tables
of sparse polynomials. We show that progress on this
special case entails that Inner Product is not computable
by small $\acz$ circuits with one layer of parity gates
close to the inputs. We then ... more >>>


TR12-160 | 20th November 2012
Frederic Green, Daniel Kreymer, Emanuele Viola

Block-symmetric polynomials correlate with parity better than symmetric


We show that degree-$d$ block-symmetric polynomials in
$n$ variables modulo any odd $p$ correlate with parity
exponentially better than degree-$d$ symmetric
polynomials, if $n \ge c d^2 \log d$ and $d \in [0.995
\cdot p^t - 1,p^t)$ for some $t \ge 1$. For these
infinitely many degrees, our result ... more >>>


TR13-119 | 2nd September 2013
Emanuele Viola

Challenges in computational lower bounds

We draw two incomplete, biased maps of challenges in
computational complexity lower bounds. Our aim is to put
these challenges in perspective, and to present some
connections which do not seem widely known.

more >>>

TR13-139 | 7th October 2013
Peter Floderus, Andrzej Lingas, Mia Persson, Dzmitry Sledneu

Detecting Monomials with $k$ Distinct Variables

We study the complexity of detecting monomials
with special properties in the sum-product
expansion of a polynomial represented by an arithmetic
circuit of size polynomial in the number of input
variables and using only multiplication and addition.
We focus on monomial properties expressed in terms
of the number of distinct ... more >>>


TR13-141 | 8th October 2013
Leonid Gurvits

Boolean matrices with prescribed row/column sums and stable homogeneous polynomials: combinatorial and algorithmic applications

Revisions: 1

We prove a new efficiently computable lower bound on the coefficients of stable homogeneous polynomials and present its algorthmic and combinatorial applications. Our main application is the first poly-time deterministic algorithm which approximates the partition functions associated with
boolean matrices with prescribed row and (uniformly bounded) column sums within simply ... more >>>


TR15-122 | 29th July 2015
Shiteng Chen, Periklis Papakonstantinou

Correlation lower bounds from correlation upper bounds

We show that for any coprime $m,r$ there is a circuit of the form $\text{MOD}_m\circ \text{AND}_{d(n)}$ whose correlation with $\text{MOD}_r$ is at least $2^{-O\left( \frac{n}{d(n)} \right) }$. This is the first correlation lower bound for arbitrary $m,r$, whereas previously lower bounds were known for prime $m$. Our motivation is the ... more >>>


TR17-167 | 3rd November 2017
Chin Ho Lee, Emanuele Viola

More on bounded independence plus noise: Pseudorandom generators for read-once polynomials

Revisions: 1

We construct pseudorandom generators with improved seed length for
several classes of tests. First we consider the class of read-once
polynomials over GF(2) in $m$ variables. For error $\e$ we obtain seed
length $\tilde O (\log(m/\e)) \log(1/\e)$, where $\tilde O$ hides lower-order
terms. This is optimal up to the factor ... more >>>




ISSN 1433-8092 | Imprint