Proof of Proposition 6.1, p. 30 — on u, v ≥ 0 the exponent g(u, v) dominates h(u, v)
ProvedOptInapprox.Orthant.g_ge_helementary-inequalitygaussianp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and , and let
Then for all ,
On the quadrant of integration of (18) this lets be replaced by the simpler exponent , at the cost of an inequality; it is the only place where the proof of Proposition 6.1 loses anything.
Preamble
import Mathlib import Definitions.Def_OptInapprox_Orthant_Setting open MeasureTheory ProbabilityTheory
Formal statement
namespace OptInapprox.Orthant
/-- Proof of Proposition 6.1, p. 30: on `u, v ≥ 0`, `g(u, v) ≥ h(u, v)`. -/
theorem g_ge_h (t ρ u v : ℝ) (ht : 0 < t) (hρ0 : 0 ≤ ρ) (hρ1 : ρ < 1) (hu : 0 ≤ u) (hv : 0 ≤ v) :
hExp ρ t u v ≤ gExp ρ t u v := by sorry
end OptInapprox.Orthant
Source
Khot, Kindler, Mossel & O'Donnell, Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?, SIAM J. Comput. 37(1), 2007 (authors' version of February 7, 2007), p. 30, proof of Proposition 6.1 (the sentence after (18))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.