اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدAMS Without 4-Wise Independence on Product Domains
38
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In their seminal work, Alon, Matias, and Szegedy introduced several sketching techniques, including showing that 4-wise independence is sufficient to obtain good approximations of the second frequency moment. In this work, we show that their sketching technique can be extended to product domains $[n]^k$ by using the product of 4-wise independent functions on $[n]$. Our work extends that of Indyk and McGregor, who showed the result for $k = 2$. Their primary motivation was the problem of identifying correlations in data streams. In their model, a stream of pairs $(i,j) in [n]^2$ arrive, giving a joint distribution $(X,Y)$, and they find approximation algorithms for how close the joint distribution is to the product of the marginal distributions under various metrics, which naturally corresponds to how close $X$ and $Y$ are to being independent. By using our technique, we obtain a new result for the problem of approximating the $ell_2$ distance between the joint distribution and the product of the marginal distributions for $k$-ary vectors, instead of just pairs, in a single pass. Our analysis gives a randomized algorithm that is a $(1 pm epsilon)$ approximation (with probability $1-delta$) that requires space logarithmic in $n$ and $m$ and proportional to $3^k$.
قيم البحث
اقرأ أيضاً
Bells theorem is often said to imply that quantum mechanics violates local causality, and that local causality cannot be restored with a hidden-variables theory. This however is only correct if the hidden-variables theory fulfils an assumption called
Statistical Independence. Violations of Statistical Independence are commonly interpreted as correlations between the measurement settings and the hidden variables (which determine the measurement outcomes). Such correlations have been discarded as finetuning or a conspiracy. We here point out that the common interpretation is at best physically ambiguous and at worst incorrect. The problem with the common interpretation is that Statistical Independence might be violated because of a non-trivial measure in state space, a possibility we propose to call supermeasured. We use Invariant Set Theory as an example of a supermeasured theory that violates the Statistical Independence assumption in Bells theorem without requiring correlations between hidden variables and measurement settings.
In this note, we prove a tight lower bound on the joint entropy of $n$ unbiased Bernoulli random variables which are $n/2$-wise independent. For general $k$-wise independence, we give new lower bounds by adapting Navon and Samorodnitskys Fourier proo
f of the `LP bound on error correcting codes. This counts as partial progress on a problem asked by Gavinsky and Pudlak.
We give a deterministic, nearly logarithmic-space algorithm for mild spectral sparsification of undirected graphs. Given a weighted, undirected graph $G$ on $n$ vertices described by a binary string of length $N$, an integer $kleq log n$, and an erro
r parameter $epsilon > 0$, our algorithm runs in space $tilde{O}(klog (Ncdot w_{mathrm{max}}/w_{mathrm{min}}))$ where $w_{mathrm{max}}$ and $w_{mathrm{min}}$ are the maximum and minimum edge weights in $G$, and produces a weighted graph $H$ with $tilde{O}(n^{1+2/k}/epsilon^2)$ edges that spectrally approximates $G$, in the sense of Spielmen and Teng [ST04], up to an error of $epsilon$. Our algorithm is based on a new bounded-independence analysis of Spielman and Srivastavas effective resistance based edge sampling algorithm [SS08] and uses results from recent work on space-bounded Laplacian solvers [MRSV17]. In particular, we demonstrate an inherent tradeoff (via upper and lower bounds) between the amount of (bounded) independence used in the edge sampling algorithm, denoted by $k$ above, and the resulting sparsity that can be achieved.
We extend the notion of spectral independence (introduced by Anari, Liu, and Oveis Gharan [ALO20]) from the Boolean domain to general discrete domains. This property characterises distributions with limited correlations, and implies that the correspo
nding Glauber dynamics is rapidly mixing. As a concrete application, we show that Glauber dynamics for sampling proper $q$-colourings mixes in polynomial-time for the family of triangle-free graphs with maximum degree $Delta$ provided $qge (alpha^*+delta)Delta$ where $alpha^*approx 1.763$ is the unique solution to $alpha^*=exp(1/alpha^*)$ and $delta>0$ is any constant. This is the first efficient algorithm for sampling proper $q$-colourings in this regime with possibly unbounded $Delta$. Our main tool of establishing spectral independence is the recursive coupling by Goldberg, Martin, and Paterson [GMP05].
This paper formalizes connections between stability of polynomials and convergence rates of Markov Chain Monte Carlo (MCMC) algorithms. We prove that if a (multivariate) partition function is nonzero in a region around a real point $lambda$ then spec
tral independence holds at $lambda$. As a consequence, for Holant-type problems (e.g., spin systems) on bounded-degree graphs, we obtain optimal $O(nlog n)$ mixing time bounds for the single-site update Markov chain known as the Glauber dynamics. Our result significantly improves the running time guarantees obtained via the polynomial interpolation method of Barvinok (2017), refined by Patel and Regts (2017). There are a variety of applications of our results. In this paper, we focus on Holant-type (i.e., edge-coloring) problems, including weighted edge covers and weighted even subgraphs. For the weighted edge cover problem (and several natural generalizations) we obtain an $O(nlog{n})$ sampling algorithm on bounded-degree graphs. The even subgraphs problem corresponds to the high-temperature expansion of the ferromagnetic Ising model. We obtain an $O(nlog{n})$ sampling algorithm for the ferromagnetic Ising model with a nonzero external field on bounded-degree graphs, which improves upon the classical result of Jerrum and Sinclair (1993) for this class of graphs. We obtain further applications to antiferromagnetic two-spin models on line graphs, weighted graph homomorphisms, tensor networks, and more.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
