Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPartially observed Boolean sequences and noise sensitivity
142
0
0.0
(
0
)
Authors
Daniel Ahlberg
Ask ChatGPT about the research
No Arabic abstract
Let $mathcal{H}$ denote a collection of subsets of ${1,2,ldots,n}$, and assign independent random variables uniformly distributed over $[0,1]$ to the $n$ elements. Declare an element $p$-present if its corresponding value is at most $p$. In this paper, we quantify how much the observation of the $r$-present ($r>p$) set of elements affects the probability that the set of $p$-present elements is contained in $mathcal{H}$. In the context of percolation, we find that this question is closely linked to the near-critical regime. As a consequence, we show that for every $r>1/2$, bond percolation on the subgraph of the square lattice given by the set of $r$-present edges is almost surely noise sensitive at criticality, thus generalizing a result due to Benjamini, Kalai and Schramm.
rate research
Read More
We prove that the Poisson Boolean model, also known as the Gilbert disc model, is noise sensitive at criticality. This is the first such result for a Continuum Percolation model, and the first for which the critical probability p_c e 1/2. Our proof uses a version of the Benjamini-Kalai-Schramm Theorem for biased product measures. A quantitative version of this result was recently proved by Keller and Kindler. We give a simple deduction of the non-quantitative result from the unbiased version. We also develop a quite general method of approximating Continuum Percolation models by discrete models with p_c bounded away from zero; this method is based on an extremal result on non-uniform hypergraphs.
Let $T_{epsilon}$ be the noise operator acting on Boolean functions $f:{0, 1}^nto {0, 1}$, where $epsilonin[0, 1/2]$ is the noise parameter. Given $alpha>1$ and fixed mean $mathbb{E} f$, which Boolean function $f$ has the largest $alpha$-th moment $mathbb{E}(T_epsilon f)^alpha$? This question has close connections with noise stability of Boolean functions, the problem of non-interactive correlation distillation, and Courtade-Kumars conjecture on the most informative Boolean function. In this paper, we characterize maximizers in some extremal settings, such as low noise ($epsilon=epsilon(n)$ is close to 0), high noise ($epsilon=epsilon(n)$ is close to 1/2), as well as when $alpha=alpha(n)$ is large. Analogous results are also established in more general contexts, such as Boolean functions defined on discrete torus $(mathbb{Z}/pmathbb{Z})^n$ and the problem of noise stability in a tree model.
We determine the size of $k$-core in a large class of dense graph sequences. Let $G_n$ be a sequence of undirected, $n$-vertex graphs with edge weights ${a^n_{i,j}}_{i,j in [n]}$ that converges to a kernel $W:[0,1]^2to [0,+infty)$ in the cut metric. Keeping an edge $(i,j)$ of $G_n$ with probability $min { {a^n_{i,j}}/{n},1 }$ independently, we obtain a sequence of random graphs $G_n(frac{1}{n})$. Denote by $C_k(G)$ the size of $k$-core in graph $G$, by $X^W$ the branching process associated with the kernel $W$, by $mathcal{A}$ the property of a branching process that the initial particle has at least $k$ children, each of which has at least $k-1$ children, each of which has at least $k-1$ children, and so on. Using branching process and theory of dense graph limits, under mild assumptions we obtain the size of $k$-core of random graphs $G_n(frac{1}{n})$, begin{align*} C_kleft(G_nleft(frac{1}{n}right)right) =n mathbb{P}_{X^W}left(mathcal{A}right) +o_p(n). end{align*} Our result can also be used to obtain the threshold of appearance of a $k$-core of order $n$. In addition, we obtain a probabilistic result concerning cut-norm and branching process which might be of independent interest.
We consider a controlled second order differential equation which is partially observed with an additional fractional noise. we study the asymptotic (for large observation time) design problem of the input and give an efficient estimator of the unknown signal drift parameter. When the input depends on the unknow parameter, we will try the one-step estimation procedure using the Newton-Raphson method.
We consider Boolean functions f:{-1,1}^n->{-1,1} that are close to a sum of independent functions on mutually exclusive subsets of the variables. We prove that any such function is close to just a single function on a single subset. We also consider Boolean functions f:R^n->{-1,1} that are close, with respect to any product distribution over R^n, to a sum of their variables. We prove that any such function is close to one of the variables. Both our results are independent of the number of variables, but depend on the variance of f. I.e., if f is epsilon*Var(f)-close to a sum of independent functions or random variables, then it is O(epsilon)-close to one of the independent functions or random variables, respectively. We prove that this dependence on Var(f) is tight. Our results are a generalization of the Friedgut-Kalai-Naor Theorem [FKN02], which holds for functions f:{-1,1}^n->{-1,1} that are close to a linear combination of uniformly distributed Boolean variables.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
