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 t
his 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.
Goldreich suggested candidates of one-way functions and pseudorandom generators included in $mathsf{NC}^0$. It is known that randomly generated Goldreichs generator using $(r-1)$-wise independent predicates with $n$ input variables and $m=C n^{r/2}$
output variables is not pseudorandom generator with high probability for sufficiently large constant $C$. Most of the previous works assume that the alphabet is binary and use techniques available only for the binary alphabet. In this paper, we deal with non-binary generalization of Goldreichs generator and derives the tight threshold for linear programming relaxation attack using local marginal polytope for randomly generated Goldreichs generators. We assume that $u(n)in omega(1)cap o(n)$ input variables are known. In that case, we show that when $rge 3$, there is an exact threshold $mu_mathrm{c}(k,r):=binom{k}{r}^{-1}frac{(r-2)^{r-2}}{r(r-1)^{r-1}}$ such that for $m=mufrac{n^{r-1}}{u(n)^{r-2}}$, the LP relaxation can determine linearly many input variables of Goldreichs generator if $mu>mu_mathrm{c}(k,r)$, and that the LP relaxation cannot determine $frac1{r-2} u(n)$ input variables of Goldreichs generator if $mu<mu_mathrm{c}(k,r)$. This paper uses characterization of LP solutions by combinatorial structures called stopping sets on a bipartite graph, which is related to a simple algorithm called peeling algorithm.
