Return to Answer

How about Boosting¹ and the Hardcore Lemma, as described in this paper?

Trevisan, Luca, Madhur Tulsiani, and Salil Vadhan. "Regularity, boosting, and efficiently simulating every high-entropy distribution." 24th Annual IEEE Conference on Computational Complexity, IEEE, 2009. (PDF download.)

The Hardcore Lemma can be proved via LP duality:

"if a problem is hard-on-average in a weak sense on uniformly distributed inputs, then there is a 'hardcore' subset of inputs of noticeable density such that the problem is hard-on-average in a much stronger sense on inputs randomly drawn from such set."

Their proof of their main result "uses duality of linear programming (or, equivalently, the finite dimensional Hahn-Banach Theorem) in the form of the min-max theorem for two-player zero-sum games."

---

¹ "most boosting algorithms consist of iteratively learning weak classifiers with respect to a distribution and adding them to a final strong classifier."

How about Boosting¹ and the Hardcore Lemma, as described in this paper?

Trevisan, Luca, Madhur Tulsiani, and Salil Vadhan. "Regularity, boosting, and efficiently simulating every high-entropy distribution." 24th Annual IEEE Conference on Computational Complexity, IEEE, 2009. (PDF download.)

The Hardcore Lemma can be proved via LP duality:

"if a problem is hard-on-average in a weak sense on uniformly distributed inputs, then there is a 'hardcore' subset of inputs of noticeable density such that the problem is hard-on-average in a much stronger sense on inputs randomly drawn from such set."

Their proof of their main result "uses duality of linear programming (or, equivalently, the finite dimensional Hahn-Banach Theorem) in the form of the min-max theorem for two-player zero-sum games."

Another summary of Impagliazzo's Hardcore Lemma:

"Every hard function has a hardcore subset such that the restricted function becomes extremely hard to compute."

---

¹ Boosting constitutes "a family of machine learning algorithms which convert weak learners to strong ones." ... "[M]ost boosting algorithms consist of iteratively learning weak classifiers with respect to a distribution and adding them to a final strong classifier."

How about Boosting¹ and the Hardcore Lemma, as described in this paper?

Trevisan, Luca, Madhur Tulsiani, and Salil Vadhan. "Regularity, boosting, and efficiently simulating every high-entropy distribution." 24th Annual IEEE Conference on Computational Complexity, IEEE, 2009. (PDF download.)

The Hardcore Lemma can be proved via LP duality:

"if a problem is hard-on-average in a weak sense on uniformly distributed inputs, then there is a 'hardcore' subset of inputs of noticeable density such that the problem is hard-on-average in a much stronger sense on inputs randomly drawn from such set."

---

¹ "most boosting algorithms consist of iteratively learning weak classifiers with respect to a distribution and adding them to a final strong classifier."

How about Boosting¹ and the Hardcore Lemma, as described in this paper?

Trevisan, Luca, Madhur Tulsiani, and Salil Vadhan. "Regularity, boosting, and efficiently simulating every high-entropy distribution." 24th Annual IEEE Conference on Computational Complexity, IEEE, 2009. (PDF download.)

The Hardcore Lemma can be proved via LP duality:

"if a problem is hard-on-average in a weak sense on uniformly distributed inputs, then there is a 'hardcore' subset of inputs of noticeable density such that the problem is hard-on-average in a much stronger sense on inputs randomly drawn from such set."

Their proof of their main result "uses duality of linear programming (or, equivalently, the finite dimensional Hahn-Banach Theorem) in the form of the min-max theorem for two-player zero-sum games."

---

¹ "most boosting algorithms consist of iteratively learning weak classifiers with respect to a distribution and adding them to a final strong classifier."

How about  Boosting and the Hardcore Lemma, as described in this paper?

Trevisan, Luca, Madhur Tulsiani, and Salil Vadhan. "Regularity, boosting, and efficiently simulating every high-entropy distribution." 24th Annual IEEE Conference on Computational Complexity, IEEE, 2009. (PDF download.)

The Hardcore Lemma can be proved via LP duality:

"if a problem is hard-on-average in a weak sense on uniformly distributed inputs, then there is a 'hardcore' subset of inputs of noticeable density such that the problem is hard-on-average in a much stronger sense on inputs randomly drawn from such set."

How about  Boosting¹ and the Hardcore Lemma, as described in this paper?

Trevisan, Luca, Madhur Tulsiani, and Salil Vadhan. "Regularity, boosting, and efficiently simulating every high-entropy distribution." 24th Annual IEEE Conference on Computational Complexity, IEEE, 2009. (PDF download.)

The Hardcore Lemma can be proved via LP duality:

"if a problem is hard-on-average in a weak sense on uniformly distributed inputs, then there is a 'hardcore' subset of inputs of noticeable density such that the problem is hard-on-average in a much stronger sense on inputs randomly drawn from such set."

---

¹ "most boosting algorithms consist of iteratively learning weak classifiers with respect to a distribution and adding them to a final strong classifier."