Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAlmost linear Boolean functions on $S_n$ are almost unions of cosets
182
0
0.0
(
0
)
Added by
Yuval Filmus
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Authors
Yuval Filmus
Ask ChatGPT about the research
No Arabic abstract
We show that if $fcolon S_n to {0,1}$ is $epsilon$-close to linear in $L_2$ and $mathbb{E}[f] leq 1/2$ then $f$ is $O(epsilon)$-close to a union of mostly disjoint cosets, and moreover this is sharp: any such union is close to linear. This constitutes a sharp Friedgut-Kalai-Naor theorem for the symmetric group. Using similar techniques, we show that if $fcolon S_n to mathbb{R}$ is linear, $Pr[f otin {0,1}] leq epsilon$, and $Pr[f = 1] leq 1/2$, then $f$ is $O(epsilon)$-close to a union of mostly disjoint cosets, and this is also sharp; and that if $fcolon S_n to mathbb{R}$ is linear and $epsilon$-close to ${0,1}$ in $L_infty$ then $f$ is $O(epsilon)$-close in $L_infty$ to a union of disjoint cosets.
rate research
Read More
We show that a Boolean degree $d$ function on the slice $binom{[n]}{k} = { (x_1,ldots,x_n) in {0,1} : sum_{i=1}^n x_i = k }$ is a junta, assuming that $k,n-k$ are large enough. This generalizes a classical result of Nisan and Szegedy on the hypercube. Moreover, we show that the maximum number of coordinates that a Boolean degree $d$ function can depend on is the same on the slice and the hypercube.
Let $mathcal{F}$ and $mathcal{G}$ be two $t$-uniform families of subsets over $[k] = {1,2,...,k}$, where $|mathcal{F}| = |mathcal{G}|$, and let $C$ be the adjacency matrix of the bipartite graph whose vertices are the subsets in $mathcal{F}$ and $mathcal{G}$, and there is an edge between $Ain mathcal{F}$ and $B in mathcal{G}$ if and only if $A cap B eq emptyset$. The pair $(mathcal{F},mathcal{G})$ is $q$-almost cross intersecting if every row and column of $C$ has exactly $q$ zeros. We consider $q$-almost cross intersecting pairs that have a circulant intersection matrix $C_{p,q}$, determined by a column vector with $p > 0$ ones followed by $q > 0$ zeros. This family of matrices includes the identity matrix in one extreme, and the adjacency matrix of the bipartite crown graph in the other extreme. We give constructions of pairs $(mathcal{F},mathcal{G})$ whose intersection matrix is $C_{p,q}$, for a wide range of values of the parameters $p$ and $q$, and in some cases also prove matching upper bounds. Specifically, we prove results for the following values of the parameters: (1) $1 leq p leq 2t-1$ and $1 leq q leq k-2t+1$. (2) $2t leq p leq t^2$ and any $q> 0$, where $k geq p+q$. (3) $p$ that is exponential in $t$, for large enough $k$. Using the first result we show that if $k geq 4t-3$ then $C_{2t-1,k-2t+1}$ is a maximal isolation submatrix of size $ktimes k$ in the $0,1$-matrix $A_{k,t}$, whose rows and columns are labeled by all subsets of size $t$ of $[k]$, and there is a one in the entry on row $x$ and column $y$ if and only if subsets $x,y$ intersect.
We study regular graphs in which the random walks starting from a positive fraction of vertices have small mixing time. We prove that any such graph is virtually an expander and has no small separator. This answers a question of Pak [SODA, 2002]. As a corollary, it shows that sparse (constant degree) regular graphs with many well-mixing vertices have a long cycle, improving a result of Pak. Furthermore, such cycle can be found in polynomial time. Secondly, we show that if the random walks from a positive fraction of vertices are well-mixing, then the random walks from almost all vertices are well-mixing (with a slightly worse mixing time).
We show that almost all n-bit Boolean functions have bounded-error quantum query complexity at least n/2, up to lower-order terms. This improves over an earlier n/4 lower bound of Ambainis, and shows that van Dams oracle interrogation is essentially optimal for almost all functions. Our proof uses the fact that the acceptance probability of a T-query algorithm can be written as the sum of squares of degree-T polynomials.
An almost self-centered graph is a connected graph of order $n$ with exactly $n-2$ central vertices, and an almost peripheral graph is a connected graph of order $n$ with exactly $n-1$ peripheral vertices. We determine (1) the maximum girth of an almost self-centered graph of order $n;$ (2) the maximum independence number of an almost self-centered graph of order $n$ and radius $r;$ (3) the minimum order of a $k$-regular almost self-centered graph and (4) the maximum size of an almost peripheral graph of order $n;$ (5) which numbers are possible for the maximum degree of an almost peripheral graph of order $n;$ (6) the maximum number of vertices of maximum degree in an almost peripheral graph of order $n$ whose maximum degree is the second largest possible. Whenever the extremal graphs have a neat form, we also describe them.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
