ECCC-Report TR06-003https://eccc.weizmann.ac.il/report/2006/003Comments and Revisions published for TR06-003en-usTue, 10 Jan 2006 05:26:09 +0200
Paper TR06-003
| Making Hard Problems Harder |
Joshua Buresh-Oppenheim,
Rahul Santhanam
https://eccc.weizmann.ac.il/report/2006/003We 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 ouputs a Boolean function on a smaller number of bits which has greater hardness as measured in terms of input length. A hardness extractor takes in a Boolean function as input, as well as an advice string, and ouputs a Boolean function defined on a smaller number of bits which has close to maximum possible hardness. We prove several positive and negative results about these objects.
Tue, 10 Jan 2006 05:26:09 +0200https://eccc.weizmann.ac.il/report/2006/003