線形最適化にほぼ二次下限、Santosh S. Vempala氏が証明
サントシュ・S・ヴェンパラ (Santosh S. Vempala) 氏は9月24日(現地時間)、メンバシップオラクルモデルにおける凸体上の線形最適化および一様サンプリングに関する確率的アルゴリズムについて、ほぼ二次下限が存在することを証明した論文を arXiv cs.DS で発表した。この研究は、線形最適化に関する既存のほぼ二次上限と、ディメンション (dimension) のポリログファクター (polylog factor) まで一致する成果であり、凸体上の最適化問題の計算限界解明に貢献する。