Name
Abstract | ||
|---|---|---|
The Fourier-Entropy Influence (FEI) Conjecture states that for any Boolean function f : {+1, -1}(n). {+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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/978-3-319-77404-6_21 | Lecture Notes in Computer Science |
Field | DocType | Volume |
Boolean function,Discrete mathematics,Combinatorics,Normal distribution,Computer science,Uniform distribution (continuous),Fourier transform,Physical constant,Conjecture,Threshold function | Conference | 10807 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
10 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sourav Chakraborty | 1 | 381 | 49.27 |
| Sushrut Karmalkar | 2 | 1 | 1.36 |
| Srijita Kundu | 3 | 0 | 0.34 |
| Satyanarayana V. Lokam | 4 | 274 | 22.36 |
| Nitin Saurabh | 5 | 5 | 3.81 |