### Recent Comments

Vijay Vazirani on To cheer you up in difficult t… Vijay Vazirani on To cheer you up in difficult t… Gil Kalai on To cheer you up in difficult t… Victory Omole on To cheer you up in difficult t… To cheer you up in d… on Test Your Intuition (27) about… To cheer you up in d… on Jim Geelen, Bert Gerards, and… To cheer you up in d… on Timothy Chow Launched Polymath… Thomas Bloom on To cheer you up in difficult t… William Gasarch on To cheer you up in difficult t… Thomas Bloom on To cheer you up in difficult t… Gil Kalai on To cheer you up in difficult t… William Gasarch on To cheer you up in difficult t… -
### Recent Posts

- To cheer you up in difficult times 9: Alexey Pokrovskiy proved that Rota’s Basis Conjecture holds asymptotically
- To Cheer you up in Difficult Times 8: Nathan Keller and Ohad Klein Proved Tomaszewski’s Conjecture on Randomly Signed Sums
- Noam Lifshitz: A new hypercontractivity inequality — The proof!
- To cheer you up in difficult times 7: Bloom and Sisask just broke the logarithm barrier for Roth’s theorem!
- To cheer you up in difficult times 6: Play Rani Sharim’s two-player games of life, read Maya Bar-Hillel presentation on catching lies with statistics, and more.
- To cheer you up in difficult times 5: A New Elementary Proof of the Prime Number Theorem by Florian K. Richter
- To cheer you up in difficult times 4: Women In Theory present — I will survive
- To cheer you up in difficult times 3: A guest post by Noam Lifshitz on the new hypercontractivity inequality of Peter Keevash, Noam Lifshitz, Eoin Long and Dor Minzer
- Harsanyi’s Sweater

### Top Posts & Pages

- To cheer you up in difficult times 9: Alexey Pokrovskiy proved that Rota’s Basis Conjecture holds asymptotically
- Test Your Intuition (27) about the Alon-Tarsi Conjecture
- To Cheer you up in Difficult Times 8: Nathan Keller and Ohad Klein Proved Tomaszewski's Conjecture on Randomly Signed Sums
- Updates and plans III.
- To cheer you up in difficult times 7: Bloom and Sisask just broke the logarithm barrier for Roth's theorem!
- Jim Geelen, Bert Gerards, and Geoﬀ Whittle Solved Rota's Conjecture on Matroids
- A sensation in the morning news - Yaroslav Shitov: Counterexamples to Hedetniemi's conjecture.
- Timothy Chow Launched Polymath12 on Rota Basis Conjecture and Other News
- 'Gina Says'

### RSS

# Tag Archives: The simplex algorithm

## Subexponential Lower Bound for Randomized Pivot Rules!

Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick have managed to prove subexponential lower bounds of the form for the following two basic randomized pivot rules for the simplex algorithm! This is the first result of its kind and deciding … Continue reading