Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data. A simulation from public publication records: the people listed were not invited and did not agree to review.
? Tutorial for this page

Gilles Bonnet

dblp:245/4164 · DBLP profile ↗
← Back
2ranked-venue papers
2as first author
2since 2021 · last 2026
0000-0003-4161-4124ORCID · reported

Domains — the database's venue-derived domains; a paper can count in several

Graphics, computer vision, multimedia, augmented reality and games · 1 · 1 first-author · 1 since 2021Theory of computation · 1 · 1 first-author · 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 1 heaviest of 1, each with the papers that count most for it

TopicWeightPapersLastEvidence papers
Mathematical optimization › combinatorial optimization
polyhedral combinatorics
0.612022
Asymptotic Bounds on the Combinatorial Diameter of Random Polytopes · SoCG 2022

Methods — techniques the papers use, named apart from their topics

probabilistic method · 0.6convex hull · 0.6
YearPublicationVenuePosition
2026 Asymptotic Bounds on the Combinatorial Diameter of Random Polytopes
Gilles Bonnet, Daniel Dadush, Uri Grupel, Sophie Huiberts, Galyna V. Livshyts
Discret. Comput. Geom.1
2022 Asymptotic Bounds on the Combinatorial Diameter of Random Polytopes
abstract
The combinatorial diameter $\operatorname{diam}(P)$ of a polytope $P$ is the maximum shortest path distance between any pair of vertices. In this paper, we provide upper and lower bounds on the combinatorial diameter of a random "spherical" polytope, which is tight to within one factor of dimension when the number of inequalities is large compared to the dimension. More precisely, for an $n$-dimensional polytope $P$ defined by the intersection of $m$ i.i.d.\ half-spaces whose normals are chosen uniformly from the sphere, we show that $\operatorname{diam}(P)$ is $Ω(n m^{\frac{1}{n-1}})$ and $O(n^2 m^{\frac{1}{n-1}} + n^5 4^n)$ with high probability when $m \geq 2^{Ω(n)}$. For the upper bound, we first prove that the number of vertices in any fixed two dimensional projection sharply concentrates around its expectation when $m$ is large, where we rely on the $Θ(n^2 m^{\frac{1}{n-1}})$ bound on the expectation due to Borgwardt [Math. Oper. Res., 1999]. To obtain the diameter upper bound, we stitch these ``shadows paths'' together over a suitable net using worst-case diameter bounds to connect vertices to the nearest shadow. For the lower bound, we first reduce to lower bounding the diameter of the dual polytope $P^\circ$, corresponding to a random convex hull, by showing the relation $\operatorname{diam}(P) \geq (n-1)(\operatorname{diam}(P^\circ)-2)$. We then prove that the shortest path between any ``nearly'' antipodal pair vertices of $P^\circ$ has length $Ω(m^{\frac{1}{n-1}})$.
Gilles Bonnet, Daniel Dadush, Uri Grupel, Sophie Huiberts, Galyna V. Livshyts
SoCG1