اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدPeeling Algorithm on Random Hypergraphs with Superlinear Number of Hyperedges
86
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
When we try to solve a system of linear equations, we can consider a simple iterative algorithm in which an equation including only one variable is chosen at each step, and the variable is fixed to the value satisfying the equation. The dynamics of this algorithm is captured by the peeling algorithm. Analyses of the peeling algorithm on random hypergraphs are required for many problems, e.g., the decoding threshold of low-density parity check codes, the inverting threshold of Goldreichs pseudorandom generator, the load threshold of cuckoo hashing, etc. In this work, we deal with random hypergraphs including superlinear number of hyperedges, and derive the tight threshold for the succeeding of the peeling algorithm. For the analysis, Wormalds method of differential equations, which is commonly used for analyses of the peeling algorithm on random hypergraph with linear number of hyperedges, cannot be used due to the superlinear number of hyperedges. A new method called the evolution of the moment generating function is proposed in this work.
قيم البحث
اقرأ أيضاً
In this work we present a simple and efficient algorithm which, with high probability, provides an almost uniform sample from the set of proper k-colourings on an instance of a sparse random graph G(n,d/n), where k=k(d) is a sufficiently large consta
nt. Our algorithm is not based on the Markov Chain Monte Carlo method (M.C.M.C.). Instead, we provide a novel proof of correctness of our Algorithm that is based on interesting spatial mixing properties of colourings of G(n,d/n). Our result improves upon previous results (based on M.C.M.C.) that required a number of colours growing unboundedly with n.
This paper has been withdrawn by the author(s),
Given an undirected graph, each of the two end-vertices of an edge can own the edge. Call a vertex poor, if it owns at most one edge. We give a polynomial time algorithm for the problem of finding an assignment of owners to the edges which minimizes
the number of poor vertices. In the terminology of graph orientation, this means finding an orientation for the edges of a graph minimizing the number of edges with out-degree at most 1, and answers a question of Asahiro Jansson, Miyano, Ono (2014).
In this paper, we present a distributed algorithm to compute various parameters of a tree such as the process number, the edge search number or the node search number and so the pathwidth. This algorithm requires n steps, an overall computation time
of O(n log(n)), and n messages of size log_3(n)+3. We then propose a distributed algorithm to update the process number (or the node search number, or the edge search number) of each component of a forest after adding or deleting an edge. This second algorithm requires O(D) steps, an overall computation time of O(D log(n)), and O(D) messages of size log_3(n)+3, where D is the diameter of the modified connected component. Finally, we show how to extend our algorithms to trees and forests of unknown size using messages of less than 2a+4+e bits, where a is the parameter to be determined and e=1 for updates algorithms.
A 2-coloring of a hypergraph is a mapping from its vertices to a set of two colors such that no edge is monochromatic. Let $H_k(n,m)$ be a random $k$-uniform hypergraph on $n$ vertices formed by picking $m$ edges uniformly, independently and with rep
lacement. It is easy to show that if $r geq r_c = 2^{k-1} ln 2 - (ln 2) /2$, then with high probability $H_k(n,m=rn)$ is not 2-colorable. We complement this observation by proving that if $r leq r_c - 1$ then with high probability $H_k(n,m=rn)$ is 2-colorable.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
