<figure><img src="image_1.png" /></figure>

HAL
open science

# Optimal Smoothed Analysis of the Simplex Method

Eleon Bach, Sophie Huiberts

► To cite this version:

Eleon Bach, Sophie Huiberts. Optimal Smoothed Analysis of the Simplex Method. Symposium on Foundations of Computer Science, Dec 2025, Sydney, Australia. hal-05345257

HAL Id: hal-05345257

https://hal.science/hal-05345257v1

Submitted on 3 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Optimal Smoothed Analysis of the Simplex Method

Eleon Bach*¹ and Sophie Huiberts†²

¹EPFL

²CNRS, Université Clermont Auvergne Clermont Auvergne INP, Mines Saint-Etienne, LIMOS

April 5, 2025

## Abstract

Smoothed analysis is a method for analyzing the performance of algorithms, used especially for those algorithms whose running time in practice is significantly better than what can be proven through worst-case analysis. Spielman and Teng (STOC '01) introduced the smoothed analysis framework of algorithm analysis and applied it to the simplex method. Given an arbitrary linear program with $d$ variables and $n$ inequality constraints, Spielman and Teng proved that the simplex method runs in time $O(\sigma^{-30}d^{55}n^{86})$, where $\sigma > 0$ is the standard deviation of Gaussian distributed noise added to the original LP data. Spielman and Teng's result was simplified and strengthened over a series of works, with the current strongest upper bound being $O(\sigma^{-3/2}d^{13/4} \log(n)^{7/4})$ pivot steps due to Huiberts, Lee and Zhang (STOC '23). We prove that there exists a simplex method whose smoothed complexity is upper bounded by $O(\sigma^{-1/2}d^{11/4} \log(n)^{7/4})$ pivot steps. Furthermore, we prove a matching high-probability lower bound of $\Omega(\sigma^{-1/2}d^{1/2} \ln(4/\sigma)^{-1/4})$ on the combinatorial diameter of the feasible polyhedron after smoothing, on instances using $n = \lfloor(4/\sigma)^d\rfloor$ inequality constraints. This lower bound indicates that our algorithm has optimal noise dependence among all simplex methods, up to polylogarithmic factors.

## 1 Introduction

Ever since its first use in early 1948, the simplex method has been one of the primary algorithms for solving linear programming (LP) problems. For the purpose of this paper, an LP is a problem described by input data $A \in \mathbb{R}^{n \times d}$, $b \in \mathbb{R}^n$, $c \in \mathbb{R}^d$ and is written as

$$ \begin{array}{ll} \text{maximize} & c^\top x \\ \text{subject to} & Ax \leq b. \end{array} $$

The computational task at hand is to find if there exists any $x \in \mathbb{R}^d$ such that the system of inequalities $Ax \leq b$ holds. If such a feasible solution $x$ exists, then one must report either a feasible solution $x$ for which additionally the inner product $c^\top x$ is maximal among all feasible solutions, or a certificate that the set of feasible solutions is *unbounded*. Linear programming problems arise in innumerable industrial contexts. Furthermore, they are often used as fundamental steps in a vast range of other optimization algorithms as they are well-known to be solvable efficiently. Despite the tremendous progress for polynomial time methods in general [Kha80] and interior point methods in particular [Kar84; Ren88; Meh92; LS14; All+22], the simplex method remains one of the most popular algorithms to solve LPs in a wide variety of practical contexts.

The simplex method is best thought of as a class of algorithms, differing in specific details such as the choice of the *pivot rule* or the *phase 1* procedure. Navigating from one vertex of the feasible set to another, the *pivot rule* is the part of a simplex method that decides in which direction the *pivot step* will move. Notable examples of *pivot rules* include the most negative reduced cost rule [Dan51], the steepest edge rule and its approximations [Har73; Gol76; FG92], and the shadow vertex rule [GS55; Bor77].

<footnote>*eleon.bach@proton.me.</footnote>

<footnote>†sophie@huiberts.me. This work was funded by ANR grant ANR-24-CE48-2762.</footnote>
Although there have been substantial improvements over the simplex method as it was first introduced by Dantzig, one thing has not changed: the total number of pivot steps required to solve LPs in practice scales roughly linear in the dimensions of the problem [Dan63; Sha87; And04; FIC]. Despite many decades of practical experience supporting this observation, it remains a major challenge for the theory of algorithms to explain this phenomenon. This is further complicated by the results from worst-case analysis: for almost every major pivot rule, there are theoretical constructions known that make the simplex method take exponentially many pivot steps before reaching an optimal solution. Because of the misleading results of worst-case analysis, the simplex method has been a showcase for the development of new methods to go beyond worst case analysis.

The majority of these worst-case constructions are based on *deformed products* [KM72; Jer73; AC78; GS79; Mur80; Gol83; AZ98] and extending arguments [Bla24] or on Markov decision processes [FHZ11; Fri11; DFH22; DM23]. The fastest known simplex method under the worst-case analysis paradigm is randomized and requires $2^{O(\sqrt{d \log(1+n/d)})}$ pivot steps [Kal92; MSW96; HZ15]. The simplex method was shown to have polynomial run time for classes of polytopes such as 0/1-polytopes [Bla+21; Bla23], bounded subdeterminants [BR13; DH16], and bounded ratios of non-zero slack values [KM11].

During the 70's and 80's, there were a number of investigations into the average-case complexity of the simplex method. A wide variety of models was studied, including drawing the rows of A from a spherically-symmetric distribution [Bor77; Bor82; Bor87; Bor99; Bon+22], drawing the combined vector $(c, b)$ from a spherically symmetric distribution [Sma83], having fixed $A, b$ and every inequality constraint independently being either $a_i^\top x \le b_i$ or $a_i^\top \ge b_i$ [Hai83], and a range of other models [AM85; Meg86; Tod86; AKS87]. For an in-depth survey we refer the reader to [Bor87].

A major weakness of average-case analysis is that real-life LPs are structured in recognizable ways, whereas average-case LPs have no such structure. As such, it is reasonable to question to what extent average-case analyses succeed at explaining the simplex method's performance in practice. Smoothed analysis is a more sophisticated way of going beyond worst-case analysis [Rou20], drawing on the advantages of average-case analysis while still preserving the large-scale geometric structure in the input instances. It is commonly understood to demonstrate that inputs on which the simplex method performs badly are “pathological”, in the sense that they depend on very brittle small-scale structures in input data. Often the focus of works in smoothed analysis is on improving the dependence on the noise parameter, which can then be interpreted as measuring “how brittle” these structures are. Beyond the simplex method, smoothed analysis has been applied to a wide range of popular algorithms. Examples of this include multicriteria optimization [BV03; Bru+14; Bei+22], Lloyd's $k$-mean algorithm [AMR11], the 2-OPT heuristic for the TSP [ERV13; KMV23; MR23], local Max-Cut [Che+20; Che+24], makespan scheduling [RSV25], policy iteration for MDPs [CY23] and many more.

One assumes that a base LP problem is adversarially constructed

$$ \begin{array}{ll} \text{maximize} & c^\top x \\ \text{subject to} & \bar{A}x \le \bar{b}, \end{array} $$

with the assumption that $\bar{A} \in \mathbb{R}^{n \times d}$ and $\bar{b} \in \mathbb{R}^n$ are such that the rows of the combined matrix $(\bar{A}, \bar{b})$ each have Euclidean norm at most 1. Subsequently, this input data gets randomly perturbed. For a parameter $\sigma > 0$, one samples $\hat{A} \in \mathbb{R}^{n \times d}$ and $\hat{b} \in \mathbb{R}^n$ with independent entries, each entry being drawn from a Gaussian distribution with mean 0 and variance $\sigma^2$. The *smoothed complexity* of an algorithm is the expected running time to solve the perturbed problem

$$ \begin{array}{ll} \text{maximize} & c^\top x \\ \text{subject to} & (\bar{A} + \hat{A})x \le \bar{b} + \hat{b}, \end{array} \qquad (\text{Input LP}) $$

where the running time is to be bounded as a polynomial function in $n, d$ and $\sigma^{-1}$. The dependence on $\sigma$ is key to smoothed analysis. When $\sigma$ is large enough such that $\hat{A}$ dominates $\bar{A}$, the smoothed complexity converges to the average case as analyzed by Borgwardt [Bor77]. If, on the contrary, $\sigma$ goes to 0, we find ourselves in the situation to analyze the worst-case complexity of the simplex method. By choosing small $\sigma$, for example inversely polynomial in $n$, smoothed analysis combines advantages of both worst-case and average-case analysis. A low smoothed complexity for an algorithm is thought to mean that one should expect this algorithm to perform well in practice. One proposed reason is that many real-world instances are generated from data that is inherently noisy by nature. In further contrast to average-case analysis, we observe that the probability mass used in (Input LP) is concentrated in a region of radius $O(\sigma\sqrt{d \ln(n/d)})$. When $\sigma$ is small, this region contains an exponentially small fraction
of the probability mass as considered in the average-case analysis as by Borgwardt [Bor77]. Smoothed analysis results are thus much stronger than comparable average-case analysis results. The case when $\sigma$ is large is considered less interesting due to it not preserving the original structure in the instance. To illustrate this point, consider the following: every row of $\bar{A}$ is assumed to have Euclidean norm at most 1. If $\sigma > 1/\sqrt{d}$ then every row of $A = \bar{A} + \hat{A}$ is expected to consist of more noise than structure. Hence the case of small $\sigma$ is most commonly studied, with many papers reporting in their final running time bound only the term with highest dependence on $\sigma$.

Spielman and Teng's result is made up of two parts. First an analysis of the shadow size $D(n, d, \sigma)$, which consists of taking a (fixed) two-dimensional linear subspace $W$ and upper bounding the expected number of vertices of the orthogonal projection $\pi_W(\{x : (\bar{A} + \hat{A})x \le 1\})$ onto $W$. Formally, what is bounded is the quantity

$$D(n, d, \sigma) = \max_{\bar{A}, c, c'} \mathbb{E}_{\hat{A}} \left[ \text{vertices} \left( \pi_{\text{span}(c, c')} (\{x : (\bar{A} + \hat{A})x \le 1\}) \right) \right],$$

where $\bar{A}$ is assumed to have rows each of Euclidean norm at most 1. This quantity is used to bound the number of pivot steps taken by the shadow vertex simplex method when moving, on the set $\{x : (\bar{A} + \hat{A})x \le 1\}$, from the maximizer of a fixed objective $c$ to the maximizer of another fixed objective $c'$.

The second part is an algorithmic reduction, showing that there exists a simplex method whose running time can be bounded as a function of $D(n, d, \sigma)$. Their algorithm is based on the shadow vertex pivot rule. This pivot rule works by having two objectives $c, c' \in \mathbb{R}^d$ and visiting all basic solutions that maximize some positive linear combination of the two. Starting from an optimal basic feasible solution to the first objective, it pivots until it finds an optimal basic feasible solution to the second objective (or finds an infinite ray certifying unboundednes). When the two objectives are chosen independently of the noise $\bar{A}$, and the right-hand side vector is the unperturbed all-ones vector, then the number of pivot steps required by the shadow vertex rule is naturally upper bounded by the shadow size $D(n, d, \sigma)$. They proved a bound on the shadow size of

$$D(n, d, \sigma) \le \frac{10^8 nd^3}{\min(\sigma, 1/3\sqrt{d \ln n})^6},$$

and found a simplex method that requires an estimated

$$O(nd \ln(n/\min(1, \sigma)))D(n, d, \frac{\min(1, \sigma^5)}{d^{8.5}n^{14} \ln^{2.5}(n)})$$

pivot steps under the smoothed analysis framework. This combines to a total of $O^*(n^{86}d^{55}\sigma^{-30})$ pivot steps, ignoring logarithmic factors and assuming that $\sigma \le 1/3\sqrt{d \ln n}$. Note that this last assumption on $\sigma$ may be made without loss of generality, for we can scale down the constraints of the LP to make the assumption hold true. The result of this scaling can be captured in an additive term in the upper bound that is independent of $\sigma$.

This work was built upon by [DS05], who improved the shadow bound to

$$D(n, d, \sigma) \le \frac{10^4 n^2 d \ln n}{\sigma^2} + 10^5 n^2 d^2 \ln^2 n.$$

Vershynin later proved in [Ver09] a shadow bound of $D(n, d, \sigma) \le d^3\sigma^{-4} + d^5\ln^2 n$, dramatically improving the dependence on $n$ to poly-logarithmic, which is the state-of-the-art dependence of $n$ up today. The price he paid, however, was a worse dependence on the noise parameter $\sigma$. Finding the optimal dependence on $\sigma$ while not losing again on the poly-logarithmic dependence on $n$, has been the objective of smoothed analysis of the shadow vertex method follow-up work ever since. He found an alternative algorithm running in time $O(D(n, d, \min(\sigma, 1/\sqrt{d \ln n}), 1/d^{3/2} \ln d))$. With the two works [DS05] and [Ver09], there was a situation where one bound on $D(n, d, \sigma)$ had better dependence on $\sigma$ and the other had much better dependence on $n$. This was resolved with the work of [DH20], who proved a best-of-both-worlds bound of $D(n, d, \sigma) \le d^2\sigma^{-2}\sqrt{\ln n} + d^3 \ln^{1.5} n$. They also observed that the comparatively simple dimension-by-dimension phase 1 algorithm of [Bor87] could be used with an expected number of pivot steps of at most $(d+1)D(n, d+1, \sigma)$.

The shadow bound with the current best dependence on $\sigma$ comes from [HLZ23] and states that

$$D(n, d, \sigma) \le O\left(\frac{d^{13/4} \ln^{7/4} n}{\sigma^{3/2}} + d^{19/4} \ln^{5/2} n\right). \quad (1)$$
The same paper also proved the first non-trivial lower bound, stating that

$$D(4d - 13, d, \sigma) \geq \Omega\left(\min\left(2^d, \frac{1}{\sqrt{d\sigma\sqrt{\log d}}}\right)\right)$$

by constructing explicit data $\bar{A}, c, c'$, assuming that $d \geq 5$. From a computational experiment they conjecture that their construction might have smoothed shadow sizes as large as $\sigma^{-3/4}/\text{poly}(d)$. In all these works, the complexity of the algorithms is reduced in a black box manner to shadow bounds of smoothed unit LP, i.e., LPs of the form $(\bar{A} + \hat{A})x \leq 1$.

## 1.1 Our results

Our main contribution is a substantially improved shadow bound presented below. An overview about our and previous upper and lower bounds are summarized in Table 1.

<table><caption>Table 1: Bounds of expected number of pivots in previous literature, assuming $d \geq 3$. Logarithmic factors are simplified. The lower bound of [Bor87] holds in the smoothed models as well.</caption><thead><tr><th></th><th>Expected number of vertices</th><th>Model</th></tr></thead><tbody><tr><td>Borgwardt</td><td>Θ(d<sup>3/2</sup>√log n)</td><td>Average-case, Gaussian</td></tr><tr><td>Spielman, Teng'04</td><td>O(σ<sup>-6</sup>d<sup>3</sup>n + d<sup>6</sup>n log<sup>3</sup> n)</td><td>D(n, d, σ)</td></tr><tr><td>Deshpande, Spielman'05</td><td>O(σ<sup>-2</sup>dn<sup>2</sup> log n + d<sup>2</sup>n<sup>2</sup> log<sup>2</sup> n)</td><td>D(n, d, σ)</td></tr><tr><td>Vershynin'09</td><td>O(σ<sup>-4</sup>d<sup>3</sup> + d<sup>5</sup> log<sup>2</sup> n)</td><td>D(n, d, σ)</td></tr><tr><td>Dadush, Huiberts'18</td><td>O(σ<sup>-2</sup>d<sup>2</sup>√log n + d<sup>3</sup> log<sup>1.5</sup> n)</td><td>D(n, d, σ)</td></tr><tr><td>Huiberts, Lee, Zhang'23</td><td>O(σ<sup>-3/2</sup>d<sup>13/4</sup> log<sup>7/4</sup> n + d<sup>19/4</sup> log<sup>13/4</sup> n)</td><td>D(n, d, σ)</td></tr><tr><td>This paper</td><td>O(σ<sup>-1/2</sup>d<sup>11/4</sup> log(n)<sup>7/4</sup> + d<sup>3</sup> log(n)<sup>2</sup>)</td><td>R(n, d, σ)</td></tr><tr><td>Huiberts, Lee, Zhang'23</td><td>Ω(min(1/√σd√log d, 2<sup>d</sup>))</td><td>D(4d - 13, d, σ)</td></tr><tr><td>This paper</td><td>Ω(√d/√σ√ln(4/σ))</td><td>R(⌊(4/σ)<sup>d</sup>⌋, d, σ)</td></tr></tbody></table>

We provide a novel three-phase shadow-vertex simplex algorithm that relies on a new quantity that we call the semi-random shadow size $R(n, d, \sigma)$. We improve the algorithmic reduction, obtaining an algorithm whose running time is $O(R(n, d, \min\{\sigma, 1/\sqrt{d\ln n}, 1/d^{3/2}\log d\}))$, where $R(n, d, \sigma)$ is defined as

$$R(n, d, \sigma) = \max_{\bar{A}, \bar{b}, c} \mathbb{E}_{\bar{A}, \bar{b}, Z} \left[ \text{vertices} \left( \pi_{\text{span}(c, Z)}\left(\{x : (\bar{A} + \hat{A})x \le \bar{b} + \hat{b}\}\right) \right) \right].$$

Here, $\bar{A}, \bar{b}$ are again chosen such that the rows of $(\bar{A}, \bar{b})$ each have norm at most 1, $c \in \mathbb{S}^{d-1}$ is a unit vector, $\hat{A}, \hat{b}$ have independent entries that are Gaussian distributed with mean 0 and standard deviation $\sigma$, and $Z \in \mathbb{R}^d$ is independently sampled from any spherically symmetric distribution. This quantity is used to bound the number of pivot steps taken by the shadow vertex simplex method when moving, on the set $\{x : (\bar{A} + \hat{A})x \le \bar{b} + \hat{b}\}$, from the maximizer of a fixed objective $c$ to the maximizer of randomly sampled objective $Z$ (or the other way around).

Having our algorithm be able to sample $Z$ at random is the key algorithmic improvement which allows us to prove stronger bounds than was possible using $D(n, d, \sigma)$. Specifically we find

$$R(n, d, \sigma) \leq O\left(\sqrt{\sigma^{-1}\sqrt{d^{11}\log(n)^7}} + d^3 \log(n)^2\right).$$

Notably, this upper bound is lower than the conjectured $\sigma^{-3/4}$ lower bound of [HLZ23] for the fixed-plane shadow size $D(n, d, \sigma)$. In terms of the exponent on $\sigma$ this is the best that a shadow size bound can be,
as we demonstrate in Section 5 with a nearly-matching lower bound of

$$ \frac{\sqrt{d-1}}{96\sqrt{\sigma\sqrt{\ln(4/\sigma)}}} \le R(\lfloor(4/\sigma)^d\rfloor, d, \sigma). $$

In our proofs, we overcome a number of key challenges which have featured prominently in previous smoothed analyses of the simplex method. The main challenge is to ensure that the (previously deterministically chosen) objectives are sufficiently enough un-aligned faces of the feasible set of dimension 2 or higher. Previously, guarantees were obtained using only the randomness in the Gaussian noise added to the constraint data, in two steps. In the first step, one proves that a typical basis visited by the algorithm is relatively well-conditioned. In the second step, one proves that when a well-conditioned basis is visited, the shadow plane is not too close to any 2-dimensional face of its normal cone. Both these steps require the use of the noise in the constraint data, which entails that both steps lose a factor at least $\sigma^{-1/2}$ in these steps. Our analysis avoids this two-step procedure by incorporating randomness in the algorithm. Our simplex method is based on a semi-random shadow plane which is the linear span of the objective c and a randomly sampled objective Z. Compared to the analysis of [HLZ23], this improves our bound by a factor $\sigma^{-1}$.

More detail on the techniques used to prove the upper bound can be found in Section 1.3.

## 1.2 Related Work

The semi-random shadow vertex method used in this paper is a simplified version of that of [DH16]. They give a simplex method which uses an expected number of $O(\frac{d^2}{\delta}\ln(d/\delta))$ pivot steps, where $\delta$ is a parameter of the constraint matrix which measures the curvature of the feasible region. Their work improves over a weaker result that used “less random” shadows [BR13].

The shadow size for polyhedra all whose vertices are integral was studied in [Bla+24; Bla23; BC24], the last of which studies uniformly random planes. Semi-random shadow planes were also used in a different context to obtain a weakly polynomial-time “simplex-like” algorithm for LP in [KS06].

Shadow bounds for random objectives were previously used by [NSS22] in order to derive results similar to diameter bounds for smoothed polyhedra. Specifically they proved that with high probability there exists a large subset of vertices (according to some specific measure) which has small diameter. Here the random objectives were sampled from some non-uniform distribution, and the sizes of the resulting shadows were bounded using the shadow bound of [DH20].

In this paper we make use of a notion of vertices being “well-separated” from each other. That assumption was pioneered in a line of work starting with [KM11]. Different from work in the smoothed analysis paradigm, in [KM11] the data is deterministic, the pivot rule is that of the most negative reduced cost, and progress is measured with respect to the objective value. We show that the well-separatedness of [KM11] is locally similar to the polar concept of *vertex-facet distance* of [HLZ23]. By simultaneously generalizing both, we are able to use proof techniques borrowed from both lines of work as part of our proofs.

## 1.3 Proof Overview

### 1.3.1 Upper bound

The main hurdle of a smoothed analysis of the shadow vertex simplex method is to find techniques allowing for an efficient translation of progress measure on the polyhedron P induced by the LP into progress measure on its 2-dimensional shadow polygon Q. In the following we will outline our new strategy for constructing a progress measure which we will refer to as “separation” and illustrate how this form of separation enables us to derive our new upper bounds.

Our main algorithmic improvement is that we avoid that the shadow plane is likely to be aligned with the smoothed polyhedron P which has been addressed to ever since the very first smoothed analysis of the shadow vertex simplex method due to Spielman and Teng [ST04] and which was a main drawback in previous smoothed analyses. We propose an analysis that is based on a semi-random shadow plane which we will explain first.

Whereas previous [ST04; DS05; Ver09; DH20; HLZ23] smoothed analyses of the shadow vertex simplex method analyzed the geometry of the polar polygon $Q \cap W$, where W denotes the shadow plane, the tractability of our argument simplifies as we remain in primal space and analyze the geometry of the primal shadow polygon. In contrast to the previous approach where the number of edges in the
polar polygon $Q \cap W$ was counted, we can omit the angular parametrization and further do not need to compare angular distances with Euclidean distances. Furthermore, our approach offers a clear way to incorporate the semi-random shadow plane into our argument.

**Random objective and semi-random shadow plane** For two vectors $c, c' \in \mathbb{R}^d$, we write $\pi_{c,c'} : \mathbb{R}^d \to \text{span}(c, c')$ for the orthogonal projection onto $\text{span}(c, c')$. Since the size of the shadow path from $Z$ to $c$ depends only on the direction $Z/\|Z\|$ and not on the norm $\|Z\|$ (see Fact 19), for the purposes of analysis we assume that $Z \in \mathbb{R}^d$ is exponentially distributed, i.e., such that for any measurable $S \subseteq \mathbb{R}^d$ it holds that $\text{Pr}[Z \in S] = \frac{1}{\text{vol}_d(\mathbb{B}_2^d)} \int_S e^{-\|z\|} \, dz$.

