Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with polynomials:
TR98-017 | 29th March 1998
Oded Goldreich, Madhu Sudan

Computational Indistinguishability: A Sample Hierarchy.

We consider the existence of pairs of probability ensembles which
may be efficiently distinguished given $k$ samples
but cannot be efficiently distinguished given $k'<k$ samples.
It is well known that in any such pair of ensembles it cannot be that
both are efficiently computable
(and that such phenomena ... more >>>

TR98-043 | 27th July 1998
Venkatesan Guruswami, Madhu Sudan

Improved decoding of Reed-Solomon and algebraic-geometric codes.

We present an improved list decoding algorithm for decoding
Reed-Solomon codes. Given an arbitrary string of length n, the
list decoding problem is that of finding all codewords within a
specified Hamming distance from the input string.

It is well-known that this decoding problem for Reed-Solomon
codes reduces to the ... more >>>

TR98-060 | 8th October 1998
Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan

Learning polynomials with queries -- The highly noisy case.

This is a revised version of work which has appeared
in preliminary form in the 36th FOCS, 1995.

Given a function $f$ mapping $n$-variate inputs from a finite field
$F$ into $F$,
we consider the task of reconstructing a list of all $n$-variate
degree $d$ polynomials which agree with $f$
more >>>

TR99-018 | 8th June 1999
Manindra Agrawal, Somenath Biswas

Reducing Randomness via Chinese Remaindering

We give new randomized algorithms for testing multivariate polynomial
identities over finite fields and rationals. The algorithms use
\lceil \sum_{i=1}^n \log(d_i+1)\rceil (plus \lceil\log\log C\rceil
in case of rationals where C is the largest coefficient)
random bits to test if a
polynomial P(x_1, ..., x_n) is zero where d_i is ... more >>>

TR03-074 | 24th June 2003
Vince Grolmusz

Sixtors and Mod 6 Computations

We consider the following phenomenon: with just one multiplication
we can compute (3u+2v)(3x+2y)= 3ux+4vy mod 6, while computing the same polynomial modulo 5 needs 2 multiplications. We generalize this observation and we define some vectors, called sixtors, with remarkable zero-divisor properties. Using sixtors, we also generalize our earlier result ... more >>>

TR04-037 | 14th April 2004
Elmar Böhler, Christian Glaßer, Bernhard Schwarz, Klaus W. Wagner

Generation Problems

Given a fixed computable binary operation f, we study the complexity of the following generation problem: The input consists of strings a1,...,an,b. The question is whether b is in the closure of {a1,...,an} under operation f.

For several subclasses of operations we prove tight upper and lower bounds for the ... more >>>

TR05-040 | 13th April 2005
Scott Aaronson

Oracles Are Subtle But Not Malicious

Theoretical computer scientists have been debating the role of
oracles since the 1970's. This paper illustrates both that oracles
can give us nontrivial insights about the barrier problems in
circuit complexity, and that they need not prevent us from trying to
solve those problems.

First, we ... more >>>

TR05-143 | 29th November 2005
Parikshit Gopalan

Constructing Ramsey Graphs from Boolean Function Representations

Explicit construction of Ramsey graphs or graphs with no large clique or independent set has remained a challenging open problem for a long time. While Erdos's probabilistic argument shows the existence of graphs on 2^n vertices with no clique or independent set of size 2n, the best known explicit constructions ... more >>>

TR07-073 | 3rd August 2007
Parikshit Gopalan, Subhash Khot, Rishi Saket

Hardness of Reconstructing Multivariate Polynomials over Finite Fields

We study the polynomial reconstruction problem for low-degree
multivariate polynomials over finite fields. In the GF[2] version of this problem, we are given a set of points on the hypercube and target values $f(x)$ for each of these points, with the promise that there is a polynomial over GF[2] of ... more >>>

TR08-043 | 12th April 2008
Gábor Ivanyos, Marek Karpinski, Nitin Saxena

Schemes for Deterministic Polynomial Factoring

In this work we relate the deterministic
complexity of factoring polynomials (over
fields) to certain combinatorial objects we
m-schemes. We extend the known conditional
deterministic subexponential time polynomial
factoring algorithm for finite fields to get an
underlying m-scheme. We demonstrate ... more >>>

TR09-037 | 10th April 2009
Parikshit Gopalan

A Fourier-analytic approach to Reed-Muller decoding

We present a Fourier-analytic approach to list-decoding Reed-Muller codes over arbitrary finite fields. We prove that the list-decoding radius for quadratic polynomials equals $1 - 2/q$ over any field $F_q$ where $q > 2$. This confirms a conjecture due to Gopalan, Klivans and Zuckerman for degree $2$. Previously, tight bounds ... more >>>

TR09-048 | 29th May 2009
Parikshit Gopalan, Shachar Lovett, Amir Shpilka

On the Complexity of Boolean Functions in Different Characteristics

Every Boolean function on $n$ variables can be expressed as a unique multivariate polynomial modulo $p$ for every prime $p$. In this work, we study how the degree of a function in one characteristic affects its complexity in other characteristics. We establish the following general principle: functions with low degree ... more >>>

TR10-039 | 10th March 2010
Gil Cohen, Amir Shpilka

On the degree of symmetric functions on the Boolean cube

Comments: 1

In this paper we study the degree of non-constant symmetric functions $f:\{0,1\}^n \to \{0,1,\ldots,c\}$, where $c\in
\mathbb{N}$, when represented as polynomials over the real numbers. We show that as long as $c < n$ it holds that deg$(f)=\Omega(n)$. As we can have deg$(f)=1$ when $c=n$, our
result shows a surprising ... more >>>

TR10-092 | 22nd May 2010
Charanjit Jutla, Arnab Roy

A Completeness Theorem for Pseudo-Linear Functions with Applications to UC Security

Revisions: 1 , Comments: 1

We consider multivariate pseudo-linear functions
over finite fields of characteristic two. A pseudo-linear polynomial
is a sum of guarded linear-terms, where a guarded linear-term is a product of one or more linear-guards
and a single linear term, and each linear-guard is
again a linear term but raised ... more >>>

TR10-148 | 23rd September 2010
Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin

High-rate codes with sublinear-time decoding

Locally decodable codes are error-correcting codes that admit efficient decoding algorithms; any bit of the original message can be recovered by looking at only a small number of locations of a corrupted codeword. The tradeoff between the rate of a code and the locality/efficiency of its decoding algorithms has been ... more >>>

TR10-182 | 26th November 2010
Shachar Lovett

An elementary proof of anti-concentration of polynomials in Gaussian variables

Recently there has been much interest in polynomial threshold functions in the context of learning theory, structural results and pseudorandomness. A crucial ingredient in these works is the understanding of the distribution of low-degree multivariate polynomials evaluated over normally distributed inputs. In particular, the two important properties are exponential tail ... more >>>

TR10-189 | 8th December 2010
Neeraj Kayal, Chandan Saha

On the Sum of Square Roots of Polynomials and related problems

The sum of square roots problem over integers is the task of deciding the sign of a nonzero sum, $S = \Sigma_{i=1}^{n}{\delta_i}$ . \sqrt{$a_i$}, where $\delta_i \in$ { +1, -1} and $a_i$'s are positive integers that are upper bounded by $N$ (say). A fundamental open question in numerical analysis and ... more >>>

TR11-002 | 9th January 2011
Gil Cohen, Amir Shpilka, Avishay Tal

On the Degree of Univariate Polynomials Over the Integers

We study the following problem raised by von zur Gathen and Roche:

What is the minimal degree of a nonconstant polynomial $f:\{0,\ldots,n\}\to\{0,\ldots,m\}$?

Clearly, when $m=n$ the function $f(x)=x$ has degree $1$. We prove that when $m=n-1$ (i.e. the point $\{n\}$ is not in the range), it must be the case ... more >>>

TR11-094 | 20th June 2011
Shachar Lovett

Computing polynomials with few multiplications

A folklore result in arithmetic complexity shows that the number of multiplications required to compute some $n$-variate polynomial of degree $d$ is $\sqrt{{n+d \choose n}}$. We complement this by an almost matching upper bound, showing that any $n$-variate polynomial of degree $d$ over any field can be computed with only ... more >>>

TR12-044 | 22nd April 2012
Swastik Kopparty

List-Decoding Multiplicity Codes

We study the list-decodability of multiplicity codes. These codes, which are based on evaluations of high-degree polynomials and their derivatives, have rate approaching $1$ while simultaneously allowing for sublinear-time error-correction. In this paper, we show that multiplicity codes also admit powerful list-decoding and local list-decoding algorithms correcting a large fraction ... more >>>

TR12-053 | 30th April 2012
Ankur Moitra

A Singly-Exponential Time Algorithm for Computing Nonnegative Rank

Here, we give an algorithm for deciding if the nonnegative rank of a matrix $M$ of dimension $m \times n$ is at most $r$ which runs in time $(nm)^{O(r^2)}$. This is the first exact algorithm that runs in time singly-exponential in $r$. This algorithm (and earlier algorithms) are built on ... more >>>

TR12-134 | 22nd October 2012
Alexander Razborov, Emanuele Viola

Real Advantage

Revisions: 1

We highlight the challenge of proving correlation bounds
between boolean functions and integer-valued polynomials,
where any non-boolean output counts against correlation.

We prove that integer-valued polynomials of degree $\frac 12
\log_2 \log_2 n$ have zero correlation with parity. Such a
result is false for modular and threshold polynomials.
Its proof ... more >>>

TR12-184 | 26th December 2012
Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, Shachar Lovett

Every locally characterized affine-invariant property is testable.

Revisions: 1

Let $\mathbb{F} = \mathbb{F}_p$ for any fixed prime $p \geq 2$. An affine-invariant property is a property of functions on $\mathbb{F}^n$ that is closed under taking affine transformations of the domain. We prove that all affine-invariant property having local characterizations are testable. In fact, we show a proximity-oblivious test for ... more >>>

TR14-018 | 13th February 2014
Arnab Bhattacharyya

Polynomial decompositions in polynomial time

Fix a prime $p$. Given a positive integer $k$, a vector of positive integers ${\bf \Delta} = (\Delta_1, \Delta_2, \dots, \Delta_k)$ and a function $\Gamma: \mathbb{F}_p^k \to \F_p$, we say that a function $P: \mathbb{F}_p^n \to \mathbb{F}_p$ is $(k,{\bf \Delta},\Gamma)$-structured if there exist polynomials $P_1, P_2, \dots, P_k:\mathbb{F}_p^n \to \mathbb{F}_p$ ... more >>>

TR14-087 | 12th July 2014
Abhishek Bhowmick, Shachar Lovett

List decoding Reed-Muller codes over small fields

Revisions: 1

The list decoding problem for a code asks for the maximal radius up to which any ball of that radius contains only a constant number of codewords. The list decoding radius is not well understood even for well studied codes, like Reed-Solomon or Reed-Muller codes.

Fix a finite field $\mathbb{F}$. ... more >>>

TR14-163 | 29th November 2014
Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, Nitin Saurabh

Homomorphism polynomials complete for VP

The VP versus VNP question, introduced by Valiant, is probably the most important open question in algebraic complexity theory. Thanks to completeness results, a variant of this question, VBP versus VNP, can be succinctly restated as asking whether the permanent of a generic matrix can be written as a determinant ... more >>>

TR15-077 | 4th May 2015
Arnab Bhattacharyya, Abhishek Bhowmick

Using higher-order Fourier analysis over general fields

Higher-order Fourier analysis, developed over prime fields, has been recently used in different areas of computer science, including list decoding, algorithmic decomposition and testing. We extend the tools of higher-order Fourier analysis to analyze functions over general fields. Using these new tools, we revisit the results in the above areas.

... more >>>

TR15-096 | 5th June 2015
Abhishek Bhowmick, Shachar Lovett

Bias vs structure of polynomials in large fields, and applications in effective algebraic geometry and coding theory

Let $f$ be a polynomial of degree $d$ in $n$ variables over a finite field $\mathbb{F}$. The polynomial is said to be unbiased if the distribution of $f(x)$ for a uniform input $x \in \mathbb{F}^n$ is close to the uniform distribution over $\mathbb{F}$, and is called biased otherwise. The polynomial ... more >>>

TR16-025 | 26th February 2016
Shachar Lovett

The Fourier structure of low degree polynomials

Revisions: 1

We study the structure of the Fourier coefficients of low degree multivariate polynomials over finite fields. We consider three properties: (i) the number of nonzero Fourier coefficients; (ii) the sum of the absolute value of the Fourier coefficients; and (iii) the size of the linear subspace spanned by the nonzero ... more >>>

TR16-191 | 24th November 2016
Roei Tell

Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials

Revisions: 3

Goldreich and Wigderson (STOC 2014) initiated a study of quantified derandomization, which is a relaxed derandomization problem: For a circuit class $\mathcal{C}$ and a parameter $B=B(n)$, the problem is to decide whether a circuit $C\in\mathcal{C}$ rejects all of its inputs, or accepts all but $B(n)$ of its inputs.

In ... more >>>

TR19-026 | 28th February 2019
Pavel Hrubes, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao, Amir Yehudayoff

Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits

There are various notions of balancing set families that appear in combinatorics and computer science. For example, a family of proper non-empty subsets $S_1,\ldots,S_k \subset [n]$ is balancing if for every subset $X \subset \{1,2,\ldots,n\}$ of size $n/2$, there is an $i \in [k]$ so that $|S_i \cap X| = ... more >>>

ISSN 1433-8092 | Imprint