Hard-core distributions for somewhat hard problems
Top Cited Papers
- 19 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 2 (02725428) , 538-545
- https://doi.org/10.1109/sfcs.1995.492584
Abstract
Consider a decision problem that cannot be 1-/spl delta/ approximated by circuits of a given size in the sense that any such circuit fails to give the correct answer on at least a /spl delta/ fraction of instances. We show that for any such problem there is a specific "hard core" set of inputs which is at least a /spl delta/ fraction of all inputs and on which no circuit of a slightly smaller size can get even a small advantage over a random guess. More generally, our argument holds for any non uniform model of computation closed under majorities. We apply this result to get a new proof of the Yao XOR lemma (A.C. Yao, 1982), and to get a related XOR lemma for inputs that are only k wise independent.Keywords
This publication has 8 references indexed in Scilit:
- Products and help bits in decision treesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Security preserving amplification of hardnessPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Hardness vs randomnessJournal of Computer and System Sciences, 1994
- Simple strategies for large zero-sum games with applications to complexity theoryPublished by Association for Computing Machinery (ACM) ,1994
- A hard-core predicate for all one-way functionsPublished by Association for Computing Machinery (ACM) ,1989
- One way functions and pseudorandom generatorsCombinatorica, 1987
- Theory and application of trapdoor functionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- Zur Theorie der GesellschaftsspieleMathematische Annalen, 1928