For our analysis we need a certain amount of randomness in the objectives with which we traverse the shadow path. If we have a slightly-random objective $c + Z/2^k$ on the shadow path that is close enough to our fixed objective $c$, we can show that there is only a constant number of pivot steps from $c + Z/2^k$ to $c$. We parametrize this closeness by some $k \ge 1$. We observe that the path from $Z$ to $c + Z/2^k$ has the same length as the path from $Z$ to $2^k c + Z$. We construct $k$ intermediate objectives $Z + 2^i c$ for $i = 0, \dots, k$ and traverse step by step the shadow path from $Z + 2^{i-1} c$ to $Z + 2^i c$ in order to get strong control over the lengths of the shadow subpaths. In Lemma 25 we will show by an argument similar to the angle bound of [ST04], that it suffices if $k$ is of order $O(d \log(n))$. This might not sound like much, but the ability to assume an amount of randomness on both objectives turns out to be crucial.

**Separation** Our progress measure consist of two components. When traversing the shadow path from $Z$ to $2^k c + Z$, we will see in Section 4.2 that for 99% of the traversed bases $I$ there exists an intermediate objective $y_I \in [Z, 2^k c + Z]$ such that $y_I^\top A_I^{-1} \ge 0.005/d =: m$ using a result of Bach, Black, Huiberts and Kafer [Bac+25]. We will call this the “good multiplier” property. This fact is independent of the noise on the constraint data and is proven using only the randomness in our random objective $Z$. The good multipliers are the ingredient that allows us to easily incorporate the randomness of our algorithm into the analysis.

At the same time, using the randomness in the perturbations on the constraint data, for at least 80% of bases $I$ on the path, the feasible solution $x_I = A_I^{-1}b_I$ has slack at least $b_j - a_j^\top x_I \ge \frac{\|x_I\|}{5000d^{3/2} \ln(n)^{3/2}} =: g\|x_I\|$ for every nonbasic constraint $j \in [n] \setminus I$. This fact is established in Section 4.3.

It will turn out that the majority of traversed bases satisfies both the “good multiplier” and “good slack” criteria from which we deduce that for these we have “good” vertex-neighbor separation in the following sense. Let’s assume for the purpose of this sketch that both properties hold for all bases on the shadow path. The machinery that allows us to pretend so is described in Section 4.4.

Any above mentioned intermediate objective $y_I \in [Z, 2^k c + Z]$, certifies large distance between $x_I$ and its closest neighbor $x_J$ as an easy computation shows us that $(y_I/\|y_I\|)^\top (x_I - x_J) = (y_I/\|y_I\|)^\top A_I^{-1} A_I (x_I - x_J) \ge (m \cdot g)\|x_I\|/\|y_I\|$. For the sake of simplicity in this proof sketch, we will consider only the case that $\|y_I\| \le O(d)$. In the full proof, $\|y_I\|$ can be exponentially large and the analysis will homogenize with respect to it as the algorithm traverses further along the shadow path from $Z$ to $2^k c + Z$.

Following the strategy proposed by Huiberts, Lee and Zhang [HLZ23], we translate this property via a case distinction in either certifying large edge lengths or large exterior angles, as we will explain in the following.

Consider two consecutive vertices of the shadow polygon $Q = \pi_{c,Z}(P)$. Without loss of generality let us call these vertices $p_1$ and $p_2$. For a number $\rho > 0$ to be decided later, we distinguish the cases whether $\|p_1 - p_2\| > \rho\|p_2\|$ or $\|p_1 - p_2\| \le \rho\|p_2\|$.

In the former case, the edge $[p_1, p_2]$ “takes up a lot of perimeter”, in the sense that out of the integral $\int_{\partial Q} \|t\|^{-1} dt$, at least $\Omega(\rho)$ of its value is contributed by the line segment $\int_{[p_1, p_2]} \|t\|^{-1} dt \ge \Omega(\rho)$. We upper bound the full integral by $O(d \log n)$, which then effectively bounds from above the number of edges for which $\|p_1 - p_2\| \ge \rho\|p_2\|$ can hold by $O(d\rho^{-1} \log n)$.

In the latter case, consider the triangle with vertices $p_1, p_2$ and $q = p_2 - y_2^\top(p_2 - p_1) \cdot y_2$ as depicted in Figure 1. Because the next vertex $p_3$ on the boundary after $[p_1, p_2]$ satisfies $y_2^\top p_3 < y_2^\top p_2$, the exterior angle $\alpha_2$ at $p_2$ is at least as large as $\angle(p_2, p_1, q)$. The right-angled triangle has a hypotenuse of length $\|p_1 - p_2\| \le \rho$ and an opposite side of length $\|p_2 - q\| \ge m \cdot g \|x_I\| / \|y_I\| =: \varepsilon \|p_2\|$, from which we derive a lower bound on the exterior angle at $p_2$ of

$$ \alpha_2 \ge \angle(p_2, p_1, q) \ge \sin(\angle(p_2, p_1, q)) \ge \varepsilon/\rho. $$

Since the sum of the exterior angles of all the vertices of $Q$ is equal to $2\pi$, that means that there can be at most $2\pi\rho/\varepsilon$ vertices with exterior angle that large.
<figure><img src="image_3.png" /><figcaption>Figure 1: Lower bounding the exterior angle at $p_2$.</figcaption></figure>

This argument shows that, under our separation assumption, every vertex must either have a long edge or a large exterior angle, hence the polygon $Q$ can only have at most $\min_{\rho>0} 2\pi\rho/\epsilon + O(d\rho^{-1}\log n)$ vertices. Choosing $\rho = \sqrt{\epsilon d \log n}$ yields an upper bound of $4\pi\sqrt{d\log(n)/\epsilon}$ vertices.

The above argument hides the issue of how we deal with the case if $\|y_I\|$ is very large as $y_I \in [2^{i-1}c + Z, 2^i c + Z]$, $i \in [k]$ can be very large. The key impact of the semi-randomness of the shadow plane is now that for $y_I \in [2^{i-1}c + Z, 2^i c + Z]$ of large norm, $i \in [k]$, the largest exterior angle that can be argued is only of order

$$ \theta_I \ge \frac{\sigma}{\text{poly}(d, \log n) \cdot \rho \cdot \|y\|} \approx \frac{\sigma}{\text{poly}(d, \log n) \cdot \rho \cdot \|2^i c + Z\|} $$

Hence, the exterior angles shrink as the objectives grow. However, the total angle to be covered between the objectives $[2^{i-1}c + Z, 2^i c + Z]$ shrinks exponentially in $i$ as well. These two factors balance out exactly, giving an upper bound on the number of pivot steps on every such segment of objectives.

**Bound** We make a distinction of four cases based on numbers $R > r > 0$, one very large and one very small, and some $\rho \in (0, 1/2]$ to be chosen later. We write $\pi_{c,Z}: \mathbb{R}^d \to \text{span}(c, Z)$ for the orthogonal projection onto $\text{span}(c, Z)$.

* The total number of bases $I \in \binom{[n]}{d}$ with $\|\pi_{c,Z}(x_I)\| > R$ is bounded per Lemma 47.

* The total number of bases $I \in \binom{[n]}{d}$ with $\|\pi_{c,Z}(x_I)\| < r$ is bounded per Lemma 49.

* The number of bases $I$ on the path from $Z$ to $c$ satisfying $\|\pi_{c,Z}(x_I)\| \in [r, R]$ and which have at least one neighbor $J$ on this path at distance $\|\pi_{c,Z}(x_I) - \pi_{c,Z}(x_J)\| \ge \rho\|\pi_{c,Z}(x_I)\|$ is at most $O(\rho^{-1}\log(R/r))$ as shown in Lemma 43.

* The bases $I$ on the path from $Z$ to $2^k c + Z$ with only close-by neighbors $\|\pi_{c,Z}(x_I) - \pi_{c,Z}(x_J)\| < \rho\|\pi_{c,Z}(x_I)\|$ are counted in Lemma 40 and Lemma 45 and there are at most $O(\rho d^{5/3}k \log(n)^{3/2})$ in expectation.

The third and fourth case are roughly analogous to the vertices with long edge lengths and the vertices with large exterior angle in the proof sketch above.

As the 2-phase shadow vertex simplex method proposed by Vershynin [Ver09] relies on the fact that the objective vectors are fixed and not randomly chosen, we need to adapt his approach and introduce the following auxiliary LPs.

### 1.3.2 Auxiliary LPs

For the smoothed objective data $A, b$, we start out by sampling a random objective vector $Z \in \mathbb{R}^d \setminus \{0\}$ from a spherically symmetric distribution and solving $\max Z^\top x$ s.t. $Ax \le 1$. We solve this first auxiliary LP by adding $d$ artificial constraints to create a starting vertex and traversing a semi-random shadow
path from that starting objective to the random objective. A number of repeated trials will be required in order to have the artificial constraints not cut off the optimal solution to the LP, see Lemma 22. At the end, this first phase results in an optimal basic feasible solution $A_I^{-1}1_I$ to this first auxiliary LP.

In the second phase, the algorithm will operate on the feasible region of a second auxiliary LP whose constraints are $Ax + (1-b)t \le 1$. We sample one more entry $Z_{d+1}$ such that the combined vector $(Z, Z_{d+1}) \in \mathbb{R}^{d+1}$ is spherically symmetrically distributed. The optimal basis of the first auxiliary LP will be a set of constraints $I$, which will be tight for an edge of this second feasible set, and this edge connects two vertices on the combined shadow path from $-e_{d+1}$ to $(Z, Z_{d+1})$ and onwards from $(Z, Z_{d+1})$ to $e_{d+1}$, where $e_{d+1}$ denotes the $(d+1)$th unit vector in $\mathbb{R}^{d+1}$. The algorithm will follow this path until it finds, on one of its traversed edges, a feasible solution satisfying equalities $x_I = A_{I'}^{-1}b_{I'}$, $I' \in \binom{[n]}{d}$ and $t = 1$, with $I' \in \binom{[n]}{d}$. This will immediately give us an optimal basic feasible solution $A_{I'}^{-1}b_{I'}$ to the linear program $\max Z^\top x$ s.t. $Ax \le b$ with random objective. For the third and final phase, the algorithm follows the shadow path from $Z$ to $c$ on the constraints $Ax \le b$ to find the optimal solution to the intended LP.

Hence, all shadow paths followed by our algorithm have at least one objective (start to finish) randomly sampled from a spherically symmetric distribution that is independent of the constraint data. We require shadow bounds in two cases, where either the right-hand side is identical to 1 or where the right-hand side is perturbed.

### 1.3.3 Lower bound

In Section 5 we construct unperturbed LP data $\bar{A}, \bar{b}, c$ for which, when the LP data is perturbed, any simplex path between the maximizer and minimizer of the objective $c$ will have at least $\frac{\sqrt{d-1}}{24\sqrt{\sigma}\sqrt{\ln(4/\sigma)}}$ steps with high probability, assuming that the number $n$ of constraints is permitted to be exponentially large $n = \lfloor(4/\sigma)^d\rfloor$. Although this result should not be thought of as indicative of real-world performance due to the high number of constraints, it does demonstrate that the dependence on $\sigma$ in Theorem 46 cannot be further decreased without increasing its dependence on $n$ from $\log(n)^{O(1)}$ to $n^{O(1/d)}$. In that sense, the upper bound described in this paper has optimal dependence on the noise parameter $\sigma$ up to poly-logarithmic factors.

The construction involves having the rows of $\bar{A}$ be a set of unit vectors that are “well-spread-out” on the sphere. In technical terms we require this set to be $\sigma$-dense: for every $\theta \in S^{d-1}$ there must be an index $i \in [n]$ such that the $i$'th row is close to $\theta$, i.e., $\|\theta - \bar{a}_i\| \le \sigma$. Taking $\bar{b} = 1$, the resulting feasible region $P = \{x : Ax \le b\}$ after perturbation will be close to the unit ball in the sense that

$$ (1 - 8\sigma\sqrt{d\ln n})\mathbb{B}_2^d \subseteq P \subseteq (1 + 16\sigma\sqrt{d\ln n})\mathbb{B}_2^d $$

with probability at least $1 - n^{-d}$. This gives the polar polytope $P^\circ = \{y \in \mathbb{R}^d : \langle y, x \rangle \le 1 \forall x \in P\}$ a similar proximity to the unit ball

$$ (1 - 16\sigma\sqrt{d\ln n})\mathbb{B}_2^d \subseteq P^\circ \subseteq (1 + 12\sigma\sqrt{d\ln n})\mathbb{B}_2^d. $$

Geometrically, it follows, using elementary calculations, that any facet of $P^\circ$ has Euclidean diameter of at most $16\sqrt{\sigma\sqrt{d\ln n}}$. Any simplex path on $P$ from the maximizer to the minimizer of any given linear objective function $c$ corresponds to a sequence of facets of $P^\circ$, and the length of this sequence can be lower bounded using geometric progress along the boundary of $P^\circ$. A similar argument connecting the primal vertex diameter and the polar facet diameter was first developed by [Bon+22] in the context of random constraint matrices. Our adaptation of this argument to the smoothed analysis context shows a new geometric perspective on their proof. For the full lower bound argument, we refer to Section 5.

## 2 Preliminaries

We write $[d] := \{1, \dots, d\}$ and $\binom{[n]}{d} := \{S \subseteq [n] : |S| = d\}$. Whenever the given dimension is clear from the context, we write 1 for the all-ones vector and $I$ for the identity matrix. The standard basis vectors are denoted by $e_1, \dots, e_d \in \mathbb{R}^d$. Let $W \subseteq \mathbb{R}^d$ be a linear subspace. Then we denote the orthogonal projection onto $W$ by $\pi_W$.

The $\ell_2$-norm is $\|x\|_2 = \sqrt{\sum_{i \in [d]} x_i^2}$ and the $\ell_\infty$-norm is $\|x\|_\infty = \max_{i \in [d]} |x_i|$ for a vector $x \in \mathbb{R}^d$. A norm without a subscript is always the $\ell_2$-norm. Given $p \ge 1, d \in \mathbb{Z}_+$, define $\mathbb{B}_p^d = \{x \in \mathbb{R}^d : \|x\|_p \le 1\}$
as the d-dimensional unit ball of $\ell_p$ norm. Further, let for $p = 2$, $\mathbb{S}^{d-1}$ denote the unit sphere in $\mathbb{R}^d$, i.e., $\mathbb{S}^{d-1} := \{x \in \mathbb{R}^d : \|x\| = 1\}$.

For sets $A, B \subseteq \mathbb{R}^d$, the distance between the two is $\text{dist}(A, B) = \inf_{a \in A, b \in B} \|a - b\|$. For a point $x \in \mathbb{R}^d$ we write $\text{dist}(x, A) = \text{dist}(A, x) = \text{dist}(A, \{x\})$. The affine hull of $d$ vectors $a_1, \dots, a_d$ is denoted as affhull($a_i : i \in [d]$) and their convex hull as $\text{conv}(a_1, \dots, a_d) = \text{conv}(a_i : i \in [d])$.

For a convex body $K \in \mathbb{R}^d$, we define $\partial K \subseteq \text{span}(K)$ as the boundary of $K$ in the linear subspace spanned by the vectors in $K$.

## 2.1 Polytopes, Cones and Fans

**Definition 1 (Polyhedron).** Let $A \in \mathbb{R}^{n \times d}$, $b \in \mathbb{R}^n$ where $n \in \mathbb{N}$. We call a convex set $Q \subset \mathbb{R}^d$ a polyhedron if it can be written as $Q = \{x \in \mathbb{R}^d : Ax \le b\}$.

**Definition 2.** Let $I \subseteq (\begin{bmatrix} n \\ d \end{bmatrix})$ index a basis, let $A_I \subseteq \mathbb{R}^{d \times d}$ and $b_I \in \mathbb{R}^d$ be the corresponding submatrix of $A$ respectively the corresponding subset of $b$ indexed by $I$ and call $x_I = A_I^{-1}b_I$ the corresponding basic solution. We say that $x_I$ and $I$ are feasible for the LP $\max c^\top x$ subject to $Ax \le b$ if it satisfies $Ax_I \le b$. We denote the set of feasible bases of the system $Ax \le b$ by $F(A, b)$.

**Definition 3.** Let $\{a_1, \dots, a_n : a_i \in \mathbb{R}^d\}$ be a set of vectors in $\mathbb{R}^d$. The cone $\text{cone}(a_1, \dots, a_n)$ generated by $a_1, \dots, a_n$ is defined as $\text{cone}(a_1, \dots, a_n) := \{x \in \mathbb{R}^d : x = \sum_{i=1}^n \lambda_i a_i\}$ for $\lambda_i \in \mathbb{R}_{\ge 0}$.

## 2.2 Probability Distributions

All probability distributions considered in this paper will admit a probability density function with respect to the Lebesgue measure.

First we look at useful properties that density functions may have and which we use throughout the paper.

**Definition 4 (L-log-Lipschitz random variable).** Given $L > 0$, we say a random variable $x \in \mathbb{R}^d$ with probability density $\mu$ is L-log-Lipschitz (or $\mu$ is L-log-Lipschitz), if for all $x, y \in \mathbb{R}^d$, we have

$$|\log(\mu(x)) - \log(\mu(y))| \le L \|x - y\|,$$

or equivalently, $\mu(x)/\mu(y) \le \exp(L\|x - y\|)$.

In the following we see an equality for the expected value of any convex function applied to any random variable.

**Lemma 5 (Jensen's inequality).** Let $X$ be a random variable and $f$ a convex function. Then we have $f(\mathbb{E}[X]) \le \mathbb{E}[f(X)]$.

**Definition 6.** Let $S \subseteq \mathbb{R}^d$. A random variable $X \in \mathbb{R}^d$ is exponentially distributed on $\mathbb{R}^d$ if

$$\text{Pr}[X \in S] = \int_S Ce^{-\|x\|} \, d\,x.$$

**Lemma 7.** The normalizing constant $C$ of the exponential distribution is $C = \frac{1}{d! \text{vol}_d(\mathbb{B}_2^d)}$. For $X$ exponentially distributed on $\mathbb{R}^d$, the $k$'th moment of $\|X\|$ is $\mathbb{E}[\|X\|^k] = \frac{(k+d-1)!}{(d-1)!}$.

*Proof.* See Appendix B. $\square$

For the exponential distribution we have the following tail bound.

**Lemma 8.** Let $X$ be exponentially distributed on $\mathbb{R}^d$. Then for any $t > 1$ we have

$$\text{Pr}[X \ge 2ed \ln t] \le t^{-d}.$$

*Proof.* See Appendix B. $\square$

The exponential distribution is 1-Lipschitz continuous.
**Definition 9 (Gaussian distribution).** The $d$-dimensional Gaussian distribution $N_d(\bar{a}, \sigma^2 I)$ with support on $\mathbb{R}^d$, mean $\bar{a} \in \mathbb{R}^d$, and standard deviation $\sigma$, is defined by the probability density function

$$ \sigma^{-d} \cdot (2\pi)^{-d/2} \cdot \exp(-\|s - \bar{a}\|^2/(2\sigma^2)) $$

at every $s \in \mathbb{R}^d$.

A useful standard property of the Gaussian distribution is the following tail bound:

**Lemma 10 (Gaussian tail bound).** Let $x \in \mathbb{R}^d$ be a random vector sampled with independent Gaussian distributed entries of mean 0 and variance $\sigma^2$. For any $t \ge 1$ and any $\theta \in \mathbb{S}^{d-1}$ where $\mathbb{S}^{d-1}$ is the unit sphere in the $d$-dimensional space, we have

$$ \Pr[\|x\| \ge t\sigma\sqrt{d}] \le \exp(-(d/2)(t-1)^2). $$

From this, we can upper-bound the maximum norm over $n$ Gaussian random vectors with mean 0 and variance $\sigma^2$ by $4\sigma\sqrt{d\log n}$ with probability at least $1 - n^{-4d}$.

**Corollary 11 (Global diameter of Gaussian random variables).** For any $n \ge 2$, let $x_1, \dots, x_n \in \mathbb{R}^d$ be random variables where each $x_i$ is independent Gaussian distributed with mean 0 and standard deviation $\sigma$. Then with probability at least $1 - n^{-d}$, $\max_{i \in [n]} \|x_i\| \le 4\sigma\sqrt{d\log n}$.

*Proof.* From Lemma 10, we have for each $i \in [n]$ that

$$ \Pr[\|x_i\| > 4\sigma\sqrt{d\log n}] \le \exp(-\frac{d(4\sqrt{\log n} - 1)^2}{2}) \le \exp(-2d\log n) \le n^{-1} \cdot n^{-d}. $$

Then the statement follows from the union bound over $i = 1, \dots, n$. $\square$

**Theorem 12 (Chernoff bound).** Let $X_1, \dots, X_n \in \{0, 1\}$ be $n$ independently distributed random variables. Let $X := \sum_{i=1}^n X_i$. Then

$$ \Pr[X = 0] \le e^{-E[X]/2}. $$

**Theorem 13 (Mass distribution of the sphere).** If $e_1$ is a fixed and arbitrary unit vector, and if $\theta \in \mathbb{S}^{d-1}$ is sampled uniformly at random from the unit sphere, then for any $\alpha > 0$ we have

$$ \Pr[|\theta^\top e_1| \le \alpha] \le \alpha\sqrt{de}. $$

Moreover, we also have a tail bound

$$ \Pr[|\theta^\top e_1| \ge t/\sqrt{d}] \le \sqrt{de} \cdot e^{-t^2/2}. $$

*Proof.* See Appendix B. $\square$

# 3 Algorithms

This section will show how to adapt the algorithmic reduction of [Ver09] such that it can be used for the semi-random shadow vertex method. Proofs of the stated lemmas can be found in [Ver09]. The full procedure will output one of following scenarios

* a vector $x \in \mathbb{R}^d$ with $Ax \le 0$, certifying *unboundedness*,

* a vector $y \in \mathbb{R}^n$ with $y^\top A < 0$, certifying *infeasibility*, or

* a basis $I \in \binom{[n]}{d}$ which is both feasible $A(A^{-1}b_I) \le b$ and optimal $c^\top A^{-1} \ge 0$.

Note that we have a rather generous definition for unboundedness: an LP can simultaneously be unbounded and infeasible, or simultaneously be unbounded and admit an optimal basic feasible solution. This flexibility we grant ourselves out of kindness and not necessity. All that follows can be adapted to work with a more restrictive definition of unboundedness. For the sake of the clarity of our argument, we proceed with this terminology.
## 3.1 Shadow vertex method

The shadow vertex method Algorithm 1 is a pivot rule for the simplex method. Let two objective vectors $y, y' \in \mathbb{R}^d$ and a feasible basis $I \in (\begin{bmatrix} n \\ d \end{bmatrix})$ optimal for $y$ be given. We want to find a basis optimal for $y'$. The shadow vertex pivot rule will prescribe pivot steps in such a manner that, throughout the algorithm's duration, the current basis is optimal for an objective $y_\lambda := \lambda y' + (1 - \lambda)y$ with $\lambda \in [0, 1]$. In the following we will describe the primal interpretation of the shadow vertex method which we summarize as Algorithm 1. In each iteration of Algorithm 1, $\lambda$ is increased according to the condition of line 9. If $\lambda$ is found to be at least 1, then our current basis is optimal for $y'$ and returned. Otherwise Algorithm 1 finds in lines 13-20 an $l \neq j$ such that the new basis $I \setminus \{l\} \cup \{j\}$ is optimal for $y_\lambda$ and repeat with increased $\lambda$. With probability 1, $l$ and $j$ are uniquely determined because the system $Ax \leq b$ is non-degenerate since the bounds $b$ are perturbed. Since $y_1 = y'$, at the end of this path the method has found an optimal basis for the objective $y'$. Algorithm 1 is called the shadow vertex method because, when the feasible set is orthogonally projected onto the two-dimensional linear subspace $(y, y')$, the vertices visited by the algorithm project onto the boundary of the projection ("shadow") $\pi_{\text{span}(y,y')}(\{x: Ax \leq b\})$ of the feasible region.

<caption>**Algorithm 1** Shadow vertex method SHADOWVERTEX(A, b, y, y', I)</caption>

1: **Input:** non-degenerate polyhedron = {$x \in \mathbb{R}^d: Ax \leq b$}
2: objective functions $y, y' \in \mathbb{R}^d$
3: feasible basis $I \subseteq [n]$, optimal for $y$
4: **Output:** basis $I \subseteq [n]$ optimal for $y'$ or unbounded
5: $i \leftarrow 0$ // Iteration counter
6: $\lambda_i \leftarrow 0$ // Shadow progress
7: **while** $\lambda_i \neq 1$ **do**
8: &nbsp;&nbsp;&nbsp;&nbsp;$i \leftarrow i + 1$
9: &nbsp;&nbsp;&nbsp;&nbsp;$\lambda_i \leftarrow$ supremum $\lambda$ such that $y_\lambda^\top A_I^{-1} \geq 0$ // Maximal $\lambda$ such that $I$ is optimal for $\lambda y' + (1 - \lambda)y$}
10: &nbsp;&nbsp;&nbsp;&nbsp;**if** $\lambda_i \geq 1$ **then**
11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**return** I // If basis is optimal for $y$, return said basis
12: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
13: &nbsp;&nbsp;&nbsp;&nbsp;$j \leftarrow j \in I$ such that $(y_\lambda^\top A_I^{-1})_j = 0$ // Pivot rule. Will be unique
14: &nbsp;&nbsp;&nbsp;&nbsp;$x_I \leftarrow A_I^{-1} b_I$
15: &nbsp;&nbsp;&nbsp;&nbsp;$s_i \leftarrow$ supremum over all $s$ such that $A(x_I - sA_I^{-1}e_j) \leq b$ // Find simplex step length $s$
16: &nbsp;&nbsp;&nbsp;&nbsp;**if** $s_i = \infty$ **then**
17: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**return** unbounded
18: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
19: &nbsp;&nbsp;&nbsp;&nbsp;$l \leftarrow l \in [n] \setminus I$ such that $a_l^\top (x_I - s_l A_I^{-1} e_j) \leq b_l$ // Ratio test. Will be unique
20: &nbsp;&nbsp;&nbsp;&nbsp;$I \leftarrow I \setminus \{l\} \cup \{j\}$
21: **end while**

**Definition 14.** We denote by $\pi_{c,c'}: \mathbb{R}^d \to \text{span}(c, c')$ the orthogonal projection onto the span of $c$ and $c'$. We call the image $\pi_{c,c'}(Q)$ of a polyhedron $Q$ under $\pi_{c,c'}$ the shadow polygon. Note that as $Q$ can be unbounded, the shadow polygon $\pi_{c,c'}(Q)$ might be unbounded.

**Definition 15.** Given a basis $I \in (\begin{bmatrix} n \\ d \end{bmatrix})$ we write the corresponding solution as $x_I = A_I^{-1} b_I$. The set $F(A, b) \subseteq (\begin{bmatrix} n \\ d \end{bmatrix})$ consists of all feasible bases, i.e., bases for which $Ax_I \leq b$.

For linearly independent $c, c' \in \mathbb{R}^d$, the subset $P(A, b, c, c') \subseteq F(A, b)$ is called shadow path from $c$ to $c'$, and consists of all bases such that $x_I$ is maximized by some $y \in [c, c']$, i.e., for which $[c, c'] \cap A_I \mathbb{R}^d \geq 0 \neq \emptyset$. The vertices $v_1, v_2$ on $P(A, b, c, c')$ maximizing $c$ or $c'$ are called endpoints.

**Definition 16.** Let $I, I' \in P(A, b, c, c')$. We say that $I'$ is a neighbor of $I$ on the shadow path if there exists an edge on the shadow polygon between $\pi_{c,c'}(x_I)$ and $\pi_{c,c'}(x_{I'})$. Note that there can be other bases $J \in P(A, b, c, c')$ which, despite having intersection $|I \cap J| = d - 1$, are not neighbors on the shadow path.

Let $N(A, b, c, c', I)$ denote the set of neighbors of $I$ on the shadow path $P(A, b, c, c')$.

**Definition 17.** A shadow path $P(A, b, c, c') \subseteq F(A, B)$ is called non-degenerate if the pre-image $\pi_{c,c'}^{-1}(\pi_{c,c'}(x_I))$ of every basic solution $x_I$ for $I \in S$ is the singleton set $\{x_I\}$.
**Fact 18 (Non-degeneracy of the shadow path).** If the matrix $A \in \mathbb{R}^{n \times d}$ has independent Gaussian-distributed entries, which are also independent of $b, c$ and $Z$, then the shadow path is non-degenerate with probability 1.

**Fact 19.** For any $A \in \mathbb{R}^{n \times d}$, $b \in \mathbb{R}^n$, $\lambda_1, \lambda_2, \lambda_3, \lambda_4 > 0$ and linearly independent $c, c' \in \mathbb{R}^d$ we have

$$ \bullet P(A, b, c, c') = P(\lambda_1 A, \lambda_2 b, \lambda_3 c, \lambda_4 c') $$

$$ \bullet P(A, b, c, c') = P(A, b, c', c). $$

**Fact 20.** Let $P(A, b, c, c')$ be a non-degenerate shadow path. Then the subgraph of the shadow polygon induced by the bases $I \in P(A, b, c, c')$ is a path in the graph-theoretical sense. If $P(A, b, c, c') \ge 2$ then for any $I \in P(A, b, c, c')$, we have $|N(A, b, c, c', I)| = 2$ except for the two endpoints where it is 1.

**Fact 21.** Let $A \in \mathbb{R}^{n \times d}$, $b \in \mathbb{R}^n$ and let $c, c' \in \mathbb{R}^d$ be linearly independent objectives. Let $P(A, b, c, c')$ be a non-degenerate shadow path. Then we have that $|P(A, b, c, y) \cap P(A, b, y, c')| \le 2$ for all $y \in [c, c']$. Moreover, if $y_1, y_2, \dots, y_k \in [c, c']$ then $\sum_{i=1}^{k-1} |P(A, b, y_i, y_{i+1})| \le |P(A, b, c, c')| + 2k$.

## 3.2 Phase 1 and the first auxiliary LP

In phase 1 we solve our first auxiliary LP. In order to construct it, we sample $Z \in \mathbb{R}^d$ with independent entries, each following a Gaussian distribution with mean 0 and standard deviation 1. The LP we will solve in this step of the algorithm is:

$$ \max Z^\top x \qquad (\text{Unit LP}) \\ Ax \le 1 $$

By construction, the all-zeroes solution is strictly feasible. We note that, of the original LP data, only the constraint matrix $A$ appears in (Unit LP). In order to obtain a feasible starting basis that is independent of the noise on $A$, we will add $d$ artificial constraints. Let $\bar{s}_1, \dots, \bar{s}_d \in \mathbb{R}^d$ be such that $\text{conv}(\bar{s}_1, \dots, \bar{s}_d)$ is a regular $d-1$-dimensional simplex, and furthermore satisfy $e_d^\top \bar{s}_i = 3$ and $\|e_d - \bar{s}_i\| = \frac{1}{10\sqrt{\ln d}}$ for each $i = 1, \dots, d$. Sample independently perturbed vectors $s_1, \dots, s_d \in \mathbb{R}^d$ with means respectively equal to $\bar{s}_1, \dots, \bar{s}_d$ and standard deviation $\sigma > 0$. Let $R \in O(d)$ denote a uniformly random rotation matrix and construct (Unit LP') as follows:

$$ \max Z^\top x \qquad (\text{Unit LP}') \\ Ax \le 1 \\ (Rs_i)^\top x \le 1 \quad \forall i = 1, \dots, d. $$

We take this construction from [Ver09] who shows the following helpful properties:

**Lemma 22.** If (Unit LP) admits an optimal solution $x^*$ then with probability at least 0.3 it satisfies $(Rs_i)^\top x^* \le 0$ for all $i = 1, \dots, d$. This probability is independent of $A$.

**Lemma 23.** Let $S \in \mathbb{R}^{d \times d}$ denote the matrix with rows $s_1, \dots, s_d$. Conditional on the rows of $A$ each having norm at most 2 then, with probability at least 0.9, independent of $A$, the basic solution $(RS)^{-1}$ is feasible and satisfies $(Re_d)^\top (RS)^{-1} \ge 0$.

The outcome of these lemmas is as follows. We can construct (Unit LP') as described, take $Re_d$ as our fixed objective and $Z$ as our random objective, and attempt to follow the shadow path starting at the constructed basis from fixed objective $Re_d$ to random objective $Z$. With constant probability this succeeds, and with constant probability this gives an optimal basic feasible solution to (Unit LP). On a failure the procedure is repeated until success. Since the success probability can be made independent of $A$, the lengths of all attempted shadow paths are identically distributed. This follows almost exactly as first described by [Ver09]. We prove in Theorem 50 that these paths have expected length $O(\sqrt{\sigma^{-1} \sqrt{d^{11} \log(n)^7}})$.

Since the smoothening of the system should not interfere with the artificial constraints forming a basic feasible solution, one needs to restrict the perturbation size $\sigma$. Dadush and Huiberts [DH20] claimed that the restriction of the perturbation size $\sigma$ suffices $\sigma \le \frac{c}{\max_{\sqrt{d} \log n, \sqrt{d} \log d} c}$ for some $c > 0$. Once again this is without loss of generality if one is willing to accept a constant additive factor independent of $\sigma$.
If any attempted shadow path finds that the feasible region of (Unit LP') is unbounded, then according to our definition so is the original LP. Thus we may simply return *unbounded* whenever this occurs.

Phase 1 ends with having found an optimal basic feasible solution to (Unit LP) with the random objective function. Having found an optimal solution to (Unit LP) for the random objective in phase 1, we can use it as input to the second auxiliary LP (Int-LP) explained in the next section.

## 3.3 Phase 2: a second auxiliary LP

In phase 2 we use the previously found basis in order to obtain a basic feasible solution on (Input LP).

Sample a $(d+1)$th coordinate $Z_{d+1} \in \mathbb{R}$ for $Z \in \mathbb{R}^d$ such that it $Z_{d+1}$ is standard Gaussian distributed number. We now think of bases $I \in \binom{[n]}{d}$ to (Unit LP) as indexing edges in the interpolation LP which has constraints

$$Ax + (1 - b)t \leq 1. \qquad (\text{Int-LP})$$

On this LP we will consider 3 different objectives: we either minimize $t$, maximize $Z^\top x + Z_{d+1}t$, or maximize $t$.

The slice of (Int-LP) where $t=0$ equals the feasible region of (Unit LP), meaning that the optimal basis $I$ from phase 1 indexes a set of constraints that is tight for some edge of (Int-LP) that passes through the $t=0$ slice. Both endpoints of this edge are part of the combined shadow path

$$P((A, (1-b)), 1, -e_{d+1}, (Z, Z_{d+1})) \cup P((A, (1-b)), 1, (Z, Z_{d+1}), e_{d+1}).$$

As such, the second phase can be started somewhere on this path and we are able to use the shadow vertex method to follow the combined shadow path in order to increase $t$. The slice of (Int-LP) where $t=1$ has a feasible region equal to the original LP, meaning that, as soon as we find a point satisfying this, we have obtained a basic feasible solution to start phase 3. Again by Theorem 50 we know that this path has length $O(\sqrt{\sigma^{-1}\sqrt{d^{11}\log(n)^7}})$.

If the shadow vertex method stops early, finding that the optimal solution to

$$\max t \\ Ax + (1 - b)t \leq 1.$$

has value strictly less than 1, then the phase 2 optimal basic feasible solution gives a certificate that the feasible set $\{x: Ax \leq b\}$ is empty. In that case the algorithm may return said certificate.

## 3.4 Phase 3: the input LP

When phase 2 found an edge of (Int-LP) that crossed the $t=1$ slice, its tight constraints give a basic feasible solution $A_I^{-1}b_I$ to (Input LP). Moreover, due to properties of the shadow vertex simplex method this basic feasible solution is optimal for the random objective $\max Z^\top x$.

Thus, in phase 3 all that remains is to follow the semi-random shadow path from $Z$ to $c$. We prove in Theorem 51 that this can be done using an expected $O(\sqrt{\sigma^{-1}\sqrt{d^{11}\log(n)^7}})$ pivot steps. This finishes the algorithmic reduction.

# 4 Semi-random shadow bound

We will prove a semi-random shadow bound in two cases: either when $b$ is perturbed as is prescribed for smoothed analysis, or when $b$ is fixed to be the all-ones vector.

Although for algorithmic purposes we were satisfied with any rotationally symmetric distribution for $Z$, the proofs in this section will have the norm $\|Z\|$ require a specific distribution as well. For that purpose, recall from Fact 19 that for any $A \in \mathbb{R}^{n \times d}$, $b \in \mathbb{R}^n$, $\lambda_1, \lambda_2 > 0$ and linearly independent $c, c' \in \mathbb{R}^d$ we have

$$P(A, b, c, c') = P(A, b, \lambda_1 c, \lambda_2 c').$$

As such, changing the norm of the random vector $Z$ has no consequences for the analysis. We will sample $Z$ to be a 1-log-Lipschitz random variable as per Definition 4.
## 4.1 Pivot steps close to the fixed objective

As the algorithm traverses the shadow path, the main analysis requires there to be a “large amount” of randomness in the objectives that are visited. This is true for the majority of the path, except when the angle between the “current objective” and the LP’s true objective is small. For that reason, we must treat this part of the shadow path separately first. The following statement is inspired by the angle bound of [ST04], but to keep this present document self-contained we give a simple proof of a similar but much weaker result. For our purposes this weaker version suffices.

**Definition 24.** (Angle) Given two nonzero vectors $s, s' \in \mathbb{R}^d$, the angle $\angle(s, s') \in [0, \pi]$ between $s$ and $s'$ is defined to be the unique number such that $\cos(\angle(s, s')) \cdot \|s\| \cdot \|s'\| = s^\top s'$.

For two sets $S, S' \subset \mathbb{R}^d$ we define $\angle(S, S') = \inf_{s \in S \setminus \{0\}} \angle(s, s')$.

**Lemma 25** (Angle bound). Let $c \in \mathbb{R}^d \setminus \{0\}$ be an objective vector. Assume that $a_1, \dots, a_n \in \mathbb{R}^d$ are independent Gaussian distributed random vectors, each with standard deviation $\sigma \le 1/4\sqrt{d \ln n}$ and $\|\mathbb{E}[a_i]\| \le 1$. Let $0 < \varepsilon \le \pi/10$. Then

$$ \Pr[\exists J \in \begin{pmatrix} [n] \\ d-1 \end{pmatrix} : \theta(c, \text{cone}(a_j : j \in J)) < \varepsilon] \le 4d \cdot n^d \cdot \frac{\varepsilon}{\sigma\sqrt{2\pi}} + n^{-d}. $$

*Proof.* Consider the event $E$ that, for every $J \in \begin{pmatrix} [n] \\ d-1 \end{pmatrix}$ and every $j \in J$, we have $\text{dist}(a_j, \text{span}(\{c\} \cup \{a_i : i \in J \setminus \{j\}\})) \ge 2d\varepsilon$. Moreover, consider the event $D$ that, for every $j \in [n]$, we have $\|a_j\| \le 2$. We first show that $E \wedge D$ implies that for all $J \in \begin{pmatrix} [n] \\ d-1 \end{pmatrix}$ we have $\angle(c, \text{cone}(a_i : i \in J)) > \varepsilon$. After that we will show that $\Pr[\neg(E \wedge D)] \le n^d \cdot \frac{\varepsilon}{\sigma\sqrt{2\pi}} + n^{-d}$.

Assume that $E$ and $D$ hold. Let $J \in \begin{pmatrix} [n] \\ d-1 \end{pmatrix}$ be arbitrary. By our assumption of $E$, for each $j \in J$ there exists some separator $y_j \in \text{span}(\{c\} \cup \{a_i : i \in J \setminus \{j\}\})^\top$ with $\|y_j\| = 1$ that certifies this distance through the inequalities $y_j^\top a_j \ge 2d\varepsilon$ and $y_j^\top a_i = 0$ for each $i \in J \setminus \{j\}$. For their sum $y = \sum_{j \in J} y_j$ we know that $y^\top a_j \ge 2d\varepsilon$ for all $j \in J$, as well as that $y^\top c = 0$. Now consider any $p \in \text{cone}(a_j : j \in J)$ that achieves $\angle(c, p) = \angle(c, \text{cone}(a_j : j \in J))$. Without loss of generality we assume $p \in \text{conv}(a_j : j \in J)$. In particular we know from the above that $y^\top p \ge 2d\varepsilon$. The triangle inequality gives us that $\|y\| \le d$. We further deduce from $D$ that $\|p\| \le \max_{j \in J} \|a_j\| \le 2$. From the definition of $\theta$ we get $\cos(\angle(y, p)) = y^\top p \cdot \|y\|^{-1} \cdot \|p\|^{-1} \ge \varepsilon$. In particular, we find that $\angle(y, p) \le \pi/2 - \varepsilon$. We know that $\angle(c, y) = \pi/2$ due to $y^\top c = 0$, and hence the triangle inequality on the sphere gives us $\angle(c, p) \ge \varepsilon$.

It remains to show that $\Pr[\neg(E \wedge D)] \le n^d \cdot \frac{\varepsilon}{\sigma\sqrt{2\pi}} + n^{-d}$. We use the union bound:

$$ \Pr[\neg(E \wedge D)] \le \Pr[\neg E] + \Pr[\neg D] \\ \le \Pr[\neg D] + \sum_{J \in \begin{pmatrix} [n] \\ d-1 \end{pmatrix}} \sum_{j \in J} \Pr[\text{dist}(a_j, \text{span}(a_i : i \in J \setminus \{j\})) \le 2d\varepsilon]. $$

Since $\sigma \le 1/(4\sqrt{d \ln n})$ and $\|\mathbb{E}[a_i]\| \le 1$ we know that $\|a_i\| > 2$ implies $\|a_i - \mathbb{E}[a_i]\| > 4\sigma\sqrt{d \ln n}$, so Corollary 11 gives that $\Pr[\neg D] \le n^{-d}$. The double summation has $\begin{pmatrix} n \\ d-1 \end{pmatrix} \cdot (d-1) \le n^d$ terms in total, so in the remainder we need only upper bound the summand uniformly. For that purpose, let $J \in \begin{pmatrix} [n] \\ d-1 \end{pmatrix}$ and $j \in J$ be arbitrary. We may as well consider $V := \text{span}(\{c\} \cup \{a_i : i \in J \setminus \{j\}\})$ to be fixed. Write $y_j \in \mathbb{S}^{d-1}$ to be one of the two unit normal vectors to this linear subspace $V$. We are interested in the distance $\text{dist}(a_j, V) = |y_j^\top a_j|$.

Note that $V$ depends only on the values of $a_i$ for $i \in J \setminus \{j\}$, and as such $y_j$ is independent of $a_j$. That makes the inner product $y_j^\top a_j$ follow a Gaussian distribution with mean $y_j^\top \mathbb{E}[a_j]$ and standard deviation $\sigma$. The probability density function of this random variable is uniformly upper bounded by $\frac{1}{\sigma\sqrt{2\pi}}$, and hence the probability that it is contained in an interval of length $2d\varepsilon$ is at most

$$ \Pr[\text{dist}(a_j, V) < 2d\varepsilon] = \Pr[y_j^\top a_j \in (-2d\varepsilon, 2d\varepsilon)] \le \frac{4d\varepsilon}{\sigma\sqrt{2\pi}}. $$

The union bound over all choices for $J \in \begin{pmatrix} [n] \\ d-1 \end{pmatrix}$ and $j \in J$ closes out the proof. $\square$

On order to upper bound the number of pivot steps between objectives with small angle between them on the total shadow path, we need a slightly different characterization, captured by the following lemma.
**Lemma 26.** Let $c \in \mathbb{S}^{d-1}$ be a fixed objective, and let $Z \in \mathbb{R}^d$ be a random objective that is linearly independent of $c$ and satisfies $\mathrm{Pr}[\|Z\| \ge t] \le n^{-d}$ for some $t > 1$. Assume $b \in \mathbb{R}^n$ is arbitrary, and that $a_1, \dots, a_n$ are independent Gaussian distributed random vectors each with standard deviation $n^{-2d} \le \sigma \le 1/4\sqrt{d\ln n}$ and $\|\mathrm{E}[a_i]\| \le 1$. Write $k = 5d[\log_2(\mathrm{E}[nt])]$. The expected length of the shadow path between the objective and a perturbed objective satisfies

$$ \mathrm{E}[|P(A, b, 2^k c + Z, c)|] \le 7. $$

*Proof.* In the event that $\|Z\| \ge t$ we count at most $\binom{n}{d}$ distinct bases. Since $\mathrm{Pr}[\|Z\| \ge t] \le n^{-d}$, the expected number of pivot steps incurred by this situation is at most 1. For that reason, we will for the remainder of this proof only consider the case $\|Z\| < t$.

We calculate $2^k \ge t \cdot n^{5d} \ge \frac{2dt \cdot n^{2d}}{\sigma}$. Note that $\angle(2^k c + Z, c) = \angle(2^k c + Z, 2^k c)$ and consider the triangle $\triangle(0, 2^k c + Z, 2^k c)$. Let us abbreviate its vertices by $a = 2^k c + Z$ and $b = 2^k c$, so that our triangle is $\triangle(0, a, b)$. The assumption on $k$ gives that $\|2^k c\| \ge \frac{2d\ln n}{\sigma} > 2\|Z\|$ and with the triangle inequality we find that the edge $[a, b]$ has the shortest length of the three.

We recall the law of sines to derive

$$ \frac{\sin(\angle(a, b))}{\|a - b\|} = \frac{\sin(\angle(0 - a, b - a))}{\|b\|} \le \frac{1}{\|b\|} = \frac{1}{2^k} \le \frac{\sigma\sqrt{2\pi}}{2dt \cdot n^{2d}} \le \frac{\sigma\sqrt{2\pi}}{2d \cdot \|Z\| \cdot n^{2d}}. $$

This gives an upper bound on the sine of our desired angle as $\|a - b\| = \|Z\|$. To relate this to the angle itself, note that the shortest edge of a triangle is opposite of the smallest angle, which gives us that $\angle(a, b) \le \pi/3$. For any $\theta \in [0, \pi/3]$ one has $\sin(\theta) > 0.8\theta$, so in particular

$$ \angle(a, b) \le \frac{5}{4} \sin(\angle(a, b)) \le \frac{5\sigma\sqrt{2\pi}}{4 \cdot 2d \cdot n^{2d}}. $$

As such, our two objectives $2^k c + Z$ and $c$ have an angle at most $\frac{5\sigma\sqrt{2\pi}}{4\cdot 2d \cdot n^{2d}}$ between them. If $|P(A, b, 2^k c + Z, c)| \ge 2$, i.e., if there was a pivot step taken between the two objectives, then that implies there is a basis $I \in P(A, b, 2^k c + Z, c)$ such that $A_I^{-1}c \ge 0$ but $A_I^{-1}(2^k c + Z) \ge 0$. This implies that there is a subset $J \subset I, |J| = d-1$ and a point $p \in [2^k c + Z, c] \cap \mathrm{span}(a_j : j \in J)$. This point must satisfy $\angle(p, c) \le \angle(2^k c + Z, c) \le \frac{5\sigma\sqrt{2\pi}}{8d \cdot n^{2d}}$, implying that in fact $\angle(c, \mathrm{span}(a_j : j \in J)) \le \frac{5\sigma\sqrt{2\pi}}{8d \cdot n^{2d}}$.

Lemma 25 shows us that the probability of this happening is at most $6n^{-d}$. Counting at most $\binom{n}{d}$ pivot steps in this case, we may conclude

$$ \mathrm{E}[|P(A, b, 2^k c + Z, c)|] \le \binom{n}{d} \mathrm{Pr}[\|Z\| \ge t] + \binom{n}{d} \mathrm{Pr}[|P(A, b, 2^k c + Z, c)| > 1] \le 7. $$

□

## 4.2 Multipliers

We will give a bound on the expected number of pivot steps for most of the shadow path, i.e., the path segment $P(A, b, Z, 2^k c + Z)$. To start, we require the following theorem proven by [Bac+25]. At the moment of writing their manuscript is yet unpublished. For that reason we reproduce a verbatim proof in the appendix (Appendix A).

**Theorem 27.** Let $B \in \mathbb{R}^{d \times d}$ be an invertible matrix, every whose column has Euclidean norm at most 2, and define, for any $m \ge 0$, $C_m = \{x \in \mathbb{R}^d : B^{-1}x \ge m\}$. Suppose $c, c' \in \mathbb{R}^d$ are fixed. Let $Z \in \mathbb{R}^d$ be a random vector with 1-log-Lipschitz probability density $\mu$. Then

$$ \mathrm{Pr}[[c + Z, c' + Z] \cap C_m \neq \emptyset] \ge 0.99 \mathrm{Pr}[[c + Z, c' + Z] \cap C_0 \neq \emptyset] $$

for $m = \ln(1/0.99)/2d$.

The elements of the shadow path satisfying the property described above form a set that we will keep track of through the following definition.

**Definition 28.** Given $A \in \mathbb{R}^{n \times d}$ and $c, c' \in \mathbb{R}^d$, and a threshold $m > 0$, the set of bases with good multipliers is

$$ M(A, c, c', m) = \left\{ I \in \binom{[n]}{d} \mid \exists y \in [c, c'] \text{ s.t. } yA_I^{-1} \ge m \right\}. $$
In the language of this definition, the previous theorem says that most bases with all nonnegative multipliers $I \in M(A, c+Z, c'+Z, 0)$ will have good multipliers $I \in M(A, c+Z, c'+Z, \ln(1/0.99)/2d)$.

**Corollary 29.** For any fixed $A \in \mathbb{R}^{n \times d}$ with rows of norm at most 2 and any fixed $c, c' \in \mathbb{R}^d$, if $Z \in \mathbb{R}^d$ has a 1-log-Lipschitz probability density function then for $m = \ln(1/0.99)/2d$ we have

$$ \Pr[I \in M(A, c+Z, c'+Z, m)] \geq 0.99 \cdot \Pr[I \in M(A, c+Z, c'+Z, 0)]. $$

*Proof.* Write $C_m = \{y \in \mathbb{R}^d : A^{-\top}y \geq m\}$. We observe that

$$ \Pr[I \in M(A, c+Z, c'+Z, m)] = \Pr[\exists y \in [c+Z, c'+Z] : A_I^{-1}y \geq m] = \Pr[[c+Z, c'+Z] \cap C_m \neq \emptyset], $$

and similarly for $M(A, c+Z, c'+Z, 0)$. At this point we can directly apply Theorem 27 to the invertible matrix $A_I^\top$ and get

$$ \begin{aligned} \Pr[I \in M(A, c+Z, c'+Z, m)] &= \Pr[[c+Z, c'+Z] \cap C_m \neq \emptyset] \\ &\geq 0.99 \Pr[[c+Z, c'+Z] \cap C_0 \neq \emptyset] \\ &= \Pr[I \in M(A, c+Z, c'+Z, 0)]. \end{aligned} $$

□

## 4.3 Slack

Having good multipliers alone is not sufficient, because we want every vertex on the shadow-path to be “well-separated” from the others. Over the course of this subsection we will prove that all bases which have non-negligible probability of being feasible also have a good probability of being feasible by a good margin, i.e., the minimum non-zero slack is bounded away from 0. This subsection is based on an argument first developed in Section 5.3 (Randomized lower bound for $\delta$) of [HLZ23]. We require a few facts about the Gaussian distribution. First a technical lemma about the range in which we may treat the Gaussian distribution as having a log-Lipschitz probability density function.

**Lemma 30 (Gaussian as log-Lipschitz).** Assume $s \in \mathbb{R}$ is Gaussian distributed with variance $\sigma^2$ and denote its probability density function by $f(\cdot)$. If $t \in \mathbb{R}$, $p \in (0, 1/e]$ and $\varepsilon \in (0, \sigma\sqrt{\ln p^{-1}})$ satisfy $\Pr[s \geq t - \varepsilon] \geq p$ and $\Pr[s \leq t] \geq p$ then for any $x_1, x_2 \in [t - 4\sigma\sqrt{\ln p^{-1}}, t + 4\sigma\sqrt{\ln p^{-1}}]$ we have

$$ \frac{f(x_1)}{f(x_2)} \leq \exp\left(8\sigma^{-1}\sqrt{\ln p^{-1}} \cdot |x_1 - x_2|\right). $$

*Proof.* We first prove that $t \leq \mathbb{E}[s] + 4\sigma\sqrt{\ln p^{-1}}$. Suppose not, then we bound

$$ \Pr[s \geq t - \varepsilon] = \Pr\left[s - \mathbb{E}[s] \geq t - \mathbb{E}[s] - \varepsilon\right] \leq \Pr\left[|s - \mathbb{E}[s]| \geq 3\sigma\sqrt{\ln p^{-1}}\right] $$

Since $\sqrt{\ln p^{-1}} \geq 1$, we conclude from Lemma 10 that this last probability is strictly less than $p$, giving a contradiction. Similarly, we may prove that $t \geq \mathbb{E}[s] - 4\sigma\sqrt{\ln p^{-1}}$ by assuming its opposite and computing

$$ \Pr[s \leq t] = \Pr\left[\mathbb{E}[s] - s \geq \mathbb{E}[s] - t\right] \leq \Pr\left[|s - \mathbb{E}[s]| \geq 4\sigma\sqrt{\ln p^{-1}}\right], $$

once again leading to a contradiction by way of Lemma 10.

Recall that the probability density function of $s$ is given by $f(x) = \frac{1}{\sigma\sqrt{2\pi}}e^{-\frac{(x-\mathbb{E}[s])^2}{2\sigma^2}}$, which means that on the interval $x_1, x_2 \in [t - 4\sigma\sqrt{\ln p^{-1}}, t + 4\sigma\sqrt{\ln p^{-1}}] \subseteq [\mathbb{E}[s] - 8\sigma\sqrt{\ln p^{-1}}, \mathbb{E}[s] + 8\sigma\sqrt{\ln p^{-1}}]$ it satisfies

$$ \begin{aligned} \log(f(x_1)) - \log(f(x_2)) &= \frac{1}{2\sigma^2}((x_2 - \mathbb{E}[s])^2 - (x_1 - \mathbb{E}[s])^2) \\ &= \frac{1}{2\sigma^2}(x_2^2 - 2x_2\mathbb{E}[s] - x_1^2 + 2x_1\mathbb{E}[s]) \\ &= \frac{1}{2\sigma^2} \cdot (x_1 + x_2 - 2\mathbb{E}[s]) \cdot (x_2 - x_1) \\ &\leq 8\sigma^{-1}\sqrt{\ln p^{-1}} \cdot |x_1 - x_2|. \end{aligned} $$

This is equivalent to our desired statement.

□
With the above lemma in place, we can set out to prove the main non-trivial fact that we require of the Gaussian distribution.

**Lemma 31 (Condition-reversing interval lemma).** Suppose $s \in \mathbb{R}$ is Gaussian distributed with variance $\sigma^2$. For $t \in \mathbb{R}$, $p \in (0, 1/e]$, write $L = 8\sigma^{-1}\sqrt{\ln p^{-1}}$ and pick any $0 \le \varepsilon \le 1/L$. Assuming that $\Pr[s \ge t - \varepsilon] \ge p$ and $\Pr[s \le t] \ge p$ we have

$$ \Pr[s \ge t - \varepsilon | s \le t] \le e^3 \varepsilon L \cdot \Pr[s \ge t]. $$

*Proof.* We start by proving that $\Pr[s \in [t - \varepsilon, t]] \le e^2 \varepsilon L \cdot \Pr[s \in [t, t + 1/L]]$. In the final paragraphs of this proof we will extend this statement into the desired conclusion.

From Lemma 30 we find that $f(x_1)/f(x_2) \le L \cdot |x_1 - x_2|$ for any two points $x_1, x_2 \in [t - 4\sigma\sqrt{\ln p^{-1}}, t + 4\sigma\sqrt{\ln p^{-1}}]$. From here we can upper bound the probability in our intended left-hand side as

$$ \Pr[s \in [t - \varepsilon, t]] = \int_{t-\varepsilon}^{t} f(x) \, dx \le \int_{t-\varepsilon}^{t} f(t)e^{L|x-t|} \, dx \le e\varepsilon f(t). $$

Similarly, we may use this log-Lipschitzness property to lower bound the probability in our intended right-hand side and find

$$ \begin{aligned} \Pr[s \in [t, t + 1/L]] &= \int_{t}^{t+1/L} f(x) \, dx \\ &\ge \int_{t}^{t+1/L} f(t)e^{-L|x-t|} \, dx \\ &\ge e^{-1} f(t)L^{-1}. \end{aligned} $$

Putting these two inequalities together, we find $\Pr[s \in [t - \varepsilon, t]] \le e^2 \varepsilon L \Pr[s \in [t, t + 1/L]]$. This is the initial statement mentioned at the start of this proof. Still using the log-Lipschitzness of Lemma 30, we may observe too that

$$ \begin{aligned} \Pr[s \le t] &= \int_{-\infty}^{t} f(x) \, dx \\ &= \int_{-\infty}^{t+1/L} f(x-1/L) \, dx \\ &\ge \int_{-\infty}^{t+1/L} f(x)e^{-1} \, dx \\ &= e^{-1} \Pr[s \le t+1/L]. \end{aligned} $$

Using the above two inequalities in order to bound the numerator and the denominator, we can now prove the lemma as follows

$$ \begin{aligned} \Pr[s \ge t - \varepsilon | s \le t] &= \frac{\Pr[s \in [t - \varepsilon, t]]}{\Pr[s \le t]} \\ &\le \frac{e \Pr[s \in [t - \varepsilon, t]]}{\Pr[s \le t + 1/L]} \\ &\le \frac{e^3 \varepsilon L \cdot \Pr[s \in [t, t + 1/L]]}{\Pr[s \le t + 1/L]} \\ &= e^3 \varepsilon L \cdot \Pr[s \ge t | s \le t + 1/L] \\ &\le e^3 \varepsilon L \cdot \Pr[s \ge t]. \end{aligned} $$

In order to establish this final inequality, note that

$$ \begin{aligned} \Pr[s \ge t] &= \Pr[s > t + 1/L] + \Pr[s \ge t | s \le t + 1/L] \Pr[s \le t + 1/L] \\ &\ge \Pr[s \ge t | s \le t + 1/L] \cdot \left( \Pr[s > t + 1/L] + \Pr[s \le t + 1/L] \right) \\ &= \Pr[s \ge t | s \le t + 1/L]. \end{aligned} $$

This, finally, proves the lemma.

<figure><img src="image_4.png" /></figure>
This all leads up to a kind of anti-concentration result first described in [HLZ23] which allowed them (and will allow us) to substantially improve over what a naive union bound argument would achieve. Whereas [HLZ23] proved this for log-Lipschitz probability distributions, we obtain a similar result for the Gaussian distribution. It will be the primary tool used to establish that the non-zero slack values are bounded away from 0.

**Lemma 32 (Conditional Anti-concentration).** Suppose $s_1, \dots, s_k \in \mathbb{R}$ are independently Gaussian distributed, each with standard deviation $\sigma > 0$, and suppose $t_1, \dots, t_k \in \mathbb{R}$ are fixed. Assume $q \in (0, 1/e)$ is such that $\Pr[s_j \le t_j] \ge q$ for all $j \in [k]$. Then for any $\varepsilon > 0$ we have

$$ \Pr[\exists j \in [k] : s_j \ge t_j - \varepsilon \mid s \le t] \le q + 16e^3 \varepsilon \sigma^{-1} \ln^{3/2}(k/q). $$

*Proof.* Since we are bounding a probability, without loss of generality we assume $\varepsilon \le \frac{\sigma}{16e^3 \ln^{3/2}(k/q)}$.

Define $C = \{j \in [k] : \Pr[s_j \ge t_j - \varepsilon] \ge q/k\}$. We proceed by independence of the random variables to find

$$ \begin{aligned} \Pr[\exists j \in [k] : s_j \ge t_j - \varepsilon \mid s \le t] &\le \sum_{j \in [k]} \Pr[s_j \ge t_j - \varepsilon \mid s_j \le t_j] \\ &\le \sum_{j \in [k] \setminus C} \Pr[s_j \ge t_j - \varepsilon] + \sum_{j \in C} \Pr[s_j \ge t_j - \varepsilon \mid s_j \le t_j] \\ &\le q + \sum_{j \in C} \Pr[s_j \ge t_j - \varepsilon \mid s_j \le t_j]. \end{aligned} $$

For any $j \in C$ we know that $\Pr[s_j \ge t_j - \varepsilon] \ge q/k$. The assumption of $\Pr[s \le t] \ge q$ implies that $\Pr[s_j \le t_j] \ge q \ge q/k$, and so we satisfy the conditions of Lemma 31 and conclude

$$ \begin{aligned} \sum_{j \in C} \Pr[s_j \ge t_j - \varepsilon \mid s_j \le t_j] &\le \sum_{j \in C} 8e^3 \varepsilon \sigma^{-1} \sqrt{\ln(k/q)} \Pr[s_j \ge t_j] \\ &= 8e^3 \varepsilon \sigma^{-1} \sqrt{\ln(k/q)} \cdot \mathbb{E}[|\{j \in C : s_j \ge t_j\}|]. \end{aligned} $$

Denote this last random set as $V = \{j \in C : s_j \ge t_j\}$. Now recall the Chernoff bound (Theorem 12) which establishes that $q \le \Pr[s \le t] = \Pr[|V| = 0] \le \exp(-\mathbb{E}[|V|]/2)$. Taking all of the above together we find

$$ \begin{aligned} \Pr[\exists j \in [k] : s_j \ge t_j - \varepsilon \mid s \le t] &\le q + \sum_{j \in C} \Pr[s_j \ge t_j - \varepsilon \mid s_j \le t_j] \\ &\le q + 8e^3 \varepsilon \cdot \sigma^{-1} \sqrt{\ln(k/q)} \cdot \mathbb{E}[|V|] \\ &\le q + 16e^3 \varepsilon \ln^{3/2}(k/q), \end{aligned} $$

finishing the proof.

<figure><img src="image_5.png" /></figure>

With these technical prerequisites in place, we can now prove the main result of this subsection. Let us define the main properties of interest.

**Definition 33.** For a matrix $A \in \mathbb{R}^{n \times d}$ and vector $b \in \mathbb{R}^n$, define the set of feasible bases as

$$ F(A, b) = \{I \in \binom{[n]}{d} : A_I \text{ invertible and } Ax_I \le b\}. $$

Following that, define the set of feasible bases with relative gap $g > 0$ as

$$ G(A, b, g) = \{I \in F(A, b) : A_{[n]\setminus I} x_I \le b_{[n]\setminus I} - g \cdot \|x_I\|\}. $$

For an appropriate choice of $g$, we prove that the set $G(A, b, g)$ contains most of the set $F(A, b)$ on average.

**Theorem 34.** (Slacks are large) Let the matrix $A \in \mathbb{R}^{n \times d}$ and index set $I \in \binom{[n]}{d}$ be as follows. We assume the entries of the submatrix $A_I$ to be fixed, with $A_I$ invertible, and we assume the remainder $A_{[n]\setminus I}$ to have independent Gaussian distributed entries, each with standard deviation $\sigma > 0$. Take $b \in \mathbb{R}^n$ to be fixed. If $\Pr[I \in F(A, b)] \ge 2n^{-d}$ then

$$ 0.9 \Pr[I \in F(A, b)] \le \Pr[I \in G(A, b, \frac{\sigma}{5000d^{3/2} \ln(n)^{3/2}})] + n^{-d} $$
Proof. Compute $x_I = A_I^{-1}b_I$. For each $j \in [n] \setminus I$ define $t_j = b_j/\|x_I\|$ and $s_j = a_j^\top x_I/\|x_I\|$, thus defining two vectors $s, t \in \mathbb{R}^{n-d}$. Taking $\epsilon = \frac{\sigma}{5000d^{3/2} \ln(n)^{3/2}}$, we find that $I \in F(A, b)$ is equivalent to the system of inequalities $s \le t$. Observe that we have by assumption that for every $j \in [n] \setminus I$ we have $\Pr[s_j \le t_j] \ge \Pr[Ax_I \le b] \ge 10n^{-d}$.

Moreover, observe that $I \in G(A, b, \epsilon)$ is equivalent to the system of inequalities $s \le t - \epsilon$. Plugging in the conditional anti-concentration Lemma 32 with $q = n^{-d}$ and using that $d \ge 3$ gives that

$$ \begin{aligned} \Pr[I \notin G(A, b, \epsilon) | I \in F(A, b)] &= \Pr[s \le t - \epsilon | s \le t] \\ &\le 16e^3 \epsilon \sigma^{-1} \ln(n^{d+1})^{3/2} + n^{-d} \\ &\le 0.1 + n^{-d}. \end{aligned} $$

Equivalently, this gives $\Pr[I \in G(A, b, \epsilon) | I \in F(A, b)] \ge 0.9 - n^{-d}$. Multiplying both sides by $\Pr[I \in F(A, b)]$ and remembering that $G(A, b, \epsilon) \subset F(A, b)$ gives

$$ \Pr[I \in G(A, b, \epsilon)] \ge (0.9 - n^{-d}) \Pr[I \in F(A, b)] \ge 0.9 \Pr[I \in F(A, b)] - n^{-d}. $$

This is equivalent to the desired conclusion.

□

## 4.4 Triples

In order to get an upper bound on the size of the shadow path, we want to reason about the case where the shadow path contains a basis in $M(A, c+Z, c'+Z, m)$ and whose neighbors on the shadow path are in $G(A, b, g)$. In order to do this effectively without having to worry about non-trivial correlations, we will consider sequences of three bases on the shadow path contained in $M(A, c+Z, c'+Z, m) \cap G(A, b, g)$.

**Definition 35.** For a graph $G = (V, E)$ and $S \subseteq V$, write $T^S \subseteq G$ for the vertices $v \in S$ who have at least 2 neighbors in $S$.

If we can bound the number of such triples, then this leads to an upper bound on the shadow path length.

**Lemma 36.** Consider a fixed finite set $U$ of possible elements. Let $S \subseteq V \subseteq U$ be two random sets such that $\Pr[I \in S | I \in V] \ge p > 2/3$ for all $I \in U$. Suppose that $P = (V, E)$ is a graph on vertex set $V$, consisting of $k$ connected components, each of which is a cycle or a path. Then we have

$$ \mathbb{E}[|V|] \le \frac{2\mathbb{E}[k] + \mathbb{E}[|T^S|]}{3p-2}. $$

Proof. We denote the number of edges adjacent to a vertex $x_I$ as $\delta_G(I)$. We count the sum of the degrees $\delta_G(I)$ of vertices $I \in S$. Counting per vertex, we find a lower bound of $2|S| - 2k$ since all vertices have degree at least 2, except possibly the endpoints of connected components that are paths, i.e.,

$$ 2|S| - 2k \le \sum_{I \in S} \delta_G(I). $$

This sum counts every edge in the induced subgraph $G[S]$ twice. Every edge outside $G[S]$ counted in the sum $\sum_{I \in S} \delta(I)$ connects to a vertex in $V \setminus S$, contributing 1 to that vertex's degree. This implies that

$$ \sum_{I \in S} \delta_G(I) \le 2|E(G[S])| + \sum_{I \in V \setminus S} \delta_G(I) \le 2|E(G[S])| + 2|V \setminus S|. $$

To further upper bound this last quantity, observe that every edge in the subgraph $G[S]$ connects to two vertices in $S$. Every vertex $I \in T^S$ has degree 2 in $G[S]$, while every vertex $I \in S \setminus T^S$ has degree 0 or 1 in $G[S]$. From this we count the sum of the degrees in $G[S]$ and find that $2|E(G[S])| = \sum_{I \in S} \delta_{G[S]}(I) = 2|T^S| + |S \setminus T^S| = |S| + |T^S|$. Taking all of the above together, we find

$$ 2|S| - 2k \le |S| + |T^S| + 2|V \setminus S| \le |T^S| + 2|V| - |S|. $$

Simplifying, we get $3|S| \le 2k + |T^S| + 2|V|$. Now it is time to remember that everything is random to conclude

$$ 3p\mathbb{E}[|V|] \le 3\mathbb{E}[|S|] \le 2\mathbb{E}[k] + \mathbb{E}[|T^S|] + 2\mathbb{E}[|V|], $$

and hence we may rearrange to $\mathbb{E}[|V|] \le \frac{2\mathbb{E}[k] + \mathbb{E}[|T^S|]}{3p-2}$.

□
Regard the shadow path as a random graph on the nodes $P(A, b, c + Z, c' + Z) \subseteq \binom{[n]}{d}$, with an edge between two bases on the path if and only if they are adjacent in the shadow path. This subsection and the previous two all lead up to the following structural result:

**Theorem 37.** Let the matrix $A \in \mathbb{R}^{n \times d}$ have independent Gaussian distributed entries, each with standard deviation $\sigma \le \frac{1}{4\sqrt{d \ln n}}$. Assume furthermore that the rows of $\mathbb{E}[A]$ each have Euclidean norm at most 1. Take $b \in \mathbb{R}^n$ and $c, c' \in \mathbb{R}^d$ to be fixed. If $Z \in \mathbb{R}^d$ has a 1-log-Lipschitz probability density function then

$$ \mathbb{E}[|P(A, b, c + Z, c' + Z)|] \le 500 + 2\mathbb{E}[|T^{G(A, b, \frac{\sigma}{5000d^{3/2} \ln(n)^{3/2}}) \cap M(A, c+Z, c'+Z, \frac{\ln(1/0.99)}{2d})}|]. $$

*Proof.* Write $m = \ln(1/0.99)/2d$ and $g = \frac{\sigma}{5000d^{3/2} \ln(n)^{3/2}}$. For any $t \ge 0$, abbreviate $M(A, c + Z, c' + Z, t) = M(t)$ and $G(A, b, t) = G(t)$. Moreover, abbreviate $\mathcal{P} = P(A, b, c + Z, c' + Z)$. Recall that $I \in \mathcal{P}$ is equivalent to $I \in M(0) \cap G(0)$ and that $I \in G(0)$ is equivalent to $I \in F(A, b)$.

Define $U := \{I \in \binom{[n]}{d} : \mathrm{Pr}[I \in \mathcal{P}] \ge 100n^{-d}\}$. Note that $U$ is fixed, not random. Immediately we find that

$$ \mathbb{E}[|\mathcal{P}|] \le \mathbb{E}[|\mathcal{P} \setminus U|] + \mathbb{E}[|\mathcal{P} \cap U|] \\ \le 100 + \mathbb{E}[|\mathcal{P} \cap U|]. $$

In order to use Lemma 36, we will consider the universe $U$. Since $\mathcal{P}$ is either a cycle or a path, we find that the graph $\mathcal{P} \cap U$ has at most $\mathcal{P} \setminus U$ connected components.

For every index set $I \in U$, we will prove

$$ \mathrm{Pr}[I \in M(m) \cap G(g) | I \in \mathcal{P}] \ge 5/6. $$

This is equivalent to the assertion that

$$ \mathrm{Pr}[I \in M(m) \cap G(g)] \ge \frac{5}{6} \mathrm{Pr}[I \in M(0) \cap G(0)], $$

which we will prove. Pick $I \in U$ arbitrarily. We denote by $A_I$ the submatrix of $A$ containing only the rows indexed by $I$, and we denote by $A_{[n]\setminus I}$ the remainder of $A$. For any fixed $t \ge 0$, the event $I \in M(t)$ depends on $A_I$ and $Z$ but is independent of $A_{[n]\setminus I}$. Moreover, the event $I \in G(t)$ depends on $A_I$ and $A_{[n]\setminus I}$ but is independent of $Z$. We can change the order of integration and find that

$$ \begin{aligned} \mathrm{Pr}_{A,Z} [I \in G(0) \cap M(0)] &= \mathbb{E}_{A_I} [\mathbb{E}_{A_{[n]\setminus I}} [\mathbb{E}_Z [1[I \in G(0)] \cdot 1[I \in M(0)]]]] \\ &= \mathbb{E}_{A_I} [\mathbb{E}_{A_{[n]\setminus I}} [1[I \in G(0)]] \cdot \mathbb{E}_Z [1[I \in M(0)]]] \\ &= \mathbb{E}_{A_I} \left[ \mathrm{Pr}_{A_{[n]\setminus I}} [I \in G(0)] \cdot \mathrm{Pr}_Z [I \in M(0)] \right]. \end{aligned} \quad (2) $$

Let $E_I$ denote the event that every row of $A_I$ has Euclidean norm at most $1 + 4\sigma\sqrt{d \ln n} \le 2$. By Lemma 10 we know that $\mathrm{Pr}[\neg E_I] \le n^{-4d}$. Fix $A_I$ to be any matrix, assuming only it is invertible. If $E_I$ holds then we may use Corollary 29 to find

$$ \mathrm{Pr}_Z[I \in M(0)] \le \frac{1}{0.99} \mathrm{Pr}[I \in M(m)] = \frac{1}{0.99} \mathrm{Pr}[I \in M(m)] + 1[\neg E_I]. $$

If $E_I$ does not hold then we directly find

$$ \mathrm{Pr}_Z[I \in M(0)] \le 1 = 1[\neg E_I] \le \frac{1}{0.99} \mathrm{Pr}[I \in M(m)] + 1[\neg E_I]. $$

Thus we have an upper bound for $\mathrm{Pr}_Z[I \in M(0)]$ that always holds. Now plug this bound into (2) to find

$$ \begin{aligned} \mathrm{Pr}_{A,Z} [I \in G(0) \cap M(0)] &= \mathbb{E}_{A_I} \left[ \mathrm{Pr}_{A_{[n]\setminus I}} [I \in G(0)] \cdot \mathrm{Pr}_Z [I \in M(0)] \right] \\ &\le \mathbb{E}_{A_I} \left[ \mathrm{Pr}_{A_{[n]\setminus I}} [I \in G(0)] \cdot \left( \frac{1}{0.99} \mathrm{Pr}_Z [I \in M(m)] + 1[\neg E_I] \right) \right] \end{aligned} $$
$$
\begin{align}
&\leq \mathbb{E}_{A_I} \left[ \frac{1}{0.99} \Pr_{A_{[n]\setminus I}} [I \in G(0)] \cdot \Pr_Z[I \in M(m)] + 1[\neg E_I] \right] \nonumber \\
&\leq \frac{1}{0.99} \mathbb{E}_{A_I} \left[ \Pr_{A_{[n]\setminus I}} [I \in G(0)] \cdot \Pr_Z[I \in M(m)] \right] + n^{-d}. \tag{3}
\end{align}
$$

We now enter a new case distinction based on $A_I$. First assume that $\mathrm{Pr}_{A_{[n]\setminus I}}[I \in G(0)] > 2n^{-d}$. We know by Theorem 34 that

$$
\mathrm{Pr}_{A_{[n]\setminus I}}[I \in G(0)] \le \frac{1}{0.9} \mathrm{Pr}_{A_{[n]\setminus I}}[I \in G(g)] + \frac{1}{0.99} n^{-d} \le \frac{1}{0.9} \mathrm{Pr}_{A_{[n]\setminus I}}[I \in G(g)] + 2n^{-d}.
$$

In the alternative case we immediately find $\mathrm{Pr}_{A_{[n]\setminus I}}[I \in G(0)] \le 2n^{-d}$. Thus we have the same upper bound in both cases. Plugging this into (3), it follows that

$$
\begin{align}
\mathrm{Pr}_{A,Z} [I \in G(0) \cap M(0)] &\le \frac{1}{0.99} \mathbb{E}_{A_I} \left[ \mathrm{Pr}_{A_{[n]\setminus I}} [I \in G(0)] \cdot \mathrm{Pr}_Z[I \in M(m)] \right] + n^{-d} \nonumber \\
&\le \frac{1}{0.99} \mathbb{E}_{A_I} \left[ \left( \frac{1}{0.9} \mathrm{Pr}_{A_{[n]\setminus I}} [I \in G(g)] + 2n^{-d} \right) \cdot \mathrm{Pr}_Z[I \in M(m)] \right] + n^{-d} \nonumber \\
&\le \frac{1}{0.99 \cdot 0.9} \mathbb{E}_{A_I} \left[ \mathrm{Pr}_{A_{[n]\setminus I}} [I \in G(g)] \cdot \mathrm{Pr}_Z[I \in M(m)] \right] + 4n^{-d}. \tag{4}
\end{align}
$$

Rearranging the order of integration once more we have found that

$$
\mathrm{Pr}_{A,Z} [I \in G(0) \cap M(0)] \le \frac{1}{0.99 \cdot 0.9} \mathrm{Pr}_{A,Z} [I \in M(m) \cap G(g)] + 4n^{-d}.
$$

Now recall that $I \in U$, meaning that $\mathrm{Pr}[I \in G(0) \cap M(0)] \ge 100n^{-d}$. Using this to upper bound the last term, we find $4n^{-d} \le 0.04 \mathrm{Pr}[I \in G(0) \cap M(0)]$. As such, we can conclude with a calculator that $\mathrm{Pr}[I \in G(0) \cap M(0)] \le \frac{6}{5} \mathrm{Pr}[I \in M(m) \cap G(g)]$,

We can now use Lemma 36 with $\mathbb{E}[k] \le \mathbb{E}[[P(A, b, c + Z, c' + Z) \setminus U]] \le 100$ and $p = 5/6$ to get the result

$$
\begin{align*}
\mathbb{E}[|P|] &\le \mathbb{E}[|P \setminus U|] + \mathbb{E}[|P \cap U|] \\
&\le 100 + \frac{2\mathbb{E}[k] + \mathbb{E}[|T^{M(m)} \cap G(g) \cap U|]}{3p-2} \\
&\le 500 + 2\mathbb{E}[|T^{M(m)} \cap G(g) \cap U|] \\
&\le 500 + 2\mathbb{E}[|T^{M(m)} \cap G(g)|].
\end{align*}
$$

□

4.5 Close and far neighbors

In order to make use of Theorem 37, the remainder of this section is dedicated to giving an upper bound on $T^{M(A,c,c',m)\cap G(A,b,g)}$. From here on we use thinking of the shadow path as lying on the boundary of the shadow polygon.

Any basis in $T^{M(A,c,c',m)\cap G(A,b,g)}$ will be accounted for in one of two ways, depending on the distance to its neighbors as measured in the projection. Recall the definition of neighbor from Definition 16.

**Definition 38.** For a given matrix $A \in \mathbb{R}^{n \times d}$, a right-hand side $b \in \mathbb{R}^n$, a pair of objectives $c, c' \in \mathbb{R}^d$ and some threshold $0 < \rho \le 1/2$, we denote the set of shadow path elements at far distance from their neighbors by

$$
H(A, b, c, c', \rho) = \{ I \in P(A, b, c, c') : \forall I' \in N(A, b, c, c', I), \|\pi_{c,c'}(x_I) - \pi_{c,c'}(x_{I'})\| \ge \rho \|\pi_{c,c'}(x_I)\| \}.
$$

These subsets of the shadow paths are an important part of the argument, so we will first extend the
conclusion of Fact 21 to these sets.

**Lemma 39.** Let $A \in \mathbb{R}^{n \times d}$, $b \in \mathbb{R}^n$ and let $c, c' \in \mathbb{R}^d$ be linearly independent objectives. Let $P(A, b, c, c')$ be a non-degenerate shadow path and $\rho \in (0, 1/2]$. Then we have that $|H(A, b, c, y, \rho) \cap H(A, b, y, c', \rho)| \le 2$ for all $y \in [c, c']$. Moreover, if $y_1, y_2, \dots, y_k \in [c, c']$, then

$$
\sum_{i=1}^{k-1} |H(A, b, y_i, y_{i+1}, \rho)| \le |H(A, b, c, c', \rho)| + 2k.
$$
Proof. Since $H(A, b, y, y', \rho) \subseteq P(A, b, y, y')$ for any $\rho$, the first statement is immediate. For the second statement, we abbreviate $P(i) = P(A, b, y_i, y_{i+1})$ and $H(i) = H(A, b, y_i, y_{i+1}, \rho)$ and calculate

$$ \begin{aligned} \sum_{i=1}^{k-1} |H(i)| &= \sum_{i=1}^{k-1} |P(i)| - |P(i) \setminus H(i)| \\ &\leq |P(A, b, c, c')| + 2k - \sum_{i=1}^{k-1} |P(i) \setminus H(i)| \end{aligned} $$

using Fact 21. Next, consider any basis $I \in P(A, b, c, c')$. Either $I \in H(A, b, c, c', \rho)$, or there exists $i \in [k-1]$ such that $I \in P(i) \setminus H(i)$. This implies that

$$ |P(A, b, c, c')| \leq |H(A, b, c, c', \rho)| + \sum_{i=1}^{k-1} |P(i) \setminus H(i)|. $$

Rearranging, we find our intended conclusion of $\sum_{i=1}^{k-1} |H(i)| \leq 2k + |H(A, b, c, c', \rho)|$. $\square$

The next lemma is the main reason for introducing the sets $H(A, b, c, c')$.

**Lemma 40.** For any $A \in \mathbb{R}^{n \times d}$, any $b \in \mathbb{R}^n$, any $c, c' \in \mathbb{R}^d$ with a non-degenerate shadow path, and any $g, m > 0$, the set of bases on the shadow path with large separation satisfies, for $\rho \in (0, 1/2]$,

$$ |T^{G(A,b,g) \cap M(A,c,c',m)}| \leq |H(A, b, c, c', \rho)| + \frac{\rho \cdot \angle(c, c') \cdot \max(\|c\|, \|c'\|)}{(1 - \rho) \cdot gm} + 2. $$

Proof. The total number of $I \in T^{G(A,b,g) \cap M(A,c,c',m)}$ that satisfy $I \in H(A, b, c, c', \rho)$ is at most $|H(A, b, c, c', \rho)|$. For that reason, we need only prove that the total number of $I \in T^{G(A,b,g) \cap M(A,c,c',m)}$ satisfying $I \notin H(A, b, c, c', \rho)$ is at most $\frac{\rho \cdot \angle(c, c') \cdot \max(\|c\|, \|c'\|)}{(1-\rho)gm}$.

Let $I \in T^{G(A,b,g) \cap M(A,c,c',m)} \setminus H(A, b, c, c', I)$ and $J, J' \in N(A, b, c, c', \rho)$ be arbitrary. This implies that $I \in M(A, c, c', m)$ and $J, J' \in G(A, b, g)$. Take $y \in [c, c']$ such that $yA_I^{-1} \geq m$. Write $j$ for the unique element $I \cap J = \{j\}$. We directly compute

$$ \begin{aligned} y^\top(x_I - x_J) &= (y^\top A_I^{-1})(A_I x_I - A_I x_J) \\ &\geq m \cdot (b_I - (A_I x_J))_j \\ &\geq mg \|x_J\| \\ &\geq mg \|\pi_{c,c'}(x_J)\|, \end{aligned} $$

and similarly for $J'$. Since $I \notin H(A, b, c, c', \rho)$ we must have at least one close-by neighbor. Without loss of generality assume $J$ satisfies $\|\pi_{c,c'}(x_I - x_J)\| \leq \rho \|\pi_{c,c'}(x_I)\|$. For $J$ we can now express that $x_I$ and $x_J$ are “far-apart” as measured by the inner product with $y$, for we must have

$$ \|\pi_{c,c'}(x_J)\| \geq \|\pi_{c,c'}(x_I)\| - \|\pi_{c,c'}(x_I - x_J)\| \geq (1 - \rho)\|\pi_{c,c'}(x_I)\|, $$

implying that $y^\top x_I \geq y^\top x_J + (1 - \rho) \cdot mg \cdot \|\pi_{c,c'}(x_I)\|$.

In Figure 2, we draw the points $\pi_{c,c'}(x_I)$, $\pi_{c,c'}(x_J)$ and $\pi_{c,c'}(x_{J'})$. We find the line orthogonal to $y$ which passes through $\pi_{c,c'}(x_J)$, and draw a single additional point $Q$, which is the orthogonal projection of $\pi_{c,c'}(x_I)$ onto said line. The triangle $\triangle(\pi_{c,c'}(x_J), Q, \pi_{c,c'}(x_J))$ has a right angle at $Q$.

Let $\alpha_I$ denote the exterior angle of the shadow polygon at the vertex $\pi_{c,c'}(x_I)$, also drawn in the figure. By chasing angles we find that $\alpha_I \geq \angle(\pi_{c,c'}(x_I), \pi_{c,c'}(x_J), Q)$. This latter angle we can lower bound with its sine

$$ \angle(\pi_{c,c'}(x_I), \pi_{c,c'}(x_J), Q) \geq \sin(\angle(\pi_{c,c'}(x_I), \pi_{c,c'}(x_J), Q)) = \frac{\|\pi_{c,c'}(x_I) - Q\|}{\|\pi_{c,c'}(x_J) - \pi_{c,c'}(x_I)\|} \geq \frac{(1 - \rho)mg}{\rho\|y\|}, $$

using the lower bound on the length of the opposite edge and the upper bound on the length of the hypothenuse described in the text above, canceling the two factors of $\|\pi_{c,c'}(x_I)\|$. What we have found is that for every $I \in T^{G(A,b,g) \cap M(A,c,c',m)} \setminus H(A, b, c, c', \rho)$ we have

$$ \alpha_I \geq \frac{(1 - \rho)mg}{\rho \|y\|} \geq \frac{(1 - \rho)mg}{\rho \max(\|c\|, \|c'\|)}. $$
<figure><img src="image_6.png" /><figcaption>Figure 2: The plane span(c, c') in Lemma 40. The vector y points straight up.</figcaption></figure>

It is now that we note that, for all $I \in P(A, b, c, c')$ except the two endpoints, the exterior angles at the shadow vertices pack into the angle between the objectives. In particular, for the sum over $I$'s currently under consideration, except the endpoints, we have

$$ \sum_{\substack{I \in T^{G(A,b,g) \cap M(A,c,c',m)} \\ \text{not an endpoint}}} \frac{(1-\rho)mg}{\rho \max(\|c\|, \|c'\|)} \le \sum_{\substack{I \in P(A,b,c,c') \\ \text{not an endpoint}}} \alpha_I \le \angle(c, c'). $$

Observe that the first summand does not depend on $I$. Therefore we can divide through $\frac{(1-\rho)mg}{\rho \max(\|c\|, \|c'\|)}$ on all sides. Accounting for the possible contributions by the endpoints, we find

$$ |T^{G(A,b,g) \cap M(A,c,c',M)} \setminus H(A, b, c, c', \rho)| \le \frac{\rho \max(\|c\|, \|c'\|) \cdot \angle(c, c')}{(1-\rho)mg} + 2. $$

□

Our next immediate concern is to bound the number of bases in $H(A, b, c, c', \rho)$. For that purpose we will integrate a potential function over part of the boundary of the shadow polygon.

**Definition 41.** We define the ring with inner radius $r$ and outer radius $R$ as $D(R, r) = R\mathbb{B}_2^2 \setminus r\mathbb{B}_2^2$.

**Lemma 42.** Let $T \subseteq \mathbb{R}^2$ be a closed convex set, and let $R > r > 0$. Then we can upper bound the following integral as follows

$$ \int_{D(R,r) \cap \partial T} \|x\|^{-1} \, d\,x \le 4\pi[\log_2(R/r)]. $$

*Proof.* To start, we define for $i = 1, \dots, l = \lceil \log_2(R/r) \rceil$ the ring $D_i := D(2^{i-1}r, 2^i r)$. Note that $\bigcup_{i=1}^l D_i \supset D(R, r)$. We break up the large integral into smaller parts as

$$ \int_{D(R,r) \cap \partial T} \|x\|^{-1} \, d\,x \le \sum_{i=1}^{l} \int_{D_i \cap \partial T} \|x\|^{-1} \, d\,x. \quad (5) $$

For each $i = 1, \dots, l$ we know that $x \in D_i$ implies an upper bound on the integrand $\|x\|^{-1} \le \frac{1}{r^{2i-1}}$. We will now upper bound the size of the integration domain. Take any point $x \in D_i \cap \partial T$. Since $x$ is on the boundary of the convex set $T$ there exists a nonzero vector $y \in \mathbb{R}^2$ such that $y^\top x = \max_{x' \in D_i \cap \partial T} y^\top x'$. This same vector $y$ demonstrates that $y^\top x = \max_{x' \in D_i \cap \partial T} y^\top x'$, and hence our point $x$ is also on the boundary of the restricted set $\text{conv}(D_i \cap \partial T)$. It follows that our integration domain satisfies the inclusion

$$ D_i \cap \partial T \subseteq \partial \text{conv}(D_i \cap \partial T). $$

We know that $\text{conv}(D_i \cap \partial T) \subseteq 2^i r \mathbb{B}_2^2$ is convex. By the monotonicity of surface area for inclusions of convex sets we find that $\int_{\partial \text{conv}(D_i \cap \partial T)} \|x\| \, d\,x \le \int_{\partial 2^i r \mathbb{B}_2^2} \|x\| \, d\,x \le 2\pi \cdot 2^i r$. Taken together, we have found that

$$ \int_{D_i \cap \partial T} \|x\|^{-1} \, d\,x \le \int_{D_i \cap \partial T} r/2^{i-1} \, d\,x \le 4\pi. $$
Summing over all values of $i = 1, \dots, \lfloor \log_2(R/r) \rfloor$ in (5) gives the result. □

With this we find an upper bound on the size of $H(A, b, c, c', \rho)$ that is independent of the objectives $c, c'$.

**Lemma 43.** For given constraint data $A \in \mathbb{R}^{n \times d}, b \in \mathbb{R}^n$, objectives $c, c' \in \mathbb{R}^d$ and threshold $\rho > 0$ we have for any $R > r > 0$ that

$$|H(A, b, c, c', \rho)| \le \frac{152 \ln(R/r)}{\rho} + |\{I \in F(A, b) : \|\pi_{c,c'}(x_I)\| \notin [r, R]\}|.$$

*Proof.* Abbreviate $S = \{I \in H(A, b, c, c', \rho) : \|\pi_{c,c'}(x_I)\| \in [r, R]\}$. It is our goal to show that $|S| \le \frac{128 \log_2(R/r)+208}{\rho}$.

For every $I \in P(A, b, c, c')$ and every $I' \in N(A, b, c, c', I)$ we abbreviate the norm $\ell_I = \|\pi_{c,c'}(x_I)\|$ and the line segment $L_{I,I'} = [\pi_{c,c'}(x_I), \pi_{c,c'}(x_{I'})]$.

Every such line segment is an edge of the shadow polygon $\pi_{c,c'}(\{x: Ax \le b\})$. Notably, every edge is found at most twice in this manner. With that knowledge and using Lemma 42, we can upper bound following the sum of integrals as

$$\sum_{I \in S} \sum_{I' \in N(A, b, c, c', I)} \int_{D(2R, r/2) \cap L_{I, I'}} \frac{1}{\|t\|} dt \le 2 \int_{D(2R, r/2) \cap \partial \pi_{c, c'}(\{x: Ax \le b\})} \frac{1}{\|t\|} dt \le 8\pi[\log_2(4R/r)].$$

Since $R > r$ we know that $8\pi[\log_2(4R/r)] \le 32 \log_2(R/r) + 52$.

Notice that if $I \in S$ then the intersection $L_{I,I'} \cap D(2\ell_I, \ell_I/2)$ contains a line segment of length at least $\rho\ell_I/2$, and on this line segment the integrand is at least $\frac{1}{2\ell_I}$. This implies that the integral on that line segment is at least $\int_{D(2R, r/2) \cap L_{I,I'}} \|t\|^{-1} dt \ge \int_{D(2\ell_I, \ell_I/2) \cap L_{I,I'}} \|t\|^{-1} dt \ge \rho/4$ and we can lower bound the sum of integrals as

$$\sum_{I \in S} \sum_{I' \in N(A, b, c, c', I)} \int_{D(2R, r/2) \cap L_{I, I'}} \frac{1}{\|t\|} dt \ge \sum_{I \in S} \sum_{I' \in N(A, b, c, c', I)} \frac{\rho}{4} \ge \frac{\rho|S|}{4}.$$

We thus learn that $|S| \le \frac{4(32 \log_2(R/r)+52)}{\rho} = \frac{128 \log_2(R/r)+208}{\rho}$. □

## 4.6 Summing over subpaths

We are almost ready to prove our key theorem for upper bounding the smoothed shadow size. The last remaining issue that needs resolving is that Lemma 40 depends linearly on the norm of the longest objective vector. The next lemma will help offset that growing factor with a proportionally shrinking angle.

**Lemma 44.** Let $c, z \in \mathbb{R}^d$ with $\|c\| = 1$. If $i \ge \lfloor \log_2(\frac{\|z\|+d}{\|c\|}) \rfloor + 2$ then $\angle(2^{i-1}c + Z, 2^i c + Z) \le \frac{5(\|z\|+d)}{2^{i+1}\|c\|}$.

*Proof.* Note that $\angle(2^{i-1}c+z, 2^i c+z) = \angle(2^i c+2z, 2^i c+z)$ and consider the triangle $\triangle(0, 2^i c+2z, 2^i c+z)$. Let us abbreviate its vertices by $a = 2^i c + 2z$ and $b = 2^i c + z$, so that our triangle is $\triangle(0, a, b)$. The assumption on $i$ gives that $\|z\| + d \le \|2^{i-1}c\|/2$. By the triangle inequality we find that the edge $[a, b]$ has the shortest length of the three.

We recall the law of sines to derive

$$\frac{\sin(\angle(a, b))}{\|a - b\|} = \frac{\sin(\angle(0 - a, b - a))}{\|b\|} \le \frac{1}{\|b\|} \le \frac{1}{2^{i-1}\|c\|}.$$

This gives an upper bound $\sin(\angle(a, b)) \le \frac{\|z\|+d}{2^{i-1}\|c\|}$ on the sine of our desired angle. To relate this to the angle itself, note that the shortest edge of a triangle is opposite of the smallest angle, which gives us that $\angle(a, b) \le \pi/3$. For any $\theta \in [0, \pi/3]$ one has $\sin(\theta) > 0.8\theta$, so in particular $\angle(2^{i-1}c + z, 2^i c + z) \le \frac{5(\|z\|+d)}{2^{i+1}\|c\|}$. □

We are now able to break up a long shadow path into smaller subpaths for easier analysis. In both the above and the below lemma, there is the seemingly mysterious quantity $\|z\| + d$. For any readers who wish to make sense this summation in terms of dimensional analysis, we note that $z$ will be sampled from a probability distribution that makes $\mathbb{E}[\|z\|] \ge d$.
**Lemma 45.** Consider constraint data $A \in \mathbb{R}^{n \times d}, b \in \mathbb{R}^n$, and linearly independent objectives $z \in \mathbb{R}^d$, $c \in \mathbb{S}^{d-1}$ with a non-degenerate shadow. Consider any values $g, m > 0$ and analysis parameters $R > r > 0$ and $k \in \mathbb{N}$. Assuming $(10 \log_2(R/r) + 16)gm \le d$, we find

$$ \begin{aligned} & |T^{G(A,b,g) \cap M(A,z,2^{k_c}+z,m)}| \\ & \le 2 \sqrt{\frac{(128 \log_2(R/r) + 208)(5k+58)(\|z\| + d)}{gm}} + |\{I \in F(A,b) : \|\pi_{c,Z}(x_I)\| \notin [r, R]\}| + 4k + 2. \end{aligned} $$

*Proof.* For $y, y' \in \mathbb{R}^d$ we abbreviate $S(y, y') = T^{G(A,b,g) \cap M(A,y,y',m)}$ and we cover the set of triples by smaller segments as follows

$$ S(z, 2^k c + z) = S(z, c + z) \cup \bigcup_{i=1}^{k} S(2^{i-1}c + z, 2^i c + z). $$

For the sake of succinctness write $c^{-1} = Z$ and for each $i = 0, \dots, k$ write $c^i = 2^i c + Z$. With this notation, our task is to bound $\sum_{i=0}^k |S(c^{i-1}, c^i)|$. For each $i = 0, \dots, k$ we apply Lemma 40 and find, for some $\rho \in (0, 1/2]$ to be decided later, that

$$ \begin{aligned} & \sum_{i=0}^{k} |S(c^{i-1}, c^i)| \le 2(k+1) + \sum_{i=0}^{k} |H(A, b, c^{i-1}, c^i, \rho)| + \frac{\rho \cdot \angle(c^{i-1}, c^i) \cdot \max(\|c^{i-1}\|, \|c^i\|)}{(1-\rho) \cdot gm} \\ & \le 2(k+1) + \sum_{i=0}^{k} |H(A, b, c^{i-1}, c^i, \rho)| + \frac{2\rho \cdot \angle(c^{i-1}, c^i) \cdot (\|z\| + 2^i \|c\|)}{gm}. \end{aligned} \quad (6) $$

The sets $H(A, b, c^{i-1}, c^i, \rho)$ have pairwise overlap of at most 2 by Lemma 39, which gives with Lemma 43 that

$$ \begin{aligned} & \sum_{i=0}^{k} |H(A, b, c^{i-1}, c^i, \rho)| \le |H(A, b, c^{-1}, c^k, \rho)| + 2k \\ & \le \frac{128 \log_2(R/r) + 208}{\rho} + |\{I \in F(A, b) : \|\pi_{z,c}(x_I)\| \notin [r, R]\}| + 2k. \end{aligned} \quad (7) $$

Now for the angle terms in (6), we wish to bound $\sum_{i=0}^k \angle(c^{i-1}, c^i) \cdot (\|z\| + 2^i \|c\|)$ from above. Observe that by construction the angles sum as $\sum_{i=0}^k \|z\| \angle(c^{i-1}, c^i) = \|z\| \angle(c^{-1}, c^k)$. We now subdivide into three parts based on a threshold $h = \lceil \log_2(\frac{\|z\|+d}{\|c\|}) \rceil + 2$ as

$$ \begin{aligned} & \sum_{i=0}^{k} \angle(c^{i-1}, c^i) \cdot (\|z\| + 2^i \|c\|) = \angle(c^{-1}, c^k) \cdot \|z\| + \sum_{i=1}^{k} 2^i \angle(c^{i-1}, c^i) \cdot \|c\| \\ & \le \pi \cdot \|z\| + \sum_{i=0}^{h} 2^i \angle(c^{i-1}, c^i) \cdot \|c\| + \sum_{i=h+1}^{k} 2^i \angle(c^{i-1}, c^i) \cdot \|c\|. \end{aligned} \quad (8) $$

For the middle term, we have $i \le h$ which implies $2^i \|c\| \le 8(\|z\| + d)$ and hence the partial sum satisfies $\sum_{i=0}^h 2^i \angle(c^{i-1}, c^i) \cdot \|c\| \le 8\pi(\|z\| + d)$. For the third term we use Lemma 44 to find $\sum_{i=h+1}^k 2^i \angle(c^{i-1}, c^i) \cdot \|c\| \le \frac{5}{2}k(\|z\| + d)$. The three terms together thus sum up to

$$ \begin{aligned} & \sum_{i=0}^{k} \angle(c^{i-1}, c^i) \cdot (\|z\| + 2^i \|c\|) \le \pi \|z\| + 8\pi(\|z\| + d) + \frac{5}{2} k (\|z\| + d) \\ & \le (29 + \frac{5}{2} k) \cdot (\|z\| + d). \end{aligned} \quad (9) $$

Taking (7), (8) and (9) together we can now upper bound (6) as

$$ S(z, 2^k c + z) \le 4k + 2 + \frac{128 \log_2(R/r) + 208}{\rho} + |\{I \in F(A, b) : \|\pi_{z,c}(x_I)\| \notin [r, R]\}| + \frac{\rho(58 + 5k) \cdot (\|z\| + d)}{gm}. $$

It remains to choose $\rho \in (0, 1/2]$ so as to find the strongest upper bound, which is attained at $\rho = \sqrt{\frac{(128 \log_2(R/r) + 208) \cdot gm}{(58+5k) \cdot (\|z\|+d)}}$. The assumption $(10 \log_2(R/r) + 16)gm \le d$ ensures that this choice satisfies $\rho \le 1/2$. $\square$
We are now ready to state our smoothed complexity technical theorem, which we will apply with two different choices for b.

**Theorem 46.** Let the matrix constraint $A \in \mathbb{R}^{n \times d}$ have independent Gaussian distributed entries, each with standard deviation $\sigma \le \frac{1}{4\sqrt{d\ln n}}$, and such that the rows of $\mathbb{E}[A]$ each have norm at most 1. Let $b \in \mathbb{R}^n$, $c \in \mathbb{R}^d$ be arbitrary and fixed, as well as the analysis parameters $R > r > 0$ and $t > 0$. Assume $\ln(R/r) + 1.6 \le 250d^3 \ln(n)$. If $Z \in \mathbb{R}^d$ has a 1-log-Lipschitz probability density function that satisfies $\Pr[\|Z\| \ge t] \le n^{-d}$ and is independent of A then

$$ \mathbb{E}[|P(A, b, Z, c)|] \le O\left(\sqrt{\frac{\mathbb{E}[\|Z\| + d] \log(R/r)}{\sigma \sqrt{d^7 \log^5(nt)}}}\right) + 2\mathbb{E}[|\{I \in F(A, b) : \pi_{c,Z}(x_I) \notin [r, R]\}|]. $$

*Proof.* We may assume $\sigma > n^{-2d}$, for otherwise the upper bound exceeds $n^d$ and is trivially true. We may assume without loss of generality that $\|c\| = 1$.

Abbreviating a number of expressions, we write $k = 5d \lfloor \log_2(nt) \rfloor$ to split up the shadow path into shorter segments, take the bound on the multipliers as $m = \ln(1/0.99)/2d$ and the bound on the relative slacks as $g = \frac{\sigma}{5000d^{3/2} \ln(n)^{3/2}}$.

We have $\mathbb{E}[|P(A, b, Z, c)|] \le \mathbb{E}[|P(A, b, Z, 2^k c + Z)|] + \mathbb{E}[|P(A, b, 2^k c + Z, c)|]$. The second term is at most 7 by Lemma 26. For the first term we apply Theorem 37 to find

$$ \mathbb{E}[|P(A, b, Z, 2^k c + Z)|] \le 500 + 2\mathbb{E}[|T^{G(A,b,g) \cap M(A,Z,2^k c+Z,m)}|]. $$

Through applying Lemma 45, noting that indeed $(10 \log_2(R/r) + 16)gm \le d$, we find that

$$ \mathbb{E}[|T^{G(A,b,g) \cap M(A,Z,2^k c+Z,m)}|] \le \mathbb{E}\left[2\sqrt{\frac{(128 \log_2(R/r) + 208)(5k + 58)(\|z\| + d)}{gm}}\right] + \mathbb{E}[|\{I \in F(A, b) : \|\pi_{c,Z}(x_I)\| \notin [r, R]\}|] + 4k + 2, $$

and Jensen's inequality gives that $\mathbb{E}[\sqrt{\|Z\| + d}] \le \sqrt{\mathbb{E}[\|Z\| + d]}$. Filling in all values and noting that $t > 1$ obtains the conclusion. □

## 4.7 Norms

In this subsection we will look at basic solutions with “very small” and “very large” norms and show that they are very unlikely to occur. This will give us values for our parameter for “very large” norms is $R$ and our parameter for “very small” norms is $r$. For the former we will deduce guarantees in Lemma 47 and for the latter in Lemma 48 and Lemma 49.

**Lemma 47.** Let each row $a_i$, $i \in [n]$ of A be an independent $\sigma^2$-Gaussian random variable, and let $b \in \mathbb{R}^n$ be fixed. Then we have for any $R > 0$ that

$$ \Pr[\max_{I \in \binom{[n]}{d}} \|x_I\| \ge R \|b\|_{\infty}] \le \frac{2 \cdot d^2 n^d}{\sigma R \sqrt{2\pi}}. $$

*Proof.* Let $I \subseteq [n]$ denote the index set of a subset of rows of cardinality $d$. Let $E_I$ denote the event that $\text{dist}(a_j, \text{span}(a_i : i \in I \setminus \{j\})) \ge d/R$ holds for each $j \in I$. Note that if the matrix $A_I$ is invertible then the column of $A_I^{-1}$ corresponding to index $j \in I$ has norm exactly equal to $1/\text{dist}(a_j, \text{span}(a_i : i \in I \setminus \{j\}))$. It follows by the triangle inequality that $E_I$ implies that $x_I$ has norm at most $\|x_I\| \le \sum_{i \in I} \|(A_I^{-T})_i\| \cdot |b_i| \le R \|b_I\|_{\infty}$. Using this implication along with a union bound we find

$$ \Pr\left[\max_{I \in \binom{[n]}{d}} \|x_I\| \ge R \|b\|_{\infty}\right] \le \Pr\left[\bigvee_{I \in \binom{[n]}{d}} \neg E_I\right] \le \sum_{I \in \binom{[n]}{d}} \Pr[\neg E_I]. \quad (10) $$

It remains to show that $\Pr[\neg E_I] \le \frac{2d^2}{\sigma R \sqrt{2\pi}}$ for all $I \in \binom{[n]}{d}$. Using another union bound, it suffices if we show for each $j \in I$ that

$$ \Pr\left[\text{dist}(a_j, \text{span}(a_i : i \in I \setminus \{j\})) \le d/R\right] \le \frac{2d}{\sigma R \sqrt{2\pi}}. $$
We take the linear subspace $V = \operatorname{span}(a_i : i \in I \setminus \{j\})$ to be fixed, and take $y \in V^{\perp} \cap S^{d-1}$ to be any fixed unit normal vector. Using this notation we can write

$$ \operatorname{dist}(a_j, V) = |y^\top a_j|. $$

Note that $V$ is defined only using $a_i$ with $i \in I \setminus \{j\}$, and in particular that $y$ is independent of $a_j$. That means that, after conditioning on the values of $a_i$ for $i \in I \setminus \{j\}$, the signed distance $y^\top a_j$ is Gaussian distributed with mean $y^\top \mathbb{E}[a_j]$ and standard deviation $\sigma$. The distance can only be small if $y^\top a_j \in (-d/R, d/R)$ and hence we find

$$ \begin{aligned} \operatorname{Pr} \left[ \operatorname{dist}(a_j, V) \le d/R \right] &= \operatorname{Pr} \left[ |y^\top a_j| \le d/R \right] \\ &= \operatorname{Pr} \left[ y^\top a_j \in [-d/R, d/R] \right] \\ &\le \frac{2d}{R} \cdot \frac{1}{\sigma\sqrt{2\pi}}, \end{aligned} \quad (11) $$

using the fact that the probability density function of $y^\top a_j$ is uniformly upper bounded by $1/\sigma\sqrt{2\pi}$. Combining (10) with the union bound over all $j \in I$ and (11) proves the lemma. $\square$

**Lemma 48 (No small norms).** Let the rows $a_i$, $i \in [n]$ of A have independent Gaussian distributed entries with expectations of norm $\|\mathbb{E}[a_i]\| \le 1$ for $i = 1, \dots, n$, each with standard deviation $\sigma \le \frac{1}{4\sqrt{d \log n}}$. Let $b \in \mathbb{R}^n$ be arbitrary subject to $|b_i| \ge \varepsilon$ for all $i \in [n]$. Then we have

$$ \operatorname{Pr} \left[ \min_{I \in \binom{[n]}{d}} \|x_I\| < \varepsilon/2 \right] \le n^{-d}. $$

*Proof.* Assume that $\|a_i\| \le 2$ for all $i \in [n]$. Then for any $x \in \mathbb{R}^d$ with $\|x\| < \varepsilon/2$ it follows that $a_i^\top x \le \|a_i\| \cdot \|x\| < \varepsilon \ne b_i$. In particular this implies that $x$ cannot be obtained as $A_I^{-1} b_I$ for any $I \in \binom{[n]}{d}$ with $i \in I$. Thus if $\|a_i\| \le 2$ then any basic solution $x_I$ for $I \in \binom{[n]}{d}$ must satisfy $\|x_I\| \ge \varepsilon/2$. This implication then gives $\operatorname{Pr}[\min_{I \in \binom{[n]}{d}} \|x_I\| < \varepsilon/2] \le \operatorname{Pr}[\exists i \in [n] : \|a_i\| > 2]$.

For $a_1, \dots, a_n$ we note by the triangle inequality that $\|a_i\| > 2$ implies $\|a_i - \mathbb{E}[a_i]\| > 1$. We call on Corollary 11 to find that

$$ \begin{aligned} \operatorname{Pr}[\exists i \in [n] : \|a_i\| > 2] &\le \operatorname{Pr}[\exists i \in [n] : \|a_i - \mathbb{E}[a_i]\| > 1] \\ &\le \operatorname{Pr}[\exists i \in [n] : \|a_i - \mathbb{E}[a_i]\| > 4\sigma\sqrt{d \log n}] \le n^{-d}. \end{aligned} $$

We have thus found that $\operatorname{Pr}[\min_{I \in \binom{[n]}{d}} \|x_I\| < \varepsilon/2] \le \operatorname{Pr}[\exists i \in [n] : \|a_i\| > 2] \le n^{-d}$ as required. $\square$

**Lemma 49.** Let the rows $a_i$, $i \in [n]$ of A have independent Gaussian distributed entries with expectations of norm $\|\mathbb{E}[a_i]\| \le 1$ for $i = 1, \dots, n$, and $\sigma \le \frac{1}{4\sqrt{d \log n}}$. Let $c \in \mathbb{R}^d \setminus \{0\}$ and $b \in \mathbb{R}^n$ be fixed subject to $|b_i| > \varepsilon$ for every $i \in [n]$ and let $Z \in \mathbb{R}^d$ be distributed independently from A, b and rotationally symmetric. Then we have, for $\alpha, \varepsilon > 0$, that

$$ \operatorname{Pr} \left[ \min_{I \in \binom{[n]}{d}} \| \pi_{\operatorname{span}(c,Z)}(x_I) \| < \frac{\alpha \cdot \varepsilon}{2} \right] \le n^{-d} + \alpha n^d \cdot \sqrt{de}. $$

*Proof.* We start with a simple bound, writing

$$ \min_{I \in \binom{[n]}{d}} \| \pi_{\operatorname{span}(c,Z)}(x_I) \| \ge \min_{I \in \binom{[n]}{d}} \| x_I \| \cdot \min_{I' \in \binom{[n]}{d}} \frac{\| \pi_{\operatorname{span}(c,Z)}(x_{I'}) \|}{\| x_{I'} \|}. $$

Thus, if $\min_{I \in \binom{[n]}{d}} \|\pi_{\operatorname{span}(c,Z)}(x_I)\| < \alpha \cdot \varepsilon/2$ is small then necessarily we need at least one of $\min_{I \in \binom{[n]}{d}} \|x_I\| < \varepsilon/2$ or $\min_{I' \in \binom{[n]}{d}} \frac{\|\pi_{\operatorname{span}(c,Z)}(x_{I'})\|}{\|x_{I'}\|} < \alpha$ to be small. A union bound over these two events gives us

$$ \operatorname{Pr} \left[ \min_{I \in \binom{[n]}{d}} \| \pi_{\operatorname{span}(c,Z)}(x_I) \| \le \alpha \cdot \varepsilon \right] \le \operatorname{Pr} \left[ \min_{I \in \binom{[n]}{d}} \| x_I \| \le \varepsilon \right] + \operatorname{Pr} \left[ \min_{I' \in \binom{[n]}{d}} \frac{\| \pi_{\operatorname{span}(c,Z)}(x_{I'}) \|}{\| x_{I'} \|} \le \alpha \right]. $$

As we have proven in Lemma 48, we have $\operatorname{Pr}[\min_{I \in \binom{[n]}{d}} \|x_I\| \le \varepsilon/2] \le n^{-d}$ for the first summand. It remains to upper bound the second summand. For this, we start by observing that for any $I \in \binom{[n]}{d}$
we have $\frac{\|\pi_{\text{span}(c,Z)}(x_I)\|}{\|x_I\|} \ge \frac{|Z^\top x_I|}{\|Z\| \cdot \|x_I\|}$. This inequality implies that if the former quantity is small then the second quantity must be small. This in turn results in the inequality $\text{Pr}[\min_{I \in (\binom{[n]}{d})} \frac{\|\pi_{\text{span}(c,Z)}(x_I)\|}{\|x_I\|} \le \alpha] \le \text{Pr}[\min_{I \in (\binom{[n]}{d})} \frac{|Z^\top x_I|}{\|Z\| \cdot \|x_I\|} \le \alpha]$. To upper bound this last probability, we observe that for each $I \in (\binom{[n]}{d})$ the fraction $\frac{Z^\top x_I}{\|Z\| \cdot \|x_I\|}$ has a distribution identical to the inner product $\theta^\top e_1$ between a uniformly random unit vector $\theta \in \mathbb{S}^{d-1}$ and an arbitrarily chosen standard basis vector. Taking a union bound over all $|\binom{[n]}{d}| \le n^d$ choices of $I$, we bound

$$ \text{Pr}[\min_{I \in (\binom{[n]}{d})} \frac{|Z^\top x_I|}{\|Z\| \cdot \|x_I\|} \le \alpha] \le \sum_{I \in (\binom{[n]}{d})} \text{Pr}[\frac{|Z^\top x_I|}{\|Z\| \cdot \|x_I\|} \le \alpha] \\ \le n^d \cdot \text{Pr}[|\theta^\top e_1| \le \alpha]. $$

Using Theorem 13 to upper bound $\text{Pr}[|\theta^\top e_1| \le \alpha] \le \alpha\sqrt{de}$ we obtain the result. $\square$

## 4.8 Conclusion

We require the semi-random shadow bound for two cases, either when the entries of $b \in \mathbb{R}^n$ are all fixed to 1, or when the entries of $b$ are Gaussian distributed. For the former we will present Theorem 50 and for the latter Theorem 51.

**Theorem 50.** Let the constraint matrix $A \in \mathbb{R}^{n \times d}$ have independent Gaussian distributed entries, each with standard deviation $\sigma > 0$ and such that the rows of $E[A]$ each have norm at most 1. Let $c \in \mathbb{R}^d$ be arbitrary and fixed, as well as the analysis parameters $R > 2r > 0$. If $Z \in \mathbb{R}^d$ has a 1-log-Lipschitz probability density function that satisfies $\text{Pr}[\|Z\| \ge 2ed \ln(n)] \le n^{-d}$ and is independent of $A$, then the semi-random shadow path on $\{x : Ax \le 1\}$ has length bounded as

$$ |P(A, 1, Z, c)| \le O \left( \sqrt{\frac{1}{\sigma} \sqrt{d^{11} \log^7 n} + d^3 \log(n)^2} \right). $$

*Proof.* We distinguish three cases on the values of the standard deviation $\sigma$. If $\sigma < n^{-2d}$ the right-hand side exceeds $\binom{n}{d}$ and the result follows immediately. Thus we assume $\sigma \ge n^{-2d}$. For the second case, we further assume that $\sigma \le \frac{1}{4\sqrt{d \log n}}$ such that we can apply Theorem 46 in the following. Choose $R = n^{5d} \ge 2d^2 n^{2d}/\sigma\sqrt{2\pi}$ and $r = n^{-2d} \le (2n^d \cdot \sqrt{de})^{-1}$. We apply Theorem 46 and with these values, we obtain $\log(R/r) \le O(d \log n)$. It remains to upper bound

$$ \mathbb{E}[|\{I \in F(A, b) : \|\pi_{c,Z}(x_I)\| > R\}|] + \mathbb{E}[|\{I \in F(A, b) : \|\pi_{c,Z}(x_I)\| < r\}|]. $$

Using Lemma 47 we get $\mathbb{E}[|\{I \in F(A, b) : \|\pi_{c,Z}(x_I)\| > R\}|] \le n^d \text{Pr}[\max_{I \in (\binom{[n]}{d})} \|x_I\| > R] \le 1$. To bound the expected number of bases with small projected norms, we start similarly by

$$ \mathbb{E}[|\{I \in F(A, b) : \|\pi_{c,Z}(x_I)\| < r\}|] \le n^d \text{Pr}[\max_{I \in (\binom{[n]}{d})} \|\pi_{c,Z}(x_I)\| < r]. $$

We apply Lemma 49 with $\varepsilon = 1$ and $\alpha = (n^{2d} \cdot \sqrt{de})^{-1}$ to get $\text{Pr}[\min_{I \in (\binom{[n]}{d})} \|\pi_{c,Z}(x_I)\| < r] \le 2n^{-d}$, which finishes the argument since now $\mathbb{E}[|\{I \in F(A, b) : \pi_{c,Z}(x_I) \notin [r, R]\}|] \le 3$.

For the third case we assume $\sigma > \frac{1}{4\sqrt{d \log n}}$ and calculate $|P(A, 1, Z, c)| \le O(d^3 \log(n)^2)$ closing the proof. $\square$

**Theorem 51.** Let the constraint matrix $A \in \mathbb{R}^{n \times d}$ have independent Gaussian distributed entries, as well as the vector $b \in \mathbb{R}^n$, each with standard deviation $\sigma > 0$, and such that the rows of $E[(A, b)]$ each have norm at most 1. Let $c \in \mathbb{R}^d$ be arbitrary and fixed, as well as the analysis parameters $R > 2r > 0$. If $Z \in \mathbb{R}^d$ has a 1-log-Lipschitz probability density function that satisfies $\text{Pr}[\|Z\| \ge 2ed \ln(n)] \le n^{-d}$ and is independent of $A$, then the semi-random shadow path on $\{x : Ax \le b\}$ has length bounded as

$$ |P(A, b, Z, c)| \le O \left( \sqrt{\frac{1}{\sigma} \sqrt{d^{11} \log^7 n} + d^3 \log(n)^2} \right). $$
**Proof.** We distinguish three cases on the values of the standard deviation $\sigma$. If $\sigma < n^{-2d}$ the right-hand side exceeds $\binom{n}{d}$ and the result follows immediately. Thus we assume $\sigma \ge n^{-2d}$. For the second case, we further assume that $\sigma \le \frac{1}{4\sqrt{d\log n}}$ such that we can apply Theorem 46 in the following. From Corollary 11 it follows that with probability at most $n^{-d}$, $\|b\|_{\infty} > 1 + 4\sigma\sqrt{d\log n}$. Hence, we conclude that this scenario contributes at most 1 shadow vertex to the expectation. Thus, we assume in the following that $\|b\|_{\infty} \le 1 + 4\sigma\sqrt{d\log n}$. We choose $R = n^{5d} \ge \frac{2d^2n^{2d}}{\sigma}$ and conclude applying Lemma 47 that as before,

$$ \mathbb{E}[|\{I \in F(A, b) : \|\pi_{c,Z}(x_I)\| > 2R\}|] \le n^d (\mathrm{Pr}[\max_{I \in \binom{[n]}{d}} \|x_I\| > \|b\|_{\infty} R] + \mathrm{Pr}[\|b\|_{\infty} > 2]) \le 2. $$

For this proof we pick $r = n^{-6d} \le \frac{\sigma\sqrt{2\pi}}{n^{3d}\sqrt{de}}$. We apply Theorem 46 and with these values, getting $\log(2R/r) \le O(d\log n)$. We are thus left with the task of bounding $\mathbb{E}[|\{I \in F(A, b) : \|\pi_{c,Z}(x_I)\| < r\}|]$. Take $\varepsilon = \sigma\sqrt{2\pi n^{-d}}$ and $\alpha = (n^{2d} \cdot \sqrt{de})^{-1}$. We separately treat the scenario where there exists $i \in [n]$ with $|b_i| < \varepsilon$ and the scenario where for all $i \in [n]$ it holds that $|b_i| \ge \varepsilon$.

In the first scenario we count at most $\binom{n}{d}$ bases $I$ with $\|\pi_{c,Z}(x_I)\| < r$, and this scenario occurs with probability $\mathrm{Pr}[\exists i \in [n], |b_i| < \varepsilon] \le \frac{2\varepsilon}{\sigma\sqrt{2\pi}} < n^{-d}$. Thus this scenario contributes at most 1 to the expectation.

For the second scenario we apply Lemma 49 to learn that $\mathrm{Pr}[\min_{I \in \binom{[n]}{d}} \|\pi_{c,Z}(x_I)\| < r] \le 2n^{-d}$, finding that this contributes at most 2 to the expectation. This suffices for the theorem. For the third case we assume $\sigma > \frac{1}{4\sqrt{d\log n}}$ and calculate $|P(A, 1, Z, c)| \le O(d^3 \log(n)^2)$ closing the proof. $\square$

# 5 Lower bound

In this section we will demonstrate that the exponent for $\sigma$ in the shadow bound proved in the previous section cannot be further improved without significantly worsening the dependence on $n$.

**Definition 52.** For $\eta > 0$ and $d \in \mathbb{N}$, a set $S \subset \mathbb{S}^{d-1}$ is called $\eta$-dense if for any $x \in \mathbb{S}^{d-1}$ there exists $s \in S$ such that $\|x - s\| \le \eta$.

Dense sets have been previously studied, and in particular there are known bounds on their size for greedy constructions.

**Lemma 53** (See, e.g., [Mat02] p.314). There exists an $\eta$-dense set $S \subset \mathbb{S}^{d-1}$ with cardinality $|S| \le (4/\eta)^d$.

For our unperturbed constraint data we will use a matrix whose rows form an $\eta$-dense set. This will result in a feasible set which is “close to the unit ball”.

**Lemma 54.** Let $\{s_1, \dots, s_n\} \subset \mathbb{S}^{d-1}$ be $\eta$-dense, $\eta \le 1/8$, and let $A \in \mathbb{R}^{n \times d}$ be a matrix with rows $a_1, \dots, a_n$. Assume that for every $i \in [n]$ we have $\|a_i - s_i\| \le \eta$. Given a vector $b \in [1 - \eta, 1 + \eta]^n$, the polyhedron $\{x \in \mathbb{R}^d : Ax \le b\}$ satisfies

$$ (1 - 2\eta)\mathbb{B}_2^d \subseteq \{x \in \mathbb{R}^d : Ax \le b\} \subseteq (1 + 4\eta)\mathbb{B}_2^d. $$

**Proof.** Suppose $x \in \mathbb{R}^d$ satisfies $\|x\| \le 1 - 2\eta$. Consider any $i \in [n]$. By the triangle inequality we find $\|a_i\| \le \|s_i\| + \|a_i - s_i\| \le 1 + \eta$. By the Cauchy-Schwarz inequality we find

$$ a_i^\top x \le \|a_i\| \cdot \|x\| \le (1 + \eta)(1 - 2\eta) = 1 - \eta - 2\eta^2 \le b_i. $$

Since this inequality $a_i^\top x \le b_i$ holds for all $i \in [n]$ we conclude that any $x \in \mathbb{R}^d$ with $\|x\| \le 1 - 2\eta$ satisfies $Ax \le b$.

Now suppose $x \in \mathbb{R}^d$ satisfies $\|x\| > 1 + 4\eta$. By the $\eta$-denseness of $S$ there exists an $i \in [n]$ such that $\frac{\|x\|}{\|x\| - s_i\|} \le \eta$, and by assumption on $A$ we have $\|a_i - s_i\| \le \eta$. By the triangle inequality we know that $\frac{\|x\|}{\|x\| - a_i\|} \le 2\eta$. We use the Cauchy-Schwarz inequality to find

$$ \begin{aligned} a_i^\top x &= \|x\| - \left( \frac{x}{\|x\|} - a_i \right)^\top x \\ &\ge (1 - 2\eta)\|x\| \end{aligned} $$
$$ 
\begin{aligned}
&> (1 - 2\eta)(1 + 4\eta) \\
&= 1 + 2\eta - 8\eta^2.
\end{aligned}
$$

Assuming that $\eta \le 1/8$ gives us $a_i^\top x > 1 + \eta \ge b_i$, implying $Ax \le b$. Hence any $x \in \mathbb{R}^d$ for which $Ax \le b$ must satisfy $\|x\| \le 1 + 4\eta$. $\square$

Finally we require one more lemma to bound the diameter.

**Lemma 55.** For $d \ge 2$, let $P \subseteq \mathbb{R}^d$, $R > 0$, be a simple bounded polytope containing the origin in its interior and let

$$ P^\circ := \{y \in \mathbb{R}^n : \langle x, y \rangle \le 1, \forall x \in P\} $$

denote the polar of $P$. If every facet of $P^\circ$ has geometric diameter at most $\gamma > 0$, then for any unit-length objective vector $c \in \mathbb{S}^{d-1}$, any maximizing vertex $v^+ \in P$, and any minimizing vertex $v^- \in P$, there is no simplex path from $v^+$ to $v^-$ of length less than $(d-1)(\frac{2}{R\gamma} - 2)$.

*Proof.* Since $P$ contains the origin in its interior, we may assume that we have a minimal inequality description $P = \{x \in \mathbb{R}^d : a_j^\top x \le 1, j \in [n]\}$. Write $A \in \mathbb{R}^{n \times d}$ for the matrix with rows $a_1, \dots, a_n$. A standard result is that we have a minimal vertex description $P^\circ = \text{conv}(a_1, \dots, a_n)$. Any simplex path of length $k$ between $v^+$ and $v^-$ can be represented as a sequence $B^0, B^1, \dots, B^k \in \binom{[n]}{d}$ of feasible bases for $P$ such that $|B^{i-1} \cap B^i| = d-1$ for every $i=1, \dots, k$, and for which we have $a_j^\top v^+ = 1$ for all $j \in B^0$ and $a_j^\top v^- = 1$ for all $j \in B^k$.

Construct a sequence of row indexes of $A$ as follows: Write $\ell = \lfloor k/(d-1) \rfloor$. For every $t = 1, \dots, \ell$ let $p^t \in B^{(d-1)t} \cap B^{(d-1)(t-1)}$ be arbitrary. Note that, due to the bases being adjacent $|B^{i-1} \cap B^i| = d-1$ for all $i \in [k]$, all sets $B^{(d-1)t} \cap B^{(d-1)(t-1)}$ are non-empty, so our desired sequence of vectors exists. We will now lower bound $\ell$, which will then give a lower bound on the path length $k$.

For every $i \in [k]$, we can write $v^i = A_{B^i}^{-1} 1$ for the vertex of $P$ corresponding to the feasible basis $B^i$. The set $F^i = \text{conv}(a_j : j \in B^i)$ is a facet of the polar polytope $P^\circ$ given by the facet-defining inequality $P^\circ \subseteq \{y : \langle y, v^i \rangle \le 1\}$, hence $F^i$ has Euclidean diameter at most $\gamma$ by assumption. In particular, since $p^t, p^{t+1} \in B^{(d-1)(t+1)}$ for all $t = 1, \dots, \ell$, we must have $a_{p^t}, a_{p^{t+1}} \in F^{(d-1)(t+1)}$ and hence $\|a_{p^t} - a_{p^{t+1}}\| \le \gamma$. Since $B^0$ is a basis for $v^+$, a maximal vertex for the objective $c$, we must have $cA_{B^0}^{-1} \ge 0$. It follows that the ray $c\mathbb{R}_{\ge 0}$ intersects the facet $F^0$. The affine hull of $F^0$ can be described as affhull($F^0$) = $\{y : y^\top v^+ = 1\}$, from which we may observe that $\frac{c}{c^\top v^+} \in \text{affhull}(F^0)$. Taking the previous two points together we find that $\frac{c}{c^\top v^+} \in F^0$. A similar arguments gives that $\frac{-c}{(-c)^\top v^-} \in F^k$. Thus, we know for the start- and endpoint that

$$ \frac{c}{c^\top v^+}, a_{p^1} \in F^0, \quad \frac{-c}{(-c)^\top v^-} \in F^k. $$

For the startpoint we conclude $\|\frac{v^+}{c^\top v^+} - a_{p^1}\| \le \gamma$. For the endpoint we observe that $B^{(d-1)\ell} \cap B^k \ne \emptyset$ and take $p' \in B^\ell \cap B^k$ arbitrarily. Making use of the Euclidean diameters of $F^{(d-1)\ell}$ and $F^k$, the triangle inequality gives $\|\frac{v^+}{c^\top v^-} - a_{p^\ell}\| \le \|\frac{v^+}{c^\top v^-} - a_{p^\ell}\| + \|a_{p^\ell} - a_{p^\ell}\| \le 2\gamma$. Finally note that, by Chauchy-Schwarz, $0 < c^\top v^+ \le \|c\| \cdot \|v^+\| \le R$ and similarly $0 < (-c)^\top v^- \le R$. We can now use the triangle inequality again to find

$$ 
\begin{aligned}
\frac{2}{R} &= \frac{\|c - (-c)\|}{R} &\le \|\frac{c}{c^\top v^+} - \frac{-c}{(-c)^\top v^-}\| \\
&\le \|\frac{c}{c^\top v^+} - a_{p^1}\| + \|a_{p^\ell} - \frac{-c}{(-c)^\top v^+}\| + \sum_{t=1}^{\ell-1} \|a_{p^t} - a_{p^{t+1}}\| \\
&\le (\ell + 2)\gamma.
\end{aligned}
$$

Hence we find that $k/(d-1) \ge \lfloor k/(d-1) \rfloor = \ell \ge \frac{2}{R\gamma} - 2$ and $k \ge (d-1)(\frac{2}{R\gamma} - 2)$. This implies that the sequence of feasible bases must have length at least $(d-1)(\frac{2}{R\gamma} - 2)$. The sequence was arbitrary, so we find that any simplex path connecting $v^+$ and $v^-$ is at least this long. $\square$

With these lemmas in place, we can prove our high-probability lower bound on the diameter of the polyhedron after perturbing.
**Theorem 56.** Given $d \ge 2$ and $\sigma > 0$ satisfying $\sigma\sqrt{\ln(4/\sigma)} \le \frac{1}{32d}$, take $n = \lfloor(4/\sigma)^d\rfloor$. There exist $\bar{A} \in \mathbb{R}^{n \times d}$, and $\bar{b} \in \mathbb{R}^n$ such that the following holds. The rows of the combined matrix $(\bar{A}, \bar{b})$ each have norm at most 1. If $A, b$ have their entries independently Gaussian distributed with variance $\sigma^2$ and expectation $\mathbb{E}[A] = \bar{A}, \mathbb{E}[b] = \bar{b}$, then the combinatorial diameter of the polyhedron $\{x : Ax \le b\}$ satisfies

$$ \mathrm{Pr} \left[ \mathrm{diam}(\{x : Ax \le b\}) \ge \frac{(d-1)^{1/2}}{24\sqrt{\sigma\sqrt{\ln(4/\sigma)}}} \right] \ge 1 - n^{-d}. $$

Moreover, with probability at least $1 - n^{-d}$, for any fixed nonzero objective vector $c \in \mathbb{R}^d$, its maximizing and minimizing vertices attain this lower bound on the combinatorial distance.

*Proof.* We pick $S \subset \mathbb{S}^{d-1}$ to be $\sigma$-dense with $|S| = \lfloor(4/\sigma)^d\rfloor$ as demonstrated by Lemma 53. We set $n = |S|$ and let $\bar{A} \in \mathbb{R}^{n \times d}$ be formed by having the elements of $S$ as its rows. We set $\bar{b} \in \mathbb{R}^n$ to be the all-ones vector, sample $A \in \mathbb{R}^{n \times d}$ and $b \in \mathbb{R}^n$ with Gaussian distributed entries as specified in this theorem's statement and write

$$ P = \{x \in \mathbb{R}^d : Ax \le b\}. $$

Using the Gaussian tail bound Lemma 10 we get that, with probability at least $1 - n^{-d}$, the rows of $\bar{A} - A$ all have norm at most $4\sigma\sqrt{d\ln n}$ and also $\|\bar{b} - b\|_{\infty} \le 4\sigma\sqrt{d\ln n}$. Note that the fact that $S$ is $\sigma$-dense implies that it is $4\sigma\sqrt{d\ln n}$-dense, where $4\sigma\sqrt{d\ln n} \le 1/8$ by assumption on $\sigma$. Abbreviate $\eta = 4\sigma\sqrt{d\ln n}$ and note $\eta = 4d\sigma\sqrt{\ln(4/\sigma)} \le 1/8$. We apply Lemma 54 to the perturbed data $A, b$ and find that the above-mentioned high probability events imply that

$$ (1 - 2\eta)\mathbb{B}_2^d \subseteq P \subseteq (1 + 4\eta)\mathbb{B}_2^d. \qquad (12) $$

It remains to show that (12) implies that the paths from maximizers to minimizers of any objective are large. Note that (12) implies, using $\eta \le 1/8$, that

$$ (1 - 4\eta)\mathbb{B}_2^d \subseteq (1 + 4\eta)^{-1}\mathbb{B}_2^d \subseteq P^\circ \subseteq (1 - 2\eta)^{-1}\mathbb{B}_2^d \subseteq (1 + 3\eta)\mathbb{B}_2^d. \qquad (13) $$

We show that all facets of $P^\circ$ have upper bounded geometric diameter. Let $F \subset P^\circ$ be an arbitrary facet, and let $y \in F$ denote the minimum-norm point inside the facet. Let $v \in F$ be an arbitrary point. The optimality condition of $y$ means that $y^\top v \ge \|y\|^2$, which gives us

$$ \|y - v\|^2 = (y - v)^\top (y - v) = \|y\|^2 + \|v\|^2 - 2y^\top v \le \|v\|^2 - \|y\|^2. $$

From (13) we know that $\|v\| \le (1 + 3\eta)$ and $\|y\| \ge (1 - 4\eta)$, resulting in

$$ \|v\|^2 - \|y\|^2 \le (1 + 6\eta + 9\eta^2) - (1 - 8\eta + 16\eta^2) \le 14\eta - 7\eta^2 \le 14\eta. $$

We thus found that $\|y - v\| \le \sqrt{14\eta}$. Since $v \in F$ was arbitrary, we must have for any two points $v, v' \in F$ that $\|v - v'\| \le \|v - y\| + \|y - v'\| \le 2\sqrt{14\eta} \le 8\sqrt{\eta}$. We have found that the geometric diameter of any facet of $P^\circ$ is at most $8\sqrt{\eta}$. We call on Lemma 55 to find that, assuming (12), for any $c \ne 0$, any path from a maximizer of $c$ to a minimizer of $c$ has combinatorial length at least

$$ (d-1)\left(\frac{2}{(1+4\eta) \cdot 8\sqrt{\eta}} - 2\right) \ge \sqrt{d-1}\left(\frac{1}{12\sqrt{\sigma\sqrt{\ln(4/\sigma)}}} - 2\right). $$

We finish the argument by observing that $\frac{1}{12\sqrt{\sigma\sqrt{\ln(4/\sigma)}}} - 2 \ge \frac{1}{24\sqrt{\sigma\sqrt{\ln(4/\sigma)}}}$. $\square$

We have found that, with probability at least $1 - n^{-d}$, for any non-zero objective $c$, any path from the maximizer of $c$ to the minimizer of $c$ has length at least $\frac{\sqrt{d-1}}{24\sqrt{\sigma\sqrt{\ln(4/\sigma)}}}$. In particular this is true for the combined semi-random shadow path $P(A, b, -c, Z) \cup P(A, b, Z, c)$. When this happens, at least one of the paths $P(A, b, -c, Z)$ or $P(A, b, Z, c)$ must have length at least $\frac{\sqrt{d-1}}{48\sqrt{\sigma\sqrt{\ln(4/\sigma)}}}$. In particular there must exist a non-zero objective $c$ such that $\mathbb{E}[|P(A, b, c, Z)|] \ge \frac{\sqrt{d-1}}{96\sqrt{\sigma\sqrt{\ln(4/\sigma)}}}$, which is the statement claimed in the introduction.

This lower bound implies that the upper bound in Theorem 51 has optimal noise dependence up to polylog factors, in the sense that any upper bound on the shadow path length of the form $\mathrm{poly}(d, \sigma^{-1}, \log n)$ must have a monomial term with dependence at least $\sigma^{-1/2}$.
# Appendices

## A Borrowed Proofs

The following is a verbatim reproduction of a necessary theorem due to [Bac+25]. It is reproduced here in its entirety for the ease of reviewing, since the manuscript [Bac+25] is not yet publically available at the time of this manuscript's submission.

**Theorem 57** (Repeated Theorem 27). Let $B \in \mathbb{R}^{d \times d}$ be an invertible matrix, every whose column has Euclidean norm at most 2, and define, for any $m > 0$, $C_m = \{x \in \mathbb{R}^d : B^{-1}x \ge m\}$. Suppose $c, c' \in \mathbb{R}^d$ are fixed. Let $Z \in \mathbb{R}^d$ be a random vector with 1-log-Lipschitz probability density $\mu$. Then

$$ \mathrm{Pr}[[c + Z, c' + Z] \cap C_m \neq \emptyset] \geq 0.99 \mathrm{Pr}[[c + Z, c' + Z] \cap C_0 \neq \emptyset] $$

for $m = \ln(1/0.99)/2d$.

*Proof.* Write $g_i$ for the $i$'th column of $B$ and $p = \sum_{i=1}^d g_i$. We have $\|p\| \le 2d$. Suppose we have a vector $z \in \mathbb{R}^d$ such that $[c + z, c' + z] \cap C_0 \neq \emptyset$. Let $\lambda \in [0, 1]$ be the minimum number such that $z + c + \lambda(c' - c) \in C_0$. Then we define, for $\alpha = -\frac{\ln(0.99)}{2d}$, the function

$$ f(z) := z + \alpha p. $$

Reusing the previous multiplier, we find the coordinatewise inequality of vectors

$$ B^{-1}(f(z) + c + \lambda(c' - c)) = B^{-1}(z + c + \lambda(c' - c)) + \alpha B^{-1}p \geq \alpha. \quad (14) $$

Hence we find that $[c + f(z), c' + f(z)] \cap C_\alpha \neq \emptyset$. Note that neither $f$ nor the non-emptiness of this intersection depends on the value of $\lambda$.

Thus we have, for a constant $\gamma$ depending only on $d$ and the distribution $\mu$, that

$$ \begin{aligned} \mathrm{Pr}[[c + Z, c' + Z] \cap C_0 \neq \emptyset] &= \mathrm{Pr}[Z \in -[c, c'] + C_0] \\ &= \gamma \int_{-[c, c'] + C_0} \mu(z) \, dz. \end{aligned} $$

Since the map $f$ is a translation independent of $Z$, it is volume-preserving and because of (14), it follows that

$$ \begin{aligned} \mathrm{Pr}[[c + Z, c' + Z] \cap C_0 \neq \emptyset] &= \gamma \int_{-[c, c'] + C_0} \mu(z) \, dz \\ &= \gamma \int_{-[c, c'] + C_\alpha} \mu(f(z)) \, dz \\ &\le \gamma \int_{-[c, c'] + C_\alpha} \mu(z) \cdot e^{\|\alpha p\|} \, dz \\ &\le \gamma e^{2\alpha d} \int_{-[c, c'] + C_\alpha} \mu(z) \, dz \\ &= e^{2\alpha d} \mathrm{Pr}[Z \in -[c, c'] + C_\alpha] \\ &= e^{2\alpha d} \mathrm{Pr}[[c + Z, c' + Z] \cap C_\alpha \neq \emptyset]. \end{aligned} $$

Thus, it follows that

$$ \mathrm{Pr}[[c + Z, c' + Z] \cap C_\alpha \neq \emptyset] \geq e^{-2\alpha d} \mathrm{Pr}[[c + Z, c' + Z] \cap C_0 \neq \emptyset]. $$

<figure><img src="image_7.png" /></figure>

## B Additional Proofs

*Proof of Lemma 7.* Integrating in polar coordinates gives us the normalizing constant

$$ \int_{\mathbb{R}^d} e^{-\|x\|} \, dx = \int_0^\infty \mathrm{vol}_{d-1}(r\mathbb{S}^{d-1}) e^{-r} \, dr $$
$$ 
\begin{aligned}
&= \mathrm{vol}_{d-1}(\mathbb{S}^{d-1}) \int_0^\infty r^{d-1} e^{-r} \, dr \\
&= \mathrm{vol}_{d-1}(\mathbb{S}^{d-1}) \cdot (d-1)!,
\end{aligned}
$$

using the Gamma function. We can obtain the moments of $\|X\|$ using a similar calculation:

$$ 
\begin{aligned}
\int_{\mathbb{R}^d} \|x\|^k e^{-\|x\|} \, dx &= \int_0^\infty \mathrm{vol}_{d-1}(r\mathbb{S}^{d-1}) r^k e^{-r} \, dr \\
&= \mathrm{vol}_{d-1}(\mathbb{S}^{d-1}) \int_0^\infty r^{k+d-1} e^{-r} \, dr \\
&= \mathrm{vol}_{d-1}(\mathbb{S}^{d-1}) \cdot (k+d-1)!.
\end{aligned}
$$

Dividing $\frac{\mathrm{vol}_{d-1}(\mathbb{S}^{d-1}) \cdot (k+d-1)!}{\mathrm{vol}_{d-1}(\mathbb{S}^{d-1}) \cdot (d-1)!} = \frac{(k+d-1)!}{(d-1)!}$ gives the result. □

*Proof of Lemma 8.* Using Markov's inequality we know for $k = d \ln n$ and $t = 2ed \ln n$ that

$$ 
\begin{aligned}
\mathrm{Pr}[\|X\| > t] &= \mathrm{Pr}[\|X\|^k > t^k] \\
&= \frac{\mathrm{E}[\|X\|^k]}{t^k} \\
&\le \frac{(k+d)^k}{t^k} \\
&\le \frac{(2d \ln n)^{d \ln n}}{(2ed \ln n)^{d \ln n}} = n^{-d}.
\end{aligned}
$$

*Proof of Theorem 13.* Assume that without loss of generality the fixed and arbitrary unit vector is $e_1$. We notice that for any $\alpha > 0$ the probability $\mathrm{Pr}[|\theta^\top e_1| \le \alpha]$ is given as the ratio between the volume of the unit sphere $\mathbb{S}^{d-1}$ intersected with the half-spaces $H := \{x \in \mathbb{R}^d: x_1 \le \alpha\}$ and $\{x \in \mathbb{R}^d: x_1 \ge -\alpha\}$ and the volume of the unit sphere $\mathbb{S}^{d-1}$ itself. Further, we notice that the volume of $\mathbb{S}^{d-1}$ can be computed as

$$ \mathrm{vol}(\mathbb{S}^{d-1}) = \int_{-1}^{1} \mathrm{vol}_{d-2}((\sqrt{1-s^2})\mathbb{S}^{d-2}) \sqrt{1 + \left(\frac{-2s}{2\sqrt{1-s^2}}\right)^2} \, ds = \mathrm{vol}_{d-2}(\mathbb{S}^{d-2}) \int_{-1}^{1} \sqrt{1-s^2}^{d-3} \, ds. $$

We notice that the factor part $\left(\frac{-2s}{2\sqrt{1-s^2}}\right)^2$ in the first equality is the derivative of the radius of the sphere $(\sqrt{1-s^2})\mathbb{S}^{d-2}$. Hence, we can write the probability that the first coordinate of $\theta$ is at most $\alpha$ as

$$ \mathrm{Pr}[|\theta^\top e_1| \le \alpha] = \frac{\mathrm{vol}_{d-2}(\mathbb{S}^{d-2}) \int_{-\alpha}^{\alpha} \sqrt{1-s^2}^{d-3} \, ds}{\mathrm{vol}_{d-2}(\mathbb{S}^{d-2}) \int_{-1}^{1} \sqrt{1-s^2}^{d-3} \, ds} \le \frac{\int_{-\alpha}^{\alpha} \sqrt{1-s^2}^{d-3} \, ds}{\int_{-1/\sqrt{d}}^{1/\sqrt{d}} \sqrt{1-s^2}^{d-3} \, ds}. $$

We will upper bound the integrant of the nominator by 1. If $s \in [-1/\sqrt{d}, 1/\sqrt{d}]$, then one calculates that $\sqrt{1-s^2}^{d-3} \in [1/\sqrt{e}, 1]$. We use this for upper bounding the denominator as

$$ \mathrm{Pr}[|\theta^\top e_1| \le \alpha] \le \frac{\int_{-\alpha}^{\alpha} 1 \, ds}{(2/\sqrt{d}) \cdot (1/\sqrt{e})} = \alpha \sqrt{de} $$

and find the desired bound. □
## Notation Index

<table><tr><td>$I \in \binom{[n]}{d}$</td><td>indexes a basis</td></tr><tr><td>$A_I$</td><td>submatrix of A induced by basis I</td></tr><tr><td>$b_I$</td><td>rows of b indexed by I</td></tr><tr><td>$x_I$</td><td>basic solution $x_I = A_I^{-1}b_I$</td></tr><tr><td>$y \in [c, c']$</td><td>intermediate objective</td></tr><tr><td>$F(A, b) \subseteq \binom{[n]}{d}$</td><td>set of feasible bases</td></tr><tr><td>$P(A, b, c, c') \subseteq F(A, b)$</td><td>bases on the shadow path from c to c'</td></tr><tr><td>$G(A, b, g) \subseteq F(A, b)$</td><td>set of bases I with $a_j^\top x_I \le b_j - g \|x_I\|$ for all $j \notin I$</td></tr><tr><td>$M(A, c, c', m) \subseteq \binom{[n]}{d}$</td><td>bases I s.t. $\exists y \in [c, c']$ with $A_I^{-1}y \ge m$</td></tr><tr><td>$N(A, b, c, c', I) \subseteq P(A, b, c, c')$</td><td>neighbours of $I \in P(A, b, c, c')$ on the shadow path</td></tr><tr><td>$L(A, b, c, c', \rho) \subseteq P(A, b, c, c')$</td><td>bases I s.t. $\frac{\|\pi_{c,c'}(x_I-x_{I'})\|}{\|\pi_{c,c'}(x_I)\|} \ge \rho$ for $I' \in N(A, b, c, c', I)$</td></tr><tr><td>$T^S \subseteq V$</td><td>graph nodes in $S \subseteq V$ who have 2 neighbors in S</td></tr><tr><td>$\angle(s, s') \in [0, \pi]$</td><td>angle, the unique number such that $\cos(\angle(s, s')) \cdot \|s\| \cdot \|s'\| = s^\top s'$</td></tr><tr><td>$\angle(S, S') := \inf_{s \in S, s' \in S'} \angle(s, s')$</td><td>minimum angle between two sets of points S, S' $\subseteq \mathbb{R}^d$</td></tr></table>

## References

[AC78] David Avis and Vasek Chvátal. "Notes on Bland's pivoting rule". In: *Polyhedral Combinatorics*. Springer, 1978, pp. 24–34.

[AKS87] Ilan Adler, Richard M. Karp, and Ron Shamir. "A simplex variant solving an $m \times d$ linear program in $O(\min(m^2, d^2))$ expected number of pivot steps". In: *J. Complexity* 3.4 (1987), pp. 372–387. ISSN: 0885-064X. DOI: 10.1016/0885-064X(87)90007-0.

[All+22] Xavier Allamigeon et al. "Interior point methods are not worse than Simplex". In: *2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)*. IEEE. 2022, pp. 267–277.

[AM85] Ilan Adler and Nimrod Megiddo. "A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension". In: *Journal of the ACM (JACM)* 32.4 (1985), pp. 871–895.

[AMR11] David Arthur, Bodo Manthey, and Heiko Röglin. "Smoothed Analysis of the k-Means Method". In: *Journal of the ACM* 58.5 (Oct. 2011), pp. 1–31. ISSN: 1557-735X. DOI: 10.1145/2027216.2027217. URL: http://dx.doi.org/10.1145/2027216.2027217.

[And04] Neculai Andrei. "On the complexity of MINOS package for linear programming". In: *Studies in Informatics and Control* 13.1 (2004), pp. 35–46.

[AZ98] Nina Amenta and Günter M. Ziegler. "Deformed Products and Maximal Shadows". In: *Contemporary Math.* 223 (1998), pp. 57–90.

[Bac+25] Eleon Bach et al. *Analyzing the simplex method with assumptions from the user manual*. 2025+.

[BC24] Alexander E. Black and Francisco Criado. *Random Shadows of Fixed Polytopes*. 2024. arXiv: 2406.06936 [math.CO]. URL: https://arxiv.org/abs/2406.06936.
[Bei+22] René Beier et al. "The smoothed number of Pareto-optimal solutions in bicriteria integer optimization". In: *Mathematical Programming* 200.1 (Sept. 2022), pp. 319–355. ISSN: 1436-4646. DOI: 10.1007/s10107-022-01885-6.

[Bla+21] Alexander Black et al. *On the Simplex method for 0/1 polytopes*. 2021. DOI: 10.48550/ARXIV.2111.14050.

[Bla+24] Alexander E Black et al. "On the Simplex Method for 0/1-Polytopes". In: *Mathematics of Operations Research* (2024).

[Bla23] Alexander E. Black. *Small Shadows of Lattice Polytopes*. Jan. 2023. DOI: 10.1137/1.9781611977554.ch63.

[Bla24] Alexander E. Black. *Exponential Lower Bounds for Many Pivot Rules for the Simplex Method*. 2024. arXiv: 2403.04886 [math.OC]. URL: https://arxiv.org/abs/2403.04886.

[Bon+22] Gilles Bonnet et al. "Asymptotic Bounds on the Combinatorial Diameter of Random Polytopes". In: *38th International Symposium on Computational Geometry, SoCG 2022, June 7-10, 2022, Berlin, Germany*. Ed. by Xavier Goaoc and Michael Kerber. Vol. 224. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, 18:1–18:15. DOI: 10.4230/LIPIcs.SoCG.2022.18.

[Bor77] Karl Heinz Borgwardt. "Untersuchungen zur Asymptotik der mittleren Schrittzahl von Simplexverfahren in der linearen Optimierung". PhD thesis. Universität Kaiserslautern, 1977.

[Bor82] Karl-Heinz Borgwardt. "The Average number of pivot steps required by the Simplex-Method is polynomial". In: *Zeitschrift für Operations Research* 26.1 (1982), pp. 157–177. DOI: 10.1007/BF01917108.

[Bor87] Karl Heinz Borgwardt. *The Simplex Method: A Probabilistic Analysis*. Vol. 1. Springer-Verlag, Berlin, 1987.

[Bor99] Karl Heinz Borgwardt. "A Sharp Upper Bound for the Expected Number of Shadow Vertices in Lp-Polyhedra Under Orthogonal Projection on Two-Dimensional Planes". In: *Mathematics of Operations Research* 24.3 (1999), pp. 544–603.

[BR13] Tobias Brunsch and Heiko Röglin. "Finding Short Paths on Polytopes by the Shadow Vertex Algorithm". In: *Automata, Languages, and Programming. ICALP '13. Berlin, Heidelberg: Springer Berlin Heidelberg*, 2013, pp. 279–290. DOI: 10.1007/978-3-642-39206-1_24.

[Bru+14] Tobias Brunsch et al. "Lower Bounds for the Average and Smoothed Number of Pareto-Optima". In: *Theory of Computing* 10.10 (2014), pp. 237–256. DOI: 10.4086/toc.2014.v010a010.

[BV03] Rene Beier and Berthold Vöcking. "Random knapsack in expected polynomial time". In: *Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing*. STOC '03. San Diego, CA, USA: Association for Computing Machinery, 2003, pp. 232–241. ISBN: 1581136749. DOI: 10.1145/780542.780578.

[Che+20] Xi Chen et al. "Smoothed complexity of local max-cut and binary max-CSP". In: *Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing*. STOC 2020. Chicago, IL, USA: Association for Computing Machinery, 2020, pp. 1052–1065. ISBN: 9781450369794. DOI: 10.1145/3357713.3384325.

[Che+24] Xi Chen et al. "Smoothed Complexity of SWAP in Local Graph Partitioning". In: *Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)*. Society for Industrial and Applied Mathematics, Jan. 2024, pp. 5057–5083. ISBN: 9781611977912. DOI: 10.1137/1.9781611977912.182.

[CY23] Miranda Christ and Mihalis Yannakakis. "The Smoothed Complexity of Policy Iteration for Markov Decision Processes". In: *Proceedings of the 55th Annual ACM Symposium on Theory of Computing*. STOC 2023. Orlando, FL, USA: Association for Computing Machinery, 2023, pp. 1890–1903. ISBN: 9781450399135. DOI: 10.1145/3564246.3585220.

[Dan51] George B Dantzig. "Maximization of a linear function of variables subject to linear inequalities". In: *Cowles Commission Monograph 13: Activity analysis of production and allocation* (1951), pp. 339–347.

[Dan63] George Dantzig. *Linear Programming and Extensions*. Princeton University Press, Dec. 1963. ISBN: 9781400884179. DOI: 10.1515/9781400884179. URL: http://dx.doi.org/10.1515/9781400884179.

[DFH22] Yann Disser, Oliver Friedmann, and Alexander V. Hopp. "An exponential lower bound for Zadeh's pivot rule". In: *Mathematical Programming* (July 2022). DOI: 10.1007/s10107-022-01848-x.

[DH16] Daniel Dadush and Nicolai Hähnle. "On the shadow simplex method for curved polyhedra". In: *Discrete Comput. Geom.* 56.4 (2016), pp. 882–909. ISSN: 0179-5376. DOI: 10.1007/s00454-016-9793-3. URL: http://dx.doi.org/10.1007/s00454-016-9793-3.
[DH20] Daniel Dadush and Sophie Huiberts. "A Friendly Smoothed Analysis of the Simplex Method". In: *SIAM Journal on Computing* 49.5 (Jan. 2020), STOC18-449-499. DOI: 10.1137/18m1197205.

[DM23] Yann Disser and Nils Mosis. "A Unified Worst Case for Classical Simplex and Policy Iteration Pivot Rules". In: *34th International Symposium on Algorithms and Computation (ISAAC 2023)*. Ed. by Satoru Iwata and Naonori Kakimura. Vol. 283. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, 27:1-27:17. ISBN: 978-3-95977-289-1. DOI: 10.4230/LIPIcs.ISAAC.2023.27.

[DS05] Amit Deshpande and Daniel A Spielman. "Improved smoothed analysis of the shadow vertex simplex method". In: *Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science*. 2005, pp. 349-356. DOI: 10.1109/SFCS.2005.44.

[ERV13] Matthias Englert, Heiko Röglin, and Berthold Vöcking. "Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP". In: *Algorithmica* 68.1 (June 2013), pp. 190-264. ISSN: 1432-0541. DOI: 10.1007/s00453-013-9801-4. URL: http://dx.doi.org/10.1007/s00453-013-9801-4.

[FG92] John J. Forrest and Donald Goldfarb. "Steepest-edge simplex algorithms for linear programming". In: *Mathematical Programming* 57.3 (1992), pp. 341-374. ISSN: 0025-5610. DOI: 10.1007/BF01581089.

[FHZ11] Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick. "Subexponential Lower Bounds for Randomized Pivoting Rules for the Simplex Algorithm". In: *Proceedings of the 43rd Annual ACM Symposium on Theory of Computing*. 2011, pp. 283-292. DOI: 10.1145/1993636.1993675.

[FIC] FICO. *FICO Xpress Optimizer Reference Manual*. https://www.fico.com/fico-xpress-optimization/docarchived at https://web.archive.org/web/20230328100937/https://www.fico.com/fico-xpress-optimizerRetrieved September 18th, 2023.

[Fri11] Oliver Friedmann. "A Subexponential Lower Bound for Zadeh's Pivoting Rule for Solving Linear Programs and Games". In: *Proceedings of 15th International Conference on Integer Programming and Combinatorial Optimization*. Ed. by Oktay Günlük and Gerhard J. Woeginger. Springer, 2011, pp. 192-206. DOI: 10.1007/978-3-642-20807-2_16.

[Gol76] Donald Goldfarb. "Using the steepest-edge simplex algorithm to solve sparse linear programs". In: *Sparse matrix computations*. Elsevier, 1976, pp. 227-240.

[Gol83] Donald Goldfarb. "Worst case complexity of the shadow vertex simplex algorithm". In: *preprint*, Columbia University (1983).

[GS55] Saul Gass and Thomas Saaty. "The computational algorithm for the parametric objective function". In: *Naval research logistics quarterly* 2.1-2 (1955), pp. 39-45.

[GS79] Donald Goldfarb and William Y Sit. "Worst case behavior of the steepest edge simplex method". In: *Discrete Applied Mathematics* 1.4 (1979), pp. 277-285.

[Hai83] M. Haimovich. *The simplex method is very good! On the expected number of pivot steps and related properties of random linear programs*. Tech. rep. Columbia University, 1983.

[Har73] Paula M. J. Harris. "Pivot selection methods of the Devex LP code". In: *Mathematical Programming* 5.1 (Dec. 1973), pp. 1-28. ISSN: 1436-4646. DOI: 10.1007/bf01580108.

[HLZ23] Sophie Huiberts, Yin Tat Lee, and Xinzhi Zhang. "Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method". In: *Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC)*. ACM, June 2023. DOI: 10.1145/3564246.3585124.

[HZ15] Thomas Dueholm Hansen and Uri Zwick. "An improved version of the random-facet pivoting rule for the simplex algorithm". In: *Proceedings of the forty-seventh annual ACM symposium on Theory of computing*. 2015, pp. 209-218. DOI: 10.1145/2746539.2746557.

[Jer73] Robert G Jeroslow. "The simplex algorithm with the pivot rule of maximizing criterion improvement". In: *Discrete Mathematics* 4.4 (1973), pp. 367-377.

[Kal92] Gil Kalai. "A subexponential randomized simplex algorithm". In: *Proceedings of the twenty-fourth annual ACM symposium on Theory of computing*. 1992, pp. 475-482.

[Kar84] Narendra Karmarkar. "A new polynomial-time algorithm for linear programming". In: *Proceedings of the sixteenth annual ACM symposium on Theory of computing*. 1984, pp. 302-311.

[Kha80] Leonid G Khachiyan. "Polynomial algorithms in linear programming". In: *USSR Computational Mathematics and Mathematical Physics* 20.1 (1980), pp. 53-72.
[KM11] Tomonari Kitahara and Shinji Mizuno. "A bound for the number of different basic solutions generated by the simplex method". In: *Mathematical Programming* 137.1-2 (Aug. 2011), pp. 579-586. DOI: 10.1007/s10107-011-0482-y.

[KM72] Victor Klee and George J Minty. "How good is the simplex algorithm". In: *Inequalities: III: proceedings of the 3rd Symposium on inequalities* (1972), pp. 159-175.

[KMV23] Marvin Künnemann, Bodo Manthey, and Rianne Veenstra. *Smoothed Analysis of the 2-Opt Heuristic for the TSP under Gaussian Noise*. 2023. DOI: 10.48550/arXiv.2308.00306. arXiv: 2308.00306 [cs.DS].

[KS06] Jonathan A. Kelner and Daniel A. Spielman. "A randomized polynomial-time simplex algorithm for linear programming". In: *Proceedings of the 38th Annual ACM Symposium on Theory of Computing*. 2006, pp. 51-60. DOI: 10.1145/1132516.1132524.

[LS14] Yin Tat Lee and Aaron Sidford. "Path finding methods for linear programming: Solving linear programs in o (vrank) iterations and faster algorithms for maximum flow". In: *2014 IEEE 55th Annual Symposium on Foundations of Computer Science*. IEEE, 2014, pp. 424-433.

[Mat02] Jiří Matoušek. *Lectures on Discrete Geometry*. Springer, 2002. ISBN: 9780387953748. DOI: 10.1007/978-1-4613-0039-7.

[Meg86] Nimrod Megiddo. "Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm". In: *Math. Programming* 35.2 (1986), pp. 140-172. ISSN: 0025-5610. DOI: 10.1007/BF01580645.

[Meh92] Sanjay Mehrotra. "On the implementation of a primal-dual interior point method". In: *SIAM Journal on optimization* 2.4 (1992), pp. 575-601.

[MR23] Bodo Manthey and Jesse van Rhijn. "Improved Smoothed Analysis of 2-Opt for the Euclidean TSP". In: *34th International Symposium on Algorithms and Computation (ISAAC 2023)*. Ed. by Satoru Iwata and Naonori Kakimura. Vol. 283. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, 52:1-52:16. ISBN: 978-3-95977-289-1. DOI: 10.4230/LIPIcs.ISAAC.2023.52.

[MSW96] Jiří Matoušek, Micha Sharir, and Emo Welzl. "A subexponential bound for linear programming". In: *Algorithmica* 16.4-5 (1996), pp. 498-516.

[Mur80] Katta G Murty. "Computational complexity of parametric linear programming". In: *Mathematical programming* 19.1 (1980), pp. 213-219.

[NSS22] Hariharan Narayanan, Rikhav Shah, and Nikhil Srivastava. "A Spectral Approach to Polytope Diameter". In: *13th Innovations in Theoretical Computer Science Conference (ITCS 2022)*. Vol. 215. Leibniz International Proceedings in Informatics (LIPIcs). 2022, 108:1-108:22. DOI: 10.4230/LIPIcs.ITCS.2022.108.

[Ren88] James Renegar. "A polynomial-time algorithm, based on Newton's method, for linear programming". In: *Mathematical programming* 40.1 (1988), pp. 59-93.

[Rou20] Tim Roughgarden, ed. *Beyond the Worst-Case Analysis of Algorithms*. Cambridge University Press, Dec. 2020. ISBN: 9781108494311. DOI: 10.1017/9781108637435.

[RSV25] Lars Rohwedder, Ashkan Safari, and Tjark Vredeveld. "Smoothed analysis of the k-swap neighborhood for makespan scheduling". In: *Operations Research Letters* 59 (Mar. 2025), p. 107244. ISSN: 0167-6377. DOI: 10.1016/j.orl.2025.107244.

[Sha87] Ron Shamir. "The efficiency of the simplex method: a survey". In: *Management science* 33.3 (1987), pp. 301-334. DOI: 10.1287/mnsc.33.3.301.

[Sma83] Steve Smale. "On the average number of steps of the simplex method of linear programming". In: *Mathematical programming* 27.3 (1983), pp. 241-262.

[ST04] Daniel A Spielman and Shang-Hua Teng. "Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time". In: *Journal of the ACM (JACM)* 51.3 (2004), pp. 385-463. DOI: 10.1145/990308.990310.

[Tod86] Michael J. Todd. "Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems". In: *Mathematical Programming* 35.2 (1986), pp. 173-192.
[Ver09] Roman Vershynin. "Beyond Hirsch conjecture: walks on random polytopes and smoothed complexity of the simplex method". In: *SIAM Journal on Computing* 39.2 (2009), pp. 646–678. DOI: 10.1137/070683386.