Given a subset K of the unit Euclidean sphere, we estimate the minimal number m = m(K) of hyperplanes that generate a uniform tessellation of K, in the sense that the fraction of the hyperplanes separating any pair x, y in K is nearly proportional to the Euclidean distance between x and y. Random hyperplanes prove to be almost ideal for this problem; they achieve the almost optimal bound m = O(w(K)^2) where w(K) is the Gaussian mean width of K. Using the map that sends x in K to the sign vector with respect to the hyperplanes, we conclude that every bounded subset K of R^n embeds into the Hamming cube -1, 1 ^m with a small distortion in the Gromov-Haussdorf metric. Since for many sets K one has m = m(K) << n, this yields a new discrete mechanism of dimension reduction for sets in Euclidean spaces.
The problem of one-bit compressed sensing was introduced by Boufounos and Baraniuk @cite_6 . Jacques, Laska, Boufounos and Baraniuk @cite_12 realized a connection of this problem to uniform tessellations of the set of sparse signals @math , and to almost isometric embedding of @math into the Hamming cube @math . For this set @math , they proved Corollary with @math and a version of Theorem for @math . The authors of the present paper analyzed in @cite_18 a bigger set of compressible'' signals @math and proved for @math a version of Corollary with @math . Since the mean widths of both sets @math and @math are of the order @math , Theorem holds for these sets with @math . In other words, apart from the dependence of @math (which is an interesting problem), the prior results follow as partial cases from Theorem .
@cite_18 @cite_12 @cite_6
2145218531 2949903712
The full' edge isoperimetric inequality for the discrete cube (due to Harper, Bernstein, Lindsay and Hart) specifies the minimum size of the edge boundary @math of a set @math , as a function of @math . A weaker (but more widely-used) lower bound is @math , where equality holds iff @math is a subcube. In 2011, the first author obtained a sharp stability' version of the latter result, proving that if @math , then there exists a subcube @math such that @math . The weak' version of the edge isoperimetric inequality has the following well-known generalization for the @math -biased' measure @math on the discrete cube: if @math , or if @math and @math is monotone increasing, then @math . In this paper, we prove a sharp stability version of the latter result, which generalizes the aforementioned result of the first author. Namely, we prove that if @math , then there exists a subcube @math such that @math , where @math . This result is a central component in recent work of the authors proving sharp stability versions of a number of Erd o s-Ko-Rado type theorems in extremal combinatorics, including the seminal complete intersection theorem' of Ahlswede and Khachatrian. In addition, we prove a biased-measure analogue of the full' edge isoperimetric inequality, for monotone increasing sets, and we observe that such an analogue does not hold for arbitrary sets, hence answering a question of Kalai. We use this result to give a new proof of the full' edge isoperimetric inequality, one relying on the Kruskal-Katona theorem. The @math -fold direct sum encoding of a string @math is a function @math that takes as input sets @math of size @math and outputs @math . In this paper we prove a direct sum testing theorem. We describe a three query test that accepts with probability one any function of the form @math for some @math and rejects with probability @math functions @math that are @math -far from being a direct sum encoding, where the constant behind the @math notation is independent of @math . This theorem has a couple of additional guises: Linearity testing: By identifying the subsets of @math with vectors in @math in the natural way, our result can be thought of as a linearity testing theorem for functions whose domain is restricted to the @math th layer of the hypercube (i.e., the set of @math -bit strings with Hamming weight @math ). Tensor power testing: By moving to @math notation, the direct sum encoding is equivalent (up to a difference thatis negligi... The seminal complete intersection theorem of Ahlswede and Khachatrian gives the maximum cardinality of a @math -uniform @math -intersecting family on @math points, and describes all optimal families. We extend this theorem to several other settings: the weighted case, the case of infinitely many points, and the Hamming scheme. The weighted Ahlswede-Khachatrian theorem gives the maximal @math measure of a @math -intersecting family on @math points, where @math . As has been observed by Ahlswede and Khachatrian and by Dinur and Safra, this theorem can be derived from the classical one by a simple reduction. However, this reduction fails to identify the optimal families, and only works for @math , using a different technique of Ahlswede and Khachatrian (the case @math is Katona's intersection theorem). We then extend the weighted Ahlswede-Khachatrian theorem to the case of infinitely many points. The Ahlswede-Khachatrian theorem on the Hamming scheme gives the maximum cardinality of a subset of @math in which any two elements @math have @math positions @math such that @math . We show that this case corresponds to @math with @math , extending work of Ahlswede and Khachatrian, who considered the case @math . We also determine the maximum cardinality families. We obtain similar results for subsets of @math , though in this case we are not able to identify all maximum cardinality families. We study arithmetic proof systems @math and @math operating with arithmetic circuits and arithmetic formulas, respectively, and that prove polynomial identities over a field @math . We establish a series of structural theorems about these proof systems, the main one stating that @math proofs can be balanced: if a polynomial identity of syntactic degree @math and depth @math has a @math proof of size @math , then it also has a @math proof of size @math in which every circuit has depth @math . As a corollary, we obtain a quasi-polynomial simulation of @math by @math . Using these results we obtain the following: consider the identities @math where @math , and @math are @math square matrices and @math is a triangular matrix with $z_...