Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTowards a Proof of the Fourier--Entropy Conjecture?
150
0
0.0
(
0
)
Added by
Dor Minzer
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
Let $P_{n}$ be a set of $n$ points, including the origin, in the unit square $U = [0,1]^2$. We consider the problem of constructing $n$ axis-parallel and mutually disjoint rectangles inside $U$ such that the bottom-left corner of each rectangle coincides with a point in $P_{n}$ and the total area covered by the rectangles is maximized cite{ibmpuzzle}, cite{Winkler2007}, cite{Winkler2010a}, cite{Winkler2010b}. The longstanding conjecture has been that at least half of $U$ can be covered when such rectangles are properly placed. In this paper, we give an existential proof of the conjecture.
The $S$-adic conjecture claims that there exists a condition $C$ such that a sequence has a sub-linear complexity if and only if it is an $S$-adic sequence satisfying Condition $C$ for some finite set $S$ of morphisms. We present an overview of the factor complexity of $S$-adic sequences and we give some examples that either illustrate some interesting properties or that are counter-examples to what could be believed to be a good Condition $C$.
This is the fifth in a series of articles devoted to showing that a typical covering map of large degree to a fixed, regular graph has its new adjacency eigenvalues within the bound conjectured by Alon for random regular graphs. In this article we use the results of Articles~III and IV in this series to prove that if the base graph is regular, then as the degree, $n$, of the covering map tends to infinity, some new adjacency eigenvalue has absolute value outside the Alon bound with probability bounded by $O(1/n)$. In addition, we give upper and lower bounds on this probability that are tight to within a multiplicative constant times the degree of the covering map. These bounds depend on two positive integers, the emph{algebraic power} (which can also be $+infty$) and the emph{tangle power} of the model of random covering map. We conjecture that the algebraic power of the models we study is always $+infty$, and in Article~VI we prove this when the base graph is regular and emph{Ramanujan}. When the algebraic power of the model is $+infty$, then the results in this article imply stronger results, such as (1) the upper and lower bounds mentioned above are matching to within a multiplicative constant, and (2) with probability smaller than any negative power of the degree, the some new eigenvalue fails to be within the Alon bound only if the covering map contains one of finitely many tangles as a subgraph (and this event has low probability).
This is the first in a series of six articles devoted to showing that a typical covering map of large degree to a fixed, regular graph has its new adjacency eigenvalues within the bound conjectured by Alon for random regular graphs. Many of the techniques we develop hold whether or not the base graph is regular. Our first main theorem in this series of articles is that if the base graph is $d$-regular, then for any $epsilon>0$, as the degree, $n$, of the covering map tends to infinity, some new adjacency eigenvalue of the map is larger in absolute value that $2(d-1)^{1/2}+epsilon$ with probability at most order $1/n$. Our second main theorem is that if, in addition, the base graph is Ramanujan, then this probability is bounded above and below by $1/n$ to the power of a positive integer that we call the {em tangle power} of the model, i.e., of the probability spaces of random covering maps of degree $n$. The tangle power is fairly easy to bound from below, and at times to compute exactly; it measures the probability that certain {em tangles} appear in the random covering graph, where a {em tangle} is a local event that forces the covering graph to have a new eigenvalue strictly larger than $2(d-1)^{1/2}$. Our main theorems are relativizations of Alons conjecture on the second eigenvalue of random regular graphs of large degree. In this first article of the series, we introduce all the terminology needed in this series, motivate this terminology, precisely state all the results in the remaining articles, and make some remarks about their proofs. As such, this article provides an overview of the entire series of articles; furthermore, the rest of the articles in this series may be read independently of one another.
We present a proof of the compositional shuffle conjecture, which generalizes the famous shuffle conjecture for the character of the diagonal coinvariant algebra. We first formulate the combinatorial side of the conjecture in terms of certain operators on a graded vector space $V_*$ whose degree zero part is the ring of symmetric functions $Sym[X]$ over $mathbb{Q}(q,t)$. We then extend these operators to an action of an algebra $tilde{AA}$ acting on this space, and interpret the right generalization of the $ abla$ using an involution of the algebra which is antilinear with respect to the conjugation $(q,t)mapsto (q^{-1},t^{-1})$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
