In this paper we prove results regarding booleanfunctions with small spectral norm (the spectral norm of f is parallel to(f) over cap parallel to(1) = Sigma(alpha)vertical barvertical bar) Specifically, we prove the ...
详细信息
In this paper we prove results regarding booleanfunctions with small spectral norm (the spectral norm of f is parallel to(f) over cap parallel to(1) = Sigma(alpha)vertical bar<(f(alpha))over cap>vertical bar) Specifically, we prove the following results for functions f : {0, 1}(n) -> {0, 1} with parallel to(f) over cap parallel to(1)= A. 1. There is an affine subspace V of co-dimension at most A(2) such that f vertical bar(V) is constant. 2. f can be computed by a parity decision tree of size at most 2(A2) n(2A). (A parity decision tree is a decision tree whose nodes are labeled with arbitrary linear functions.) 3. f can be computed by a De Morgan formula of size O(2(A2) n(2A+ 2)) and by a De Morgan formula of depth O(A(2) + log(n) center dot A). 4. If in addition f has at most s nonzero Fourier coefficients, then f can be computed by a parity decision tree of depth at most A(2) log s. 5. For every is an element of > 0 there is a parity decision tree of depth O(A(2) + log(1/is an element of)) and size 2(O(A2)) center dot min{1/is an element of(2), log(1/is an element of)(2A)} that is an element of-approximates f. Furthermore, this tree can be learned ( in the uniform distribution model), with probability 1 - delta, using poly(n, exp(A(2)), 1/is an element of, log(1/delta)) membership queries. All the results above (except 3) also hold (with a slight change in parameters) for functions f : Z(p)(n) -> {0, 1}.
The Sensitivity Conjecture and the Log-rank Conjecture are among the most important and challenging problems in concrete complexity. Incidentally, the Sensitivity Conjecture is known to hold for monotone functions, an...
详细信息
The non-linear invariance principle of Mossel, O'Donnell and Oleszkiewicz establishes that if f (xi,, xn) is a multilinear low-degree polynomial with low influences then the distribution of f (B),, Bn) is close (i...
详细信息
ISBN:
(纸本)9783959770088
The non-linear invariance principle of Mossel, O'Donnell and Oleszkiewicz establishes that if f (xi,, xn) is a multilinear low-degree polynomial with low influences then the distribution of f (B),, Bn) is close (in various senses) to the distribution of f (G1,...,G(n)), where B-i is an element of(R) {-1, 1} are independent Bernoulli random variables and g(i) similar to(0, 1) are independent standard Gaussians. The invariance principle has seen many application in theoretical computer science, including the Majority is Stablest conjecture, which shows that the Goemans Williamson algorithm for MAXCUT is optimal under the Unique Games Conjecture. More generally, MOO's invariance principle works for any two vectors of hypercontractive random variables (X-1,..., X-n), (y(1),..., y(n)) such that (i) Matching moments: X-i and Y-i have matching first and second moments, (ii) Independence: the variables X1,, Xn are independent, as are, Y-1,..., y(n). The independence condition is crucial to the proof of the theorem, yet in some cases we would like to use distributions (X),., Xn) in which the individual coordinates are not independent. A common example is the uniform distribution on the slice (nk1) which consists of all vectors (x1,, xn) E {0, 1}n with Hamming weight k. The slice shows up in theoretical computer science (hardness amplification, direct sum testing), extremal combinatorics (ErdOs Ko Rado theorems) and coding theory (in the guise of the Johnson association scheme). Our main result is an invariance principle in which (X),., Xn) is the uniform distribution on a slice (pnn1) and (y,,, Yn) consists either of n independent Ber(p) random variables, or of n independent N(p, p(1 p)) random variables. As applications, we prove a version of Majority is Stablest for functions on the slice, a version of Bourgain's tail theorem, a version of the Kindler Safra structural theorem, and a stability version of the t-intersecting ErdOs Ko Rado theorem, combining techniques of Wils
In a recent work with Kindler and Wimmer we proved an invariance principle for the slice for low-influence, low-degree functions. Here we provide an alternative proof for general lowdegree functions, with no constrain...
详细信息
ISBN:
(纸本)9783959770088
In a recent work with Kindler and Wimmer we proved an invariance principle for the slice for low-influence, low-degree functions. Here we provide an alternative proof for general lowdegree functions, with no constraints on the influences. We show that any real-valued function on the slice, whose degree when written as a harmonic multi-linear polynomial is o(root n), has approximately the same distribution under the slice and cube measure. Our proof is based on a novel decomposition of random increasing paths in the cube in terms of martingales and reverse martingales. While such decompositions have been used in the past for stationary reversible Markov chains, ours decomposition is applied in a non-reversible nonstationary setup. We also provide simple proofs for some known and some new properties of harmonic functions which are crucial for the proof. Finally, we provide independent simple proofs for the known facts that 1) one cannot distinguish between the slice and the cube based on functions of o(n) coordinates and 2) boolean symmetric functions on the cube cannot be approximated under the uniform measure by functions whose sum of influences is o(root n).
We describe a web of connections between the following topics: the mathematical theory of voting and social choice;the computational complexity of the Maximum Cut problem;the Gaussian Isoperimetric Inequality and Bore...
详细信息
ISBN:
(纸本)9788961058070
We describe a web of connections between the following topics: the mathematical theory of voting and social choice;the computational complexity of the Maximum Cut problem;the Gaussian Isoperimetric Inequality and Borell's generalization thereof;the Hypercontractive Inequality of Bonami;and, the analysis of boolean functions. A major theme is the technique of reducing inequalities about Gaussian functions to inequalities about booleanfunctions f : {-1, 1}(n) -> {-1,1}, and then using induction on n to further reduce to inequalities about functions f : {-1, 1} -> {-1,1}. We especially highlight De, Mossel, and Neeman's recent use of this technique to prove the Majority Is Stablest Theorem and Borell's Isoperimetric Inequality simultaneously.
Given ƒ : {--1, 1}n → {-- 1, 1}, define the spectral distribution of ƒ to be the distribution on subsets of [n] in which the set S is sampled with probability ƒ(S)2. Then the Fourier Entropy-Influence (FEI) conjectur...
详细信息
ISBN:
(纸本)9781450326988
Given ƒ : {--1, 1}n → {-- 1, 1}, define the spectral distribution of ƒ to be the distribution on subsets of [n] in which the set S is sampled with probability ƒ(S)2. Then the Fourier Entropy-Influence (FEI) conjecture of Friedgut and Kalai [2] states that there is some absolute constant C such that H[ƒ2] ≤ C ⋅ Inf[ƒ]. Here, H[ƒ2] denotes the Shannon entropy of ƒ's spectral distribution, and Inf[ƒ] is the total influence of ƒ. This conjecture is one of the major open problems in the analysis of boolean functions, and settling it would have several interesting *** results on the FEI conjecture have been largely through direct calculation. In this paper we study a natural interpretation of the conjecture, which states that there exists a communication protocol which, given subset S of [n] distributed as ƒ2, can communicate the value of S using at most C⋅Inf[ƒ] bits in expectation. Using this interpretation, we are able show the following results: First, if ƒ is computable by a read-k decision tree, then H[ƒ2] ≤ 9k ⋅ Inf[ƒ].Next, if ƒ has Inf[ƒ] ≥ 1 and is computable by a decision tree with expected depth d, then H[[ƒ2] ≤ 12d⋅ Inf[ƒ].Finally, we give a new proof of the main theorem of O'Donnell and Tan [8], i.e. that their FEI+ conjecture *** addition, we show that natural improvements to our decision tree results would be sufficient to prove the FEI conjecture in its entirety. We believe that our methods give more illuminating proofs than previous results about the FEI conjecture.
It has long been known that any boolean function that depends on n input variables has both degree and exact quantum query complexity of Omega(log n), and that this bound is achieved for some functions. In this paper ...
详细信息
ISBN:
(纸本)9780769549972
It has long been known that any boolean function that depends on n input variables has both degree and exact quantum query complexity of Omega(log n), and that this bound is achieved for some functions. In this paper we study the case of approximate degree and bounded-error quantum query complexity. We show that for these measures the correct lower bound is Omega(log n/log log n), and we exhibit quantum algorithms for two functions where this bound is achieved.
暂无评论