Beyond Smoothed Analysis: Analyzing the Simplex Method by the Book
Posted3 months agoActive2 months ago
arxiv.orgSciencestory
calmpositive
Debate
10/100
AlgorithmsComplexity TheoryOptimization
Key topics
Algorithms
Complexity Theory
Optimization
A new paper analyzes the simplex method using a novel approach beyond smoothed analysis, sparking interest and discussion among HN users about its implications for optimization and complexity theory.
Snapshot generated from the HN discussion
Discussion Activity
Light discussionFirst comment
5d
Peak period
3
108-120h
Avg / period
3
Key moments
- 01Story posted
Oct 27, 2025 at 12:13 PM EDT
3 months ago
Step 01 - 02First comment
Nov 1, 2025 at 7:34 AM EDT
5d after posting
Step 02 - 03Peak activity
3 comments in 108-120h
Hottest window of the conversation
Step 03 - 04Latest activity
Nov 1, 2025 at 9:06 AM EDT
2 months ago
Step 04
Generating AI Summary...
Analyzing up to 500 comments to identify key contributors and discussion patterns
ID: 45722691Type: storyLast synced: 11/20/2025, 2:21:16 PM
Want the full context?
Jump to the original sources
Read the primary article or dive into the live Hacker News thread when you're ready.
[EDIT: The following is my own clumsy mistake] Minor note: The definition of "mean width" of a polyhedron P in the paper is not translation invariant, and that's confusing. In other words, the mean width of a polyhedron P can differ from that of P+x := {p+x | p ∈ P} where x is some vector. Is that intended? It doesn't agree with how the word "width" is normally used. I would call it a "mean furthest projection". Or maybe "mean peak projection" or "mean shadow"?
"Half the mean width of a polyhedron P is equal to the expected value of
where θ ∈ S^(d−1) is uniformly random distributed with respect to the Haar measure on the unit sphere."The expression max θ^T x is not translation-invariant: if you replace x with x + ∆x, you get (max θ^T x) + θ^T ∆x. But the expectation of θ^T ∆x is 0 so the expectation of the maximum is translation-invariant again.