Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFourier Entropy-Influence Conjecture for Random Linear Threshold Functions
72
0
0.0
(
0
)
Added by
Nitin Saurabh
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The Fourier-Entropy Influence (FEI) Conjecture states that for any Boolean function $f:{+1,-1}^n to {+1,-1}$, the Fourier entropy of $f$ is at most its influence up to a universal constant factor. While the FEI conjecture has been proved for many classes of Boolean functions, it is still not known whether it holds for the class of Linear Threshold Functions. A natural question is: Does the FEI conjecture hold for a `random linear threshold function? In this paper, we answer this question in the affirmative. We consider two natural distributions on the weights defining a linear threshold function, namely uniform distribution on $[-1,1]$ and Normal distribution.
rate research
Read More
Given a Boolean function $f:{-1,1}^nto {-1,1}$, the Fourier distribution assigns probability $widehat{f}(S)^2$ to $Ssubseteq [n]$. The Fourier Entropy-Influence (FEI) conjecture of Friedgut and Kalai asks if there exist a universal constant C>0 such that $H(hat{f}^2)leq C Inf(f)$, where $H(hat{f}^2)$ is the Shannon entropy of the Fourier distribution of $f$ and $Inf(f)$ is the total influence of $f$. 1) We consider the weaker Fourier Min-entropy-Influence (FMEI) conjecture. This asks if $H_{infty}(hat{f}^2)leq C Inf(f)$, where $H_{infty}(hat{f}^2)$ is the min-entropy of the Fourier distribution. We show $H_{infty}(hat{f}^2)leq 2C_{min}^oplus(f)$, where $C_{min}^oplus(f)$ is the minimum parity certificate complexity of $f$. We also show that for every $epsilongeq 0$, we have $H_{infty}(hat{f}^2)leq 2log (|hat{f}|_{1,epsilon}/(1-epsilon))$, where $|hat{f}|_{1,epsilon}$ is the approximate spectral norm of $f$. As a corollary, we verify the FMEI conjecture for the class of read-$k$ $DNF$s (for constant $k$). 2) We show that $H(hat{f}^2)leq 2 aUC^oplus(f)$, where $aUC^oplus(f)$ is the average unambiguous parity certificate complexity of $f$. This improves upon Chakraborty et al. An important consequence of the FEI conjecture is the long-standing Mansours conjecture. We show that a weaker version of FEI already implies Mansours conjecture: is $H(hat{f}^2)leq C min{C^0(f),C^1(f)}$?, where $C^0(f), C^1(f)$ are the 0- and 1-certificate complexities of $f$, respectively. 3) We study what FEI implies about the structure of polynomials that 1/3-approximate a Boolean function. We pose a conjecture (which is implied by FEI): no flat degree-$d$ polynomial of sparsity $2^{omega(d)}$ can 1/3-approximate a Boolean function. We prove this conjecture unconditionally for a particular class of polynomials.
We study parity decision trees for Boolean functions. The motivation of our study is the log-rank conjecture for XOR functions and its connection to Fourier analysis and parity decision tree complexity. Let f be a Boolean function with Fourier support S and Fourier sparsity k. 1) We prove via the probabilistic method that there exists a parity decision tree of depth O(sqrt k) that computes f. This matches the best known upper bound on the parity decision tree complexity of Boolean functions (Tsang, Wong, Xie, and Zhang, FOCS 2013). Moreover, while previous constructions (Tsang et al., FOCS 2013, Shpilka, Tal, and Volk, Comput. Complex. 2017) build the trees by carefully choosing the parities to be queried in each step, our proof shows that a naive sampling of the parities suffices. 2) We generalize the above result by showing that if the Fourier spectra of Boolean functions satisfy a natural folding property, then the above proof can be adapted to establish existence of a tree of complexity polynomially smaller than O(sqrt k). We make a conjecture in this regard which, if true, implies that the communication complexity of an XOR function is bounded above by the fourth root of the rank of its communication matrix, improving upon the previously known upper bound of square root of rank (Tsang et al., FOCS 2013, Lovett, J. ACM. 2016). 3) It can be shown by elementary techniques that for any Boolean function f and all pairs (alpha, beta) of parities in S, there exists another pair (gamma, delta) of parities in S such that alpha + beta = gamma + delta. We show, among other results, that there must exist several gamma in F_2^n such that there are at least three pairs (alpha_1, alpha_2) of parities in S with alpha_1 + alpha_2 = gamma.
The problem of distinguishing between a random function and a random permutation on a domain of size $N$ is important in theoretical cryptography, where the security of many primitives depend on the problems hardness. We study the quantum query complexity of this problem, and show that any quantum algorithm that solves this problem with bounded error must make $Omega(N^{1/5}/log N)$ queries to the input function. Our lower bound proof uses a combination of the Collision Problem lower bound and Ambainiss adversary theorem.
The total influence of a function is a central notion in analysis of Boolean functions, and characterizing functions that have small total influence is one of the most fundamental questions associated with it. The KKL theorem and the Friedgut junta theorem give a strong characterization of such functions whenever the bound on the total influence is $o(log n)$. However, both results become useless when the total influence of the function is $omega(log n)$. The only case in which this logarithmic barrier has been broken for an interesting class of functions was proved by Bourgain and Kalai, who focused on functions that are symmetric under large enough subgroups of $S_n$. In this paper, we build and improve on the techniques of the Bourgain-Kalai paper and establish new concentration results on the Fourier spectrum of Boolean functions with small total influence. Our results include: 1. A quantitative improvement of the Bourgain--Kalai result regarding the total influence of functions that are transitively symmetric. 2. A slightly weaker version of the Fourier--Entropy Conjecture of Friedgut and Kalai. This weaker version implies in particular that the Fourier spectrum of a constant variance, Boolean function $f$ is concentrated on $2^{O(I[f]log I[f])}$ characters, improving an earlier result of Friedgut. Removing the $log I[f]$ factor would essentially resolve the Fourier--Entropy Conjecture, as well as settle a conjecture of Mansour regarding the Fourier spectrum of polynomial size DNF formulas. Our concentration result has new implications in learning theory: it implies that the class of functions whose total influence is at most $K$ is agnostically learnable in time $2^{O(Klog K)}$, using membership queries.
Random $s$-intersection graphs have recently received considerable attention in a wide range of application areas. In such a graph, each vertex is equipped with a set of items in some random manner, and any two vertices establish an undirected edge in between if and only if they have at least $s$ common items. In particular, in a uniform random $s$-intersection graph, each vertex independently selects a fixed number of items uniformly at random from a common item pool, while in a binomial random $s$-intersection graph, each item in some item pool is independently attached to each vertex with the same probability. For binomial/uniform random $s$-intersection graphs, we establish threshold functions for perfect matching containment, Hamilton cycle containment, and $k$-robustness, where $k$-robustness is in the sense of Zhang and Sundaram [IEEE Conf. on Decision & Control 12]. We show that these threshold functions resemble those of classical ErdH{o}s-R{e}nyi graphs, where each pair of vertices has an undirected edge independently with the same probability.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
