The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
In this paper we give the first construction of a pseudorandom generator, with seed length O(log n), for CC0[p], the class of constant-depth circuits with unbounded fan-in MODp gates, for some prime p. More accurately, the seed length of our generator is O(log n) for any constant error ϵ > 0. In fact, we obtain our generator by fooling distributions generated by low degree polynomials, over Fp,...
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 modulo p must have high complexity in every other characteristic q. More precisely, we...
In this paper we give reconstruction algorithms for depth-3 arithmetic circuits with k multiplication gates (also known as SigmaPiSigma(k) circuits), where k=O(1). Namely, we give an algorithm that when given a black box holding a SigmaPiSigma(k) circuit C over a field F as input, makes queries to the black box (possibly over a polynomial sized extension field of F) and outputs a circuit C' computing...
In this paper we consider the problem of determining whether an unknown arithmetic circuit, for which we have oracle access, computes the identically zero polynomial. This problem is known as the black-box polynomial identity testing (PIT) problem. Our focus is on polynomials that can be written in the form f(xmacr) = Sigmai=1k hi(xmacr) ldr gi(xmacr), where each hi is a polynomial that depends on...
A noisy interpolating set (NIS) for degree d polynomials is a set S sube Fn, where F is a finite field, such that any degree d polynomial q isin F[x1,..., xn] can be efficiently interpolated from its values on S, even if an adversary corrupts a constant fraction of the values. In this paper we construct explicit NIS for every prime field Fp and any degree d. Our sets are of size O(nd) and have efficient...
In this paper we study the problem of explicitly constructing a dimension expander: Let Fn be the n dimensional linear space over the field F. Find a small (ideally constant) set of linear transformations from Fn to itself {Ai}iisinI such that for every linear subspace V C Fn of dimension dim(V) < n/2 we have dim (SigmaiisinIAi(V)) ges(1+alpha)ldrdim(V), where alpha > 0 is some constant. In...
We consider the problem of approximating the support size of a distribution from a small number of samples, when each element in the distribution appears with probability at least 1/n. This problem is closely related to the problem of approximating the number of distinct elements in a sequence of length n. For both problems, we prove a nearly linear in n lower bound on the query complexity, applicable...
We construct an explicit polynomial f(x1,..., xn), with coefficients in {0, 1}, such that the size of any syntactically multilinear arithmetic circuit computing f is at least Omega{n4/3 log2 n} The lower bound holds over any field.
In this work we give two new constructions of epsi-biased generators. Our first construction answers an open question of Dodis and Smith (2005), and our second construction significantly extends a result of Mossel et al. (2003). In particular we obtain the following results: (1) We construct a family of asymptotically good binary codes such that the codes in our family are also epsi-biased sets for...
Abstract. In this paper we prove quadratic lower bounds for depth-3 arithmetic circuits over fields of characteristic zero. Such bounds are obtained for the elementary symmetric functions, the (trace of) iterated matrix multiplication, and the determinant. As corollaries we get the first nontrivial lower bounds for computing polynomials of constant degree, and a gap between the power of depth-3 arithmetic...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.