Search Results

We consider the following basic, and very broad, statistical problem: Given a known high-dimensional distribution D over ℝⁿ and a collection of data points in ℝⁿ, distinguish between the two possibilities that (i) the data was drawn from D, versus (ii) ...

We give a pseudorandom generator that fools degree-d polynomial threshold functions over n-dimensional Gaussian space with seed length d ^O(logd) · logn. All previous generators had a seed length with at least a 2 ^d dependence on d.

The key new ...

We show that a very simple pseudorandom generator fools intersections of k linear threshold functions (LTFs) and arbitrary functions of k LTFs over n-dimensional Gaussian space. The two analyses of our PRG (for intersections versus arbitrary functions ...

The degree-d Chow parameters of a Boolean function are its degree at most d Fourier coefficients. It is well-known that degree-d Chow parameters uniquely characterize degree-d polynomial threshold functions (PTFs) within the space of all bounded ...

We construct and analyze a pseudorandom generator for degree 2 boolean polynomial threshold functions. Random constructions achieve the optimal seed length of [EQUATION], however the best known explicit construction of [8] uses a seed length of O(log n ·...

The threshold degree of a Boolean function $f$ is the minimum degree of a real polynomial $p$ that represents $f$ in sign: $f(x)\equiv {sgn}~ p(x)$. Introduced in the seminal work of Minsky and Papert [Perceptrons: An Introduction to Computational Geometry, ...

The threshold degree of a Boolean function $f$ is the minimum degree of a real polynomial $p$ that represents $f$ in sign: $f(x)\equiv {sgn}\ p(x)$. In a seminal 1969 monograph, Minsky and Papert constructed a polynomial-size constant-depth $\{\wedge,\vee\}$-...

A polynomial threshold function (PTF) of degree d is a boolean function of the form f=sgn(p), where p is a degree-d polynomial, and sgn is the sign function. The main result of the paper is an almost optimal bound on the probability that a random ...

The threshold degree of a Boolean function f is the minimum degree of a real polynomial p that represents f in sign: f(x) ≡ sgn p(x). In a seminal 1969 monograph, Minsky and Papert constructed a polynomial-size constant-depth {∧, ∨)-circuit in n ...

For an $n$-variate degree–$2$ real polynomial $p$, we prove that $\E_{x\sim \mathcal{D}}[\sgn(p(x))]$ is determined up to an additive $\eps$ as long as $\mathcal{D}$ is a $k$-wise independent distribution over $\bits^n$ for $k = \poly(1/\eps)$. This ...

In 2002 Jackson et al. [JKS02] asked whether AC⁰ circuits augmented with a threshold gate at the output can be efficiently learned from uniform random examples. We answer this question affirmatively by showing that such circuits have fairly strong ...

A real polynomial P ( X ₁ , ... , X _n ) sign represents f : A ⁿ {0, 1} if for every ( a ₁ , ... , a _n ) A ⁿ , the sign of P ( a ₁ , ... , a _n ) equals $$(-1)^{f(a_{1}, \ldots ,a_{n})}$$ . Such sign representations are well-studied in computer ...

We give the first polynomial time algorithm to learn any function of a constant number of halfspaces under the uniform distribution on the Boolean hypercube to within any constant error parameter. We also give the first quasipolynomial time algorithm for ...

We give new upper and lower bounds on the degree of real multivariate polynomials which sign-represent Boolean functions. Our upper bounds for Boolean formulas yield the first known subexponential time learning algorithms for formulas of superconstant ...