Article

Hard-core distributions for somewhat hard problems

Author:

R. ImpagliazzoAuthors Info & Claims

FOCS '95: Proceedings of the 36th Annual Symposium on Foundations of Computer Science

Page 538

Published: 23 October 1995 Publication History

Publisher Site

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.

Cited By

View all

Gravin NGuo SKwok TLu PMarx D(2021)Concentration bounds for almost k-wise independence with applications to non-uniform securityProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458207(2404-2423)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458207
Bogdanov ASabin MVasudevan PChan T(2019)XOR codes and sparse learning parity with noiseProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310496(986-1004)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310496
Balcan MBlum AChen SAndre EKoenig SDastani MSukthankar G(2018)Diversified Strategies for Mitigating Adversarial Attacks in Multiagent SystemsProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3237383.3237446(407-415)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.5555/3237383.3237446
Show More Cited By

Recommendations

The inapproximability of non-NP-hard optimization problems

The inapproximability of non-NP-hard optimization problems is investigated. Techniques are given to show that the problems LOG DOMINATING SET and LOG HYPERGRAPH VERTEX COVER cannot be approximated to a constant ratio in polynomial time unless the ...
Hard constraint satisfaction problems have hard gaps at location 1

An instance of the maximum constraint satisfaction problem (Max CSP) is a finite collection of constraints on a set of variables, and the goal is to assign values to the variables that maximises the number of satisfied constraints. Max CSP captures many ...
Complexity of Hard-Core Set Proofs

We study a fundamental result of Impagliazzo (FOCS’95) known as the hard-core set lemma. Consider any function $${f:\{0,1\}^n\to\{0,1\}}$$ which is “mildly hard”, in the sense that any circuit of size s must disagree with f on at least a δ fraction of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

FOCS '95: Proceedings of the 36th Annual Symposium on Foundations of Computer Science

October 1995

ISBN:0818671831

Publisher

IEEE Computer Society

United States

Publication History

Published: 23 October 1995

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

64
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Gravin NGuo SKwok TLu PMarx D(2021)Concentration bounds for almost k-wise independence with applications to non-uniform securityProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458207(2404-2423)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458207
Bogdanov ASabin MVasudevan PChan T(2019)XOR codes and sparse learning parity with noiseProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310496(986-1004)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310496
Balcan MBlum AChen SAndre EKoenig SDastani MSukthankar G(2018)Diversified Strategies for Mitigating Adversarial Attacks in Multiagent SystemsProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3237383.3237446(407-415)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.5555/3237383.3237446
De AMossel ENeeman JCzumaj A(2018)Non interactive simulation of correlated distributions is decidableProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175478(2728-2746)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175478
Artemenko SImpagliazzo RKabanets VShaltiel R(2016)Pseudorandomness when the odds are against youProceedings of the 31st Conference on Computational Complexity10.5555/2982445.2982454(1-35)Online publication date: 29-May-2016
https://dl.acm.org/doi/10.5555/2982445.2982454
Skórski M(2016)Simulating Auxiliary Inputs, RevisitedProceedings, Part I, of the 14th International Conference on Theory of Cryptography - Volume 998510.1007/978-3-662-53641-4_7(159-179)Online publication date: 31-Oct-2016
https://dl.acm.org/doi/10.1007/978-3-662-53641-4_7
Rossman BZuckerman D(2015)Correlation bounds against monotone NCProceedings of the 30th Conference on Computational Complexity10.5555/2833227.2833247(392-411)Online publication date: 17-Jun-2015
https://dl.acm.org/doi/10.5555/2833227.2833247
Watson T(2015)Advice Lower Bounds for the Dense Model TheoremACM Transactions on Computation Theory10.1145/26766597:1(1-18)Online publication date: 13-Jan-2015
https://dl.acm.org/doi/10.1145/2676659
De ADiakonikolas IFeldman VServedio R(2014)Nearly Optimal Solutions for the Chow Parameters Problem and Low-Weight Approximation of HalfspacesJournal of the ACM10.1145/259077261:2(1-36)Online publication date: 24-Apr-2014
https://dl.acm.org/doi/10.1145/2590772
Vadhan SZheng CKarloff HPitassi T(2012)Characterizing pseudoentropy and simplifying pseudorandom generator constructionsProceedings of the forty-fourth annual ACM symposium on Theory of computing10.1145/2213977.2214051(817-836)Online publication date: 19-May-2012
https://dl.acm.org/doi/10.1145/2213977.2214051
Show More Cited By

Abstract

Cited By

Recommendations

The inapproximability of non-NP-hard optimization problems

Hard constraint satisfaction problems have hard gaps at location 1

Complexity of Hard-Core Set Proofs

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations