Lucky Talk: An Algorithmic Characterization of a Class of Inequalities
summary
Main theorem: given finite sequences a_i, b_i, c_i the multiplicative inequality over all positive x_j,y_j holds exactly when the target expression decomposes as a finite product of Hölder-type and lp-monotonicity inequalities, and there is a polynomial-time algorithm that either outputs that decomposition or produces a concrete witness sequence. Proof maps sequences to l(a,b)=log sum_j x_j^a y_j^b, uses convexity plus a convex lower-hull with origin-secant condition, encodes constraints as a linear program and reads off constructive proofs or counterexamples. Numerical checks work on the l variables, making the method robust.
AI-written summary · about
chapters (7)
- 0:00Instance optimal algorithms
- 1:26Inequalities with sequences
- 4:14Holder and LP monotonicity
- 7:15Counterexamples impractical
- 10:14Geometric proof interpretation
- 17:33Linear program construction
- 21:54Numerical precision
related talks
33mA Few Connections Between Optimization and Probability
01h 11mPedagogical Talk: Failure of Low-Degree Polynomials
49mDiscrete Optimization using Log-Concave Polynomials
32mQuantitative Correlation Inequalities via Semigroup Interpolation
01h 04mFrom Proofs to Algorithms for Machine Learning Problems
01h 11m(Hidden) Symmetries of Computational Problems (continued)
01h 04mLP/SDP Hierarchies and Sum of Squares Proofs 2
27mNonnegative Polynomials, Nonconvex Polynomial Optimization, and Applications to Learning