All reports by Author Igor Oliveira:

__
TR13-129
| 17th September 2013
__

Adam Klivans, Pravesh Kothari, Igor Oliveira#### Constructing Hard Functions from Learning Algorithms

Revisions: 1

__
TR13-117
| 1st September 2013
__

Igor Oliveira#### Algorithms versus Circuit Lower Bounds

Adam Klivans, Pravesh Kothari, Igor Oliveira

Fortnow and Klivans proved the following relationship between efficient learning algorithms and circuit lower bounds: if a class $\mathcal{C} \subseteq P/poly$ of Boolean circuits is exactly learnable with membership and equivalence queries in polynomial-time, then $EXP^{NP} \not \subseteq \mathcal{C}$ (the class $EXP^{NP}$ was subsequently improved to $P$ by Hitchcock and ... more >>>

Igor Oliveira

Different techniques have been used to prove several transference theorems of the form "nontrivial algorithms for a circuit class C yield circuit lower bounds against C". In this survey we revisit many of these results. We discuss how circuit lower bounds can be obtained from derandomization, compression, learning, and satisfiability ... more >>>