We consider the existence of pairs of probability ensembles which may be efficiently distinguished given $k$ samples but cannot be efficiently distinguished given $k'more >>>

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 >>>

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 the ... more >>>

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 (Computing ... more >>>

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 >>>

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 give an oracle relative ... more >>>

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 >>>

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 >>>

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

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 >>>

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 >>>

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 >>>