Demo Data from EDBT 2026 / reviewers in the wild / expert
Nicolas Vandame
dblp:310/1592
· DBLP profile ↗
1ranked-venue papers
0as first author
1since 2021 · last 2022
—ORCID · none
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 1 · 1 since 2021
Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.
| Theoretical computer science
1 paper |
Mathematical optimization · 100% |
Topics — the 4 heaviest of 4, each with the papers that count most for it
| Topic | Weight | Papers | Last | Evidence papers |
|---|---|---|---|---|
Mathematical optimization › numerical computation › numerical optimization › second-order methods
interior point methods |
0.6 | 1 | 2022 | No self-concordant barrier interior point method is strongly polynomial · STOC 2022 |
Mathematical optimization
linear programming |
0.6 | 1 | 2022 | No self-concordant barrier interior point method is strongly polynomial · STOC 2022 |
Mathematical optimization › linear programming
strongly polynomial algorithms |
0.6 | 1 | 2022 | No self-concordant barrier interior point method is strongly polynomial · STOC 2022 |
Mathematical optimization › convergence analysis
iteration complexity |
0.2 | 1 | 2022 | No self-concordant barrier interior point method is strongly polynomial · STOC 2022 |
Methods — techniques the papers use, named apart from their topics
parametric optimization · 0.6central path analysis · 0.6
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2022 | No self-concordant barrier interior point method is strongly polynomialabstractIt is an open question to determine if the theory of self-concordant barriers can provide an interior point method with strongly polynomial complexity in linear programming. In the special case of the logarithmic barrier, it was shown in [Allamigeon, Benchimol, Gaubert and Joswig, SIAM J. on Applied Algebra and Geometry, 2018] that the answer is negative. In this paper, we show that none of the self-concordant barrier interior point methods is strongly polynomial. This result is obtained by establishing that, on parametric families of convex optimization problems, the log-limit of the central path degenerates to a piecewise linear curve, independently of the choice of the barrier function. We provide an explicit linear program that falls in the same class as the Klee–Minty counterexample for the simplex method, i.e., in which the feasible region is a combinatorial cube and the number of iterations is Ω(2n). Xavier Allamigeon, Stéphane Gaubert, Nicolas Vandame |
STOC | 3 |