On the Problems Related to Waring Rank and Border Waring Rank

on YouTube ↗33m

" summary

Shows that if a homogeneous polynomial has border Waring rank k (k < degree d) then its actual Waring rank is at most 4^k · d, improving the trivial d^k bound and generalizing known small-k cases. Uses algebraic limits (ε expansions), partial-derivative obstructions tied to natural-proof barriers, and simple geometric reductions; exhibits the concrete example x^2 y with border rank 2 but Waring rank 3 to illustrate the gap. Places results in the GCT/approximation context and notes remaining questions about tight equations and ε-degree control.

AI-written summary · about

" chapters (4)

1. 0:00Introduction to GCT and complexity
2. 14:17Defining Waring rank
3. 14:52Border complexity and bounds
4. 29:37Conclusion and future questions

" related talks

• 43mGeometric Complexity Theory and Tensor RankChristian Ikenmeyer · Geometric Complexity Theory 2014
• 59mElementary Results on Maximal, Generic and Typical RanksGrigoriy Blekherman · Tensors in Computer Science and Geometry 2014
• 01h 00mAverage-case Complexity for Polynomials, and All ThatEmanuele Viola · Lower Bounds, Learning, and Average-Case Complexity
• 36mThe Rank of Sparse Random MatricesJane Gao · Computational Phase Transitions (Simons Institute, 2020)
• 01h 03mHigh Dimensional Geometry and Concentration IISantosh Vempala · Foundations of Data Science Boot Camp 2018
• 50mAlgorithmic Regularity for Polynomials and ApplicationsArnab Bhattacharyya · Neo-Classical Methods in Discrete Analysis 2013
• 44mNew Techniques For Proving Fine-Grained Average-Case HardnessAndrea Lincoln · Rigorous Evidence for Information-Computation Trade-offs
• 35mOn the Chromatic Number of Random Regular GraphsSamuel Hetterich · Random Instances and Phase Transitions (Simons Institute, 2016)