Viktor Harangi
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
Research Subjects
Research Interests
Viktor Harangi has a total of 14 co-authors. Here are the top co-authors by number of shared publications:
- Balázs Gerencsér
HUN-REN Alfréd Rényi Institute of Mathematics Budapest Hungary
7 shared publications - Ágnes Backhausz
Department of Probability Theory and Statistics, Faculty of Science, ELTE Eötvös Loránd University, Budapest, Hungary
3 shared publications - Bo Bai
Huawei Technologies Company Ltd., Shenzhen, China
2 shared publications - Máté Vizer
ALFRÉD RÉNYI INSTITUTE OF MATHEMATICS BUDAPEST HUNGARY
2 shared publications - Xueyan Niu
Department of Mathematical Sciences Theory Lab Tsinghua University 2012 Beijing China
2 shared publications András Máthé
1 shared publication
Latest Publications
- Open Access
- 25 March 2026
- Published by Elsevier in Journal of Combinatorial Theory, Series B
- Vol. 179, 147-204
The least balanced graphs and trees
- 25 March 2026
- Published by Elsevier in Journal of Combinatorial Theory, Series B
- Vol. 179, 147-204
Open AccessThe least balanced graphs and trees
- Open Access
RSB bounds on the maximum cut
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.
Open AccessRSB bounds on the maximum cut
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.
- 14 September 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (2) , 904-919
Conditional Graph Entropy as an Alternating Minimization Problem
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.
- 14 September 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (2) , 904-919
Conditional Graph Entropy as an Alternating Minimization Problem
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
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 AccessConditional graph entropy as an alternating minimization problem
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
- 28 January 2023
- Published by Springer Nature in Journal of Statistical Physics
- Vol. 190 (3) , 1-24
Improved Replica Bounds for the Independence Ratio of Random Regular Graphs
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$$ 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$$ . For $$d \le 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 \le d \le 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.- 28 January 2023
- Published by Springer Nature in Journal of Statistical Physics
- Vol. 190 (3) , 1-24
Open AccessImproved Replica Bounds for the Independence Ratio of Random Regular Graphs
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$$ 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$$ . For $$d \le 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 \le d \le 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
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 AccessImproved replica bounds for the independence ratio of random regular graphs
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
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.
Open AccessEntropy and expansion
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.
- 29 April 2018
- Published by Cambridge University Press (CUP) in Ergodic Theory and Dynamical Systems
- Vol. 39 (11) , 3015-3030
Mutual information decay for factors of i.i.d.
This paper is concerned with factors of independent and identically distributed processes on the .
- 29 April 2018
- Published by Cambridge University Press (CUP) in Ergodic Theory and Dynamical Systems
- Vol. 39 (11) , 3015-3030
Mutual information decay for factors of i.i.d.
This paper is concerned with factors of independent and identically distributed processes on the .
- 13 April 2018
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 62 (1) , 239
Correction to: Acute Sets of Exponentially Optimal Size
- 13 April 2018
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 62 (1) , 239
Correction to: Acute Sets of Exponentially Optimal Size
- Open Access
Entropy inequalities for factors of IID
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.
Open AccessEntropy inequalities for factors of IID
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.