VHViktor Harangi

Viktor Harangi

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Viktor Harangi has a total of 14 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    The least balanced graphs and trees

    by Péter Csikvári, Viktor Harangi

  • Open Access

    RSB bounds on the maximum cut

    by Viktor Harangi

    In the context of random regular graphs, the size of the maximum cut is probably the second most studied graph parameter after the independence ratio. Zdeborová and Boettcher used the cavity method, a non-rigorous statistical physics technique, to predict one-step replica symmetry breaking (1-RSB) formulas. Coja-Ohglan et al. confirmed these predictions as rigorous upper bounds using the interpolation method. While these upper bounds were not expected to be exact, they may be very close to the true values. In this paper, we establish 2-RSB upper bounds and fine-tune their parameters to beat the aforementioned 1-RSB bounds.

  • Conditional Graph Entropy as an Alternating Minimization Problem

    by Viktor Harangi, Xueyan Niu, Bo Bai

    Conditional graph entropy is known to be the minimal rate for a natural functional compression problem with side information at the receiver. In this paper we show that it can be formulated as an alternating minimization problem, which gives rise to a simple iterative algorithm for numerically computing (conditional) graph entropy. This also leads to a new formula which shows that conditional graph entropy is part of a more general framework: the solution of an optimization problem over a convex corner. In the special case of graph entropy (i.e., unconditioned version) this was known due to Csiszár, Körner, Lovász, Marton, and Simonyi. In that case the role of the convex corner was played by the so-called vertex packing polytope. In the conditional version it is a more intricate convex body but the function to minimize is the same. Furthermore, we describe a dual problem that leads to an optimality check and an error bound for the iterative algorithm.


  • Open Access

    Conditional graph entropy as an alternating minimization problem

    by Viktor Harangi, Xueyan Niu, Bo Bai

    Conditional graph entropy is known to be the minimal rate for a natural functional compression problem with side information at the receiver. In this paper we show that it can be formulated as an alternating minimization problem, which gives rise to a simple iterative algorithm for numerically computing (conditional) graph entropy. This also leads to a new formula which shows that conditional graph entropy is part of a more general framework: the solution of an optimization problem over a convex corner. In the special case of graph entropy (i.e., unconditioned version) this was known due to Csisz\'ar, K\"orner, Lov\'asz, Marton, and Simonyi. In that case the role of the convex corner was played by the so-called vertex packing polytope. In the conditional version it is a more intricate convex body but the function to minimize is the same. Furthermore, we describe a dual problem that leads to an optimality check and an error bound for the iterative algorithm.

  • Open Access

    Improved Replica Bounds for the Independence Ratio of Random Regular Graphs

    by Viktor Harangi

    Studying independent sets of maximum size is equivalent to considering the hard-core model with the fugacity parameter $$\lambda $$ λ tending to infinity. Finding the independence ratio of random d-regular graphs for some fixed degree d has received much attention both in random graph theory and in statistical physics. For $$d \ge 20$$ d ≥ 20 the problem is conjectured to exhibit 1-step replica symmetry breaking (1-RSB). The corresponding 1-RSB formula for the independence ratio was confirmed for (very) large d in a breakthrough paper by Ding, Sly, and Sun. Furthermore, the so-called interpolation method shows that this 1-RSB formula is an upper bound for each $$d \ge 3$$ d ≥ 3 . For $$d \le 19$$ d ≤ 19 this bound is not tight and full-RSB is expected. In this work we use numerical optimization to find good substituting parameters for discrete r-RSB formulas ( $$r=2,3,4,5$$ r = 2 , 3 , 4 , 5 ) to obtain improved rigorous upper bounds for the independence ratio for each degree $$3 \le d \le 19$$ 3 ≤ d ≤ 19 . As r grows, these formulas get increasingly complicated and it becomes challenging to compute their numerical values efficiently. Also, the functions to minimize have a large number of local minima, making global optimization a difficult task.


  • Open Access

    Improved replica bounds for the independence ratio of random regular graphs

    by Viktor Harangi

    Studying independent sets of maximum size is equivalent to considering the hard-core model with the fugacity parameter $\lambda$ tending to infinity. Finding the independence ratio of random $d$-regular graphs for some fixed degree $d$ has received much attention both in random graph theory and in statistical physics. For $d \geq 20$ the problem is conjectured to exhibit 1-step replica symmetry breaking (1-RSB). The corresponding 1-RSB formula for the independence ratio was confirmed for (very) large $d$ in a breakthrough paper by Ding, Sly, and Sun. Furthermore, the so-called interpolation method shows that this 1-RSB formula is an upper bound for each $d \geq 3$. For $d \leq 19$ this bound is not tight and full-RSB is expected. In this work we use numerical optimization to find good substituting parameters for discrete $r$-RSB formulas ($r=2,3,4,5$) to obtain improved rigorous upper bounds for the independence ratio for each degree $3 \leq d \leq 19$. As $r$ grows, these formulas get increasingly complicated and it becomes challenging to compute their numerical values efficiently. Also, the functions to minimize have a large number of local minima, making global optimization a difficult task.

  • Open Access

    Entropy and expansion

    by Endre Csóka, Viktor Harangi, Bálint Virág

    Shearer's inequality bounds the sum of joint entropies of random variables in terms of the total joint entropy. We give another lower bound for the same sum in terms of the individual entropies when the variables are functions of independent random seeds. The inequality involves a constant characterizing the expansion properties of the system. Our results generalize to entropy inequalities used in recent work in invariant settings, including the edge-vertex inequality for factor-of-IID processes, Bowen's entropy inequalities, and Bollob\'as's entropy bounds in random regular graphs. The proof method yields inequalities for other measures of randomness, including covariance. As an application, we give upper bounds for independent sets in both finite and infinite graphs.

  • Mutual information decay for factors of i.i.d.

    by Balázs Gerencsér, Viktor Harangi

    This paper is concerned with factors of independent and identically distributed processes on the .


  • Open Access

    Entropy inequalities for factors of IID

    by Ágnes Backhausz, Balázs Gerencsér, Viktor Harangi

    This paper is concerned with certain invariant random processes (called factors of IID) on infinite trees. Given such a process, one can assign entropies to different finite subgraphs of the tree. There are linear inequalities between these entropies that hold for any factor of IID process (e.g. "edge versus vertex" or "star versus edge"). These inequalities turned out to be very useful: they have several applications already, the most recent one is the Backhausz-Szegedy result on the eigenvectors of random regular graphs. We present new entropy inequalities in this paper. In fact, our approach provides a general "recipe" for how to find and prove such inequalities. Our key tool is a generalization of the edge-vertex inequality for a broader class of factor processes with fewer symmetries.