UC San Diego

This dissertation presents several results at the intersection of

complexity theory and algorithm design. Complexity theory aims to

lower-bound the amount of computational resources (such as time and

space) required to solve interesting problems. Algorithm design aims

to upper-bound the amount of computational resources required to solve

interesting problems. These pursuits appear opposed. However, some

algorithm design and complexity lower bound problems are inextricably

connected.

This dissertation explores several such connections. From "natural"

proofs of circuit-size lower bounds, we create learning

algorithms. From the exact hardness of problems in polynomial time, we

create algorithms of estimating the acceptance probability of

circuits. Finally, from algorithms for testing the identity of

airthmetic circuits over finite fields, we create arithmetic

circuit-complexity lower bounds.