Making Hard Problems Harder

Joshua Buresh-Oppenheim, Rahul Santhanam

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider a general approach to the hoary problem of (im)proving circuit lower bounds. We define notions of hardness condensing and hardness extraction, in analogy to the corresponding notions from the computational theory of randomness. A hardness condenser is a procedure that takes in a Boolean function as input, as well as an advice string, and outputs a Boolean function on a smaller number of bits which has greater hardness when measured in terms of input length. A hardness extractor takes in a Boolean function as input, as well as an advice string, and outputs a Boolean function defined on a smaller number of bits which has close to maximum hardness. We prove several positive and negative results about these objects.
Original languageEnglish
Title of host publication21st Annual IEEE Conference on Computational Complexity (CCC 2006), 16-20 July 2006, Prague, Czech Republic
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages73-87
Number of pages15
ISBN (Print)0-7695-2596-2
DOIs
Publication statusPublished - 2006

Fingerprint

Dive into the research topics of 'Making Hard Problems Harder'. Together they form a unique fingerprint.

Cite this