Hiroshi Hirai
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
Hiroshi Hirai has a total of 44 co-authors. Here are the top co-authors by number of shared publications:
- Yuni Iwamasa
Department of Mathematics, Graduate School of Science, Kobe University, Kobe, 657-8501, Japan
8 shared publications - Motoki Ikeda
Department of Mathematical Informatics, Graduate School of Information Science and Technology, The University of Tokyo, Tokyo, Japan
3 shared publications - Ryosuke Sato
Department of Mathematical Informatics Graduate School of Information Science and Technology The University of Tokyo 113-8656 Tokyo Japan
3 shared publications - Taihei Oki
Institute for Chemical Reaction Design and Discovery (ICReDD), Hokkaido University, Sapporo, Hokkaido 001-0021, Japan, and Center for Advanced Intelligence Project, RIKEN, Tokyo 103-0027, Japan
3 shared publications - Anthony Genevois
University of Montpellier, France
2 shared publications - Damian Osajda
Instytut Matematyczny, Uniwersytet Wrocławski, Wrocław, Poland
2 shared publications
Latest Publications
- Open Access
- 7 July 2026
- Published by Springer Nature in Foundations of Computational Mathematics
- p. 1-107
Interior-Point Methods on Manifolds: Theory and Applications
Interior-point methods offer a highly versatile framework for convex optimization that is effective in theory and practice. A key notion in their theory is that of a self-concordant barrier. We give a suitable generalization of self-concordance to Riemannian manifolds and show that it gives the same structural results and guarantees as in the Euclidean setting, in particular local quadratic convergence of Newton’s method. We analyze a path-following method for optimizing compatible objectives over a convex domain for which one has a self-concordant barrier, and obtain the standard complexity guarantees as in the Euclidean setting. We provide general constructions of barriers, and show that on the space of positive-definite matrices and other symmetric spaces, the squared distance to a point is self-concordant. To demonstrate the versatility of our framework, we give algorithms with state-of-the-art complexity guarantees for the general class of scaling and non-commutative optimization problems, which have been of much recent interest, and we provide the first algorithms for efficiently finding high-precision solutions for computing minimal enclosing balls and geometric medians in nonpositive curvature.
- 7 July 2026
- Published by Springer Nature in Foundations of Computational Mathematics
- p. 1-107
Open AccessInterior-Point Methods on Manifolds: Theory and Applications
Interior-point methods offer a highly versatile framework for convex optimization that is effective in theory and practice. A key notion in their theory is that of a self-concordant barrier. We give a suitable generalization of self-concordance to Riemannian manifolds and show that it gives the same structural results and guarantees as in the Euclidean setting, in particular local quadratic convergence of Newton’s method. We analyze a path-following method for optimizing compatible objectives over a convex domain for which one has a self-concordant barrier, and obtain the standard complexity guarantees as in the Euclidean setting. We provide general constructions of barriers, and show that on the space of positive-definite matrices and other symmetric spaces, the squared distance to a point is self-concordant. To demonstrate the versatility of our framework, we give algorithms with state-of-the-art complexity guarantees for the general class of scaling and non-commutative optimization problems, which have been of much recent interest, and we provide the first algorithms for efficiently finding high-precision solutions for computing minimal enclosing balls and geometric medians in nonpositive curvature.
- 24 April 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
Gradient Descent for Unbounded Convex Functions on Hadamard Manifolds and Its Applications to Scaling Problems
In this paper, we study the asymptotic behavior of continuous- and discrete-time gradient flows of a “lower-unbounded” convex function f on a Hadamard manifold M, particularly their convergence properties to the boundary [ ] at infinity of M. We establish a duality theorem that the infimum of the gradient-norm [ ] of f over M is equal to the supremum of the negative of the recession function [ ] of f over the boundary [ ], provided the infimum is positive. Further, the infimum and the supremum are obtained by the limit of the gradient flow of f. Our results feature convex optimization ingredients of the moment-weight inequality for reductive group actions, and are applied to noncommutative optimization. We show that gradient descent of the Kempf-Ness function for an unstable orbit converges to a destabilizing 1-parameter subgroup in the Hilbert-Mumford criterion, and the associated moment-map sequence converges to the minimum-norm point of the moment polytope. We show further refinements for operator scaling—the left-right action on a matrix tuple [ ]. We characterize the gradient-flow limit of operator scaling by a vector-space generalization of the classical Dulmage-Mendelsohn decomposition of a bipartite graph. For a special case of [ ], we reveal that the limit determines the Kronecker canonical form of a matrix pencil [ ]. Funding: H. Hirai was supported by the Japan Society for the Promotion of Science (KAKENHI [Grants JP21K19759 and JP24K21315]). K. Sakabe was supported by Deutsche Forschungsgemeinschaft (DFG, German Research Foundation [Grant 556164098]) and the European Research Council (ERC Starting Grant SYMOPTIC [Grant 101040907]).
- 24 April 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
Gradient Descent for Unbounded Convex Functions on Hadamard Manifolds and Its Applications to Scaling Problems
In this paper, we study the asymptotic behavior of continuous- and discrete-time gradient flows of a “lower-unbounded” convex function f on a Hadamard manifold M, particularly their convergence properties to the boundary [ ] at infinity of M. We establish a duality theorem that the infimum of the gradient-norm [ ] of f over M is equal to the supremum of the negative of the recession function [ ] of f over the boundary [ ], provided the infimum is positive. Further, the infimum and the supremum are obtained by the limit of the gradient flow of f. Our results feature convex optimization ingredients of the moment-weight inequality for reductive group actions, and are applied to noncommutative optimization. We show that gradient descent of the Kempf-Ness function for an unstable orbit converges to a destabilizing 1-parameter subgroup in the Hilbert-Mumford criterion, and the associated moment-map sequence converges to the minimum-norm point of the moment polytope. We show further refinements for operator scaling—the left-right action on a matrix tuple [ ]. We characterize the gradient-flow limit of operator scaling by a vector-space generalization of the classical Dulmage-Mendelsohn decomposition of a bipartite graph. For a special case of [ ], we reveal that the limit determines the Kronecker canonical form of a matrix pencil [ ]. Funding: H. Hirai was supported by the Japan Society for the Promotion of Science (KAKENHI [Grants JP21K19759 and JP24K21315]). K. Sakabe was supported by Deutsche Forschungsgemeinschaft (DFG, German Research Foundation [Grant 556164098]) and the European Research Council (ERC Starting Grant SYMOPTIC [Grant 101040907]).
- Open Access
- 31 October 2025
- Published by Elsevier in Linear Algebra and its Applications
- Vol. 730, 525-545
A scaling characterization of nc-rank via unbounded gradient flow
- 31 October 2025
- Published by Elsevier in Linear Algebra and its Applications
- Vol. 730, 525-545
Open AccessA scaling characterization of nc-rank via unbounded gradient flow
- Open Access
- 6 February 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Economics and Computation
- Vol. 13 (1) , 1-30
Polyhedral Clinching Auctions for Indivisible Goods
In this study, we propose a polyhedral clinching auction for indivisible goods, which has so far been studied for divisible goods. As in the divisible setting by Goel et al. (2015), our mechanism enjoys incentive compatibility, individual rationality, and Pareto optimality, and works with polymatroidal environments. A notable feature of this mechanism for the indivisible setting is that the entire procedure can be conducted in time polynomial of the number of buyers and goods. Moreover, we show additional efficiency guarantees, recently established by Sato for the divisible setting: the liquid welfare (LW) of our mechanism achieves more than half of the optimal LW, and the social welfare is more than the optimal LW.
- 6 February 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Economics and Computation
- Vol. 13 (1) , 1-30
Open AccessPolyhedral Clinching Auctions for Indivisible Goods
In this study, we propose a polyhedral clinching auction for indivisible goods, which has so far been studied for divisible goods. As in the divisible setting by Goel et al. (2015), our mechanism enjoys incentive compatibility, individual rationality, and Pareto optimality, and works with polymatroidal environments. A notable feature of this mechanism for the indivisible setting is that the entire procedure can be conducted in time polynomial of the number of buyers and goods. Moreover, we show additional efficiency guarantees, recently established by Sato for the divisible setting: the liquid welfare (LW) of our mechanism achieves more than half of the optimal LW, and the social welfare is more than the optimal LW.
- Top Cited PapersOpen Access
- 1 January 2025
- Published by Mathematical Sciences Publishers in Geometry & Topology
- Vol. 29 (1) , 1-70
Helly groups
Helly graphs are graphs in which every family of pairwise-intersecting balls has a nonempty intersection. This is a classical and widely studied class of graphs. We focus on groups acting geometrically on Helly graphs-Helly groups. We provide numerous examples of such groups: all (Gromov) hyperbolic groups, CAT.0/ cubical groups, finitely presented graphical C.4/-T.4/ small cancellation groups and type-preserving uniform lattices in Euclidean buildings of type C n are Helly; free products of Helly groups with amalgamation over finite subgroups, graph products of Helly groups, some diagram products of Helly groups, some right-angled graphs of Helly groups and quotients of Helly groups by finite normal subgroups are Helly. We show many properties of Helly groups: biautomaticity, existence of finite-dimensional models for classifying spaces for proper actions, contractibility of asymptotic cones, existence of EZ-boundaries, satisfiability of the Farrell-Jones conjecture and satisfiability of the coarse Baum-Connes conjecture. This leads to new results for some classical families of groups (eg for FC-type Artin groups) and to a unified approach to results obtained earlier. 20F06, 20F65, 20F67
- 1 January 2025
- Published by Mathematical Sciences Publishers in Geometry & Topology
- Vol. 29 (1) , 1-70
Top Cited PapersOpen AccessHelly groups
Helly graphs are graphs in which every family of pairwise-intersecting balls has a nonempty intersection. This is a classical and widely studied class of graphs. We focus on groups acting geometrically on Helly graphs-Helly groups. We provide numerous examples of such groups: all (Gromov) hyperbolic groups, CAT.0/ cubical groups, finitely presented graphical C.4/-T.4/ small cancellation groups and type-preserving uniform lattices in Euclidean buildings of type C n are Helly; free products of Helly groups with amalgamation over finite subgroups, graph products of Helly groups, some diagram products of Helly groups, some right-angled graphs of Helly groups and quotients of Helly groups by finite normal subgroups are Helly. We show many properties of Helly groups: biautomaticity, existence of finite-dimensional models for classifying spaces for proper actions, contractibility of asymptotic cones, existence of EZ-boundaries, satisfiability of the Farrell-Jones conjecture and satisfiability of the coarse Baum-Connes conjecture. This leads to new results for some classical families of groups (eg for FC-type Artin groups) and to a unified approach to results obtained earlier. 20F06, 20F65, 20F67
- Open Access
- 2 November 2024
- Published by Springer Nature in Mathematical Programming
- Vol. 213 (1-2) , 941-984
Algebraic combinatorial optimization on the degree of determinants of noncommutative symbolic matrices
We address the computation of the degrees of minors of a noncommutative symbolic matrix of form $$ A[c] :=\sum _{k=1}^m A_k t^{c_k} x_k, $$ where $$A_k$$ are matrices over a field $$\mathbb {K}$$ , $$x_k$$ are noncommutative variables, $$c_k$$ are integer weights, and t is a commuting variable specifying the degree. This problem extends noncommutative Edmonds’ problem (Ivanyos et al. in Comput Complex 26:717–763, 2017), and can formulate various combinatorial optimization problems. Extending the study by Hirai 2018, and Hirai, Ikeda 2022, we provide novel duality theorems and polyhedral characterization for the maximum degrees of minors of A[c] of all sizes, and develop a strongly polynomial-time algorithm for computing them. This algorithm is viewed as a unified algebraization of the classical Hungarian method for bipartite matching and the weight-splitting algorithm for linear matroid intersection. As applications, we provide polynomial-time algorithms for weighted fractional linear matroid matching and for membership of rank-2 Brascamp–Lieb polytopes.- 2 November 2024
- Published by Springer Nature in Mathematical Programming
- Vol. 213 (1-2) , 941-984
Open AccessAlgebraic combinatorial optimization on the degree of determinants of noncommutative symbolic matrices
We address the computation of the degrees of minors of a noncommutative symbolic matrix of form $$ A[c] :=\sum _{k=1}^m A_k t^{c_k} x_k, $$ where $$A_k$$ are matrices over a field $$\mathbb {K}$$ , $$x_k$$ are noncommutative variables, $$c_k$$ are integer weights, and t is a commuting variable specifying the degree. This problem extends noncommutative Edmonds’ problem (Ivanyos et al. in Comput Complex 26:717–763, 2017), and can formulate various combinatorial optimization problems. Extending the study by Hirai 2018, and Hirai, Ikeda 2022, we provide novel duality theorems and polyhedral characterization for the maximum degrees of minors of A[c] of all sizes, and develop a strongly polynomial-time algorithm for computing them. This algorithm is viewed as a unified algebraization of the classical Hungarian method for bipartite matching and the weight-splitting algorithm for linear matroid intersection. As applications, we provide polynomial-time algorithms for weighted fractional linear matroid matching and for membership of rank-2 Brascamp–Lieb polytopes. - 1 November 2024
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 49 (4) , 2166-2179
Finding Hall Blockers by Matrix Scaling
- 1 November 2024
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 49 (4) , 2166-2179
Finding Hall Blockers by Matrix Scaling
- Open Access
Minimum 0-Extension Problems on Directed Metrics
For a metric $\mu$ on a finite set $T$, the minimum 0-extension problem 0-Ext$[\mu]$ is defined as follows: Given $V\supseteq T$ and $\ c:{V \choose 2}\rightarrow \mathbf{Q_+}$, minimize $\sum c(xy)\mu(\gamma(x),\gamma(y))$ subject to $\gamma:V\rightarrow T,\ \gamma(t)=t\ (\forall t\in T)$, where the sum is taken over all unordered pairs in $V$. This problem generalizes several classical combinatorial optimization problems such as the minimum cut problem or the multiterminal cut problem. Karzanov and Hirai established a complete classification of metrics $\mu$ for which 0-Ext$[\mu]$ is polynomial time solvable or NP-hard. This result can also be viewed as a sharpening of the general dichotomy theorem for finite-valued CSPs (Thapper and \v{Z}ivn\'{y} 2016) specialized to 0-Ext$[\mu]$. In this paper, we consider a directed version $\overrightarrow{0}$-Ext$[\mu]$ of the minimum 0-extension problem, where $\mu$ and $c$ are not assumed to be symmetric. We extend the NP-hardness condition of 0-Ext$[\mu]$ to $\overrightarrow{0}$-Ext$[\mu]$: If $\mu$ cannot be represented as the shortest path metric of an orientable modular graph with an orbit-invariant ``directed'' edge-length, then $\overrightarrow{0}$-Ext$[\mu]$ is NP-hard. We also show a partial converse: If $\mu$ is a directed metric of a modular lattice with an orbit-invariant directed edge-length, then $\overrightarrow{0}$-Ext$[\mu]$ is tractable. We further provide a new NP-hardness condition characteristic of $\overrightarrow{0}$-Ext$[\mu]$, and establish a dichotomy for the case where $\mu$ is a directed metric of a star.Open AccessMinimum 0-Extension Problems on Directed Metrics
For a metric $\mu$ on a finite set $T$, the minimum 0-extension problem 0-Ext$[\mu]$ is defined as follows: Given $V\supseteq T$ and $\ c:{V \choose 2}\rightarrow \mathbf{Q_+}$, minimize $\sum c(xy)\mu(\gamma(x),\gamma(y))$ subject to $\gamma:V\rightarrow T,\ \gamma(t)=t\ (\forall t\in T)$, where the sum is taken over all unordered pairs in $V$. This problem generalizes several classical combinatorial optimization problems such as the minimum cut problem or the multiterminal cut problem. Karzanov and Hirai established a complete classification of metrics $\mu$ for which 0-Ext$[\mu]$ is polynomial time solvable or NP-hard. This result can also be viewed as a sharpening of the general dichotomy theorem for finite-valued CSPs (Thapper and \v{Z}ivn\'{y} 2016) specialized to 0-Ext$[\mu]$. In this paper, we consider a directed version $\overrightarrow{0}$-Ext$[\mu]$ of the minimum 0-extension problem, where $\mu$ and $c$ are not assumed to be symmetric. We extend the NP-hardness condition of 0-Ext$[\mu]$ to $\overrightarrow{0}$-Ext$[\mu]$: If $\mu$ cannot be represented as the shortest path metric of an orientable modular graph with an orbit-invariant ``directed'' edge-length, then $\overrightarrow{0}$-Ext$[\mu]$ is NP-hard. We also show a partial converse: If $\mu$ is a directed metric of a modular lattice with an orbit-invariant directed edge-length, then $\overrightarrow{0}$-Ext$[\mu]$ is tractable. We further provide a new NP-hardness condition characteristic of $\overrightarrow{0}$-Ext$[\mu]$, and establish a dichotomy for the case where $\mu$ is a directed metric of a star. - 31 December 2023
- Published by Springer Nature
- p. 366-383
Polyhedral Clinching Auctions for Indivisible Goods
- 31 December 2023
- Published by Springer Nature
- p. 366-383
Polyhedral Clinching Auctions for Indivisible Goods
- Open Access
Algebraic combinatorial optimization on the degree of determinants of noncommutative symbolic matrices
We address the computation of the degrees of minors of a noncommutative symbolic matrix of form \[ A[c] := \sum_{k=1}^m A_k t^{c_k} x_k, \] where $A_k$ are matrices over a field $\mathbb{K}$, $x_i$ are noncommutative variables, $c_k$ are integer weights, and $t$ is a commuting variable specifying the degree. This problem extends noncommutative Edmonds' problem (Ivanyos et al. 2017), and can formulate various combinatorial optimization problems. Extending the study by Hirai 2018, and Hirai, Ikeda 2022, we provide novel duality theorems and polyhedral characterization for the maximum degrees of minors of $A[c]$ of all sizes, and develop a strongly polynomial-time algorithm for computing them. This algorithm is viewed as a unified algebraization of the classical Hungarian method for bipartite matching and the weight-splitting algorithm for linear matroid intersection. As applications, we provide polynomial-time algorithms for weighted fractional linear matroid matching and linear optimization over rank-2 Brascamp-Lieb polytopes.Open AccessAlgebraic combinatorial optimization on the degree of determinants of noncommutative symbolic matrices
We address the computation of the degrees of minors of a noncommutative symbolic matrix of form \[ A[c] := \sum_{k=1}^m A_k t^{c_k} x_k, \] where $A_k$ are matrices over a field $\mathbb{K}$, $x_i$ are noncommutative variables, $c_k$ are integer weights, and $t$ is a commuting variable specifying the degree. This problem extends noncommutative Edmonds' problem (Ivanyos et al. 2017), and can formulate various combinatorial optimization problems. Extending the study by Hirai 2018, and Hirai, Ikeda 2022, we provide novel duality theorems and polyhedral characterization for the maximum degrees of minors of $A[c]$ of all sizes, and develop a strongly polynomial-time algorithm for computing them. This algorithm is viewed as a unified algebraization of the classical Hungarian method for bipartite matching and the weight-splitting algorithm for linear matroid intersection. As applications, we provide polynomial-time algorithms for weighted fractional linear matroid matching and linear optimization over rank-2 Brascamp-Lieb polytopes.