More Web Proxy on the site http://driver.im/

Article

Impossibility results on weakly black-box hardness amplification

Authors:

Hsin-Lung WuAuthors Info & Claims

FCT'07: Proceedings of the 16th international conference on Fundamentals of Computation Theory

Pages 400 - 411

Published: 27 August 2007 Publication History

Abstract

We study the task of hardness amplification which transforms a hard function into a harder one. It is known that in a high complexity class such as exponential time, one can convert worst-case hardness into average-case hardness. However, in a lower complexity class such as NP or sub-exponential time, the existence of such an amplification procedure remains unclear.

We consider a class of hardness amplifications called weakly black-box hardness amplification, in which the initial hard function is only used as a black box to construct the harder function. We show that if an amplification procedure in TIME(t) can amplify hardness beyond an O(t) factor, then it must basically embed in itself a hard function computable in TIME(t). As a result, it is impossible to have such a hardness amplification with hardness measured against TIME(t). Furthermore, we show that, for any k ∈ N, if an amplification procedure in Σ_kP can amplify hardness beyond a polynomial factor, then it must basically embed a hard function in Σ_kP. This in turn implies the impossibility of having such hardness amplification with hardness measured against Σ_kP/poly.

References

[1]

Agrawal, M., Allender, E., Rudich, S.: Reductions in circuit complexity: an isomorphism theorem and a gap theorem. Journal of Computer and System Sciences 57, 127-143 (1998)

Digital Library

[2]

Billingsley, P.: Probability and measure, 3rd edn. Wiley & Sons, Chichester (1995)

[3]

Babai, L., Fortnow, L., Nisan, N., Wigderson, A.: BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computational Complexity 3(4), 307-318 (1993)

Digital Library

[4]

Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudo random bits. In: Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science, pp. 112-117. IEEE Computer Society Press, Los Alamitos (1982)

Digital Library

[5]

Bogdanov, A., Trevisan, L.: On worst-case to average-case reductions for NP problems. In: Proceedings of the 44th Annual Symposium on Foundations of Computer Science, Cambridge, Massachusetts, pp. 11-14 (2003)

Digital Library

[6]

Furst, M. L., Saxe, J. B., Sipser, M.: Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory 17(1), 13-27 (1984)

[7]

Håstad, J.: Computational limitations for small depth circuits. PhD thesis, MIT Press (1986)

[8]

Healy, A., Vadhan, S., Viola, E.: Using nondeterminism to amplify hardness. In: Proceedings of the 36th ACM Symposium on Theory of Computing, pp. 192-201. ACM Press, New York (2004)

Digital Library

[9]

Impagliazzo, R.: Hard-core distributions for somewhat hard problems. In: Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, pp. 538-545. IEEE Computer Society Press, Los Alamitos (1995)

Digital Library

[10]

Impagliazzo, R., Levin, L.: No better ways to generate hard NP instances than picking uniformly at random. In: Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, pp. 812-821. IEEE Computer Society Press, Los Alamitos (1990)

Digital Library

[11]

Impagliazzo, R., Shaltiel, R., Wigderson, A.: Extractors and pseudo-random generators with optimal seed length. In: Proceedings of the 32nd ACM Symposium on Theory of Computing, pp. 1-10. ACM Press, New York (2000)

Digital Library

[12]

Impagliazzo, R., Wigderson, A.: P=BPP if E requires exponential circuits: Derandomizing the XOR lemma. In: Proceedings of the 29th ACM Symposium on Theory of Computing, pp. 220-229. ACM Press, New York (1997)

Digital Library

[13]

Klivans, A., van Melkebeek, D.: Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. In: Proceedings of the 31st ACM Symposium on Theory of Computing, pp. 659-667. ACM Press, New York (1999)

Digital Library

[14]

Lu, C.-J., Tsai, S.-C., Wu, H.-L.: On the complexity of hardness amplification. In: Proceedings of the 20th Annual IEEE Conference on Computational Complexity, pp. 170-182. IEEE Computer Society Press, Los Alamitos (2005)

Digital Library

[15]

Lin, H., Trevisan, L., Wee, H.: On hardness amplification of one-way functions. In: Proceedings of the 2nd Theory of Cryptography Conference, pp. 34-49 (2005)

Digital Library

[16]

Nisan, N.: Pseudorandom bits for constant depth circuits. Combinatorica 11(1), 63-70 (1991)

[17]

Nisan, N., Wigderson, A.: Hardness vs Randomness. Journal of Computer and System Sciences 49(2), 149-167 (1994)

Digital Library

[18]

O'Donnell, R.: Hardness amplification within NP. In: Proceedings of the 34th ACM Symposium on Theory of Computing, pp. 751-760. ACM Press, New York (2002)

Digital Library

[19]

Papadimitriou, C.: Computational Complexity. Addison-Wesley, Reading (1994)

[20]

Sudan, M., Trevisan, L., Vadhan, S.: Pseudorandom generators without the XOR lemma. Journal of Computer and System Sciences 62(2), 236-266 (2001)

Digital Library

[21]

Shaltiel, R., Umans, C.: Simple extractors for all min-entropies and a new pseudorandom generator. In: Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, pp. 648-657. IEEE Computer Society Press, Los Alamitos (2001)

Digital Library

[22]

Umans, C.: Pseudo-random generators for all hardnesses. Journal of Computer and System Sciences 67(2), 419-440 (2003)

Digital Library

[23]

Viola, E.: The complexity of constructing pseudorandom generators from hard functions. Computational Complexity 13(3-4), 147-188 (2004)

Digital Library

[24]

Viola, E.: On constructing parallel pseudorandom generators from one-way Functions. In: Proceedings of the 20th Annual IEEE Conference on Computational Complexity, pp. 183-197. IEEE Computer Society Press, Los Alamitos (2005)

Digital Library

[25]

Yao, A.C.-C.: Theory and applications of trapdoor functions. In: Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science, pp. 80-91. IEEE Computer Society Press, Los Alamitos (1982)

Cited By

Applebaum BArtemenko SShaltiel RYang GZuckerman D(2015)Incompressible functions, relative-error extractors, and the power of nondeterministic reductions (extended abstract)Proceedings of the 30th Conference on Computational Complexity10.5555/2833227.2833256(582-600)Online publication date: 17-Jun-2015
https://dl.acm.org/doi/10.5555/2833227.2833256
Shaltiel RViola ELadner RDwork C(2008)Hardness amplification proofs require majorityProceedings of the fortieth annual ACM symposium on Theory of computing10.1145/1374376.1374461(589-598)Online publication date: 17-May-2008
https://dl.acm.org/doi/10.1145/1374376.1374461

Impossibility results on weakly black-box hardness amplification
1. Theory of computation
  1. Computational complexity and cryptography

Recommendations

Hardness amplification proofs require majority
STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computing

Hardness amplification is the fundamental task of converting a δ-hard function f : (0, 1)ⁿ -> (0, 1) into a (1/2-ε)-hard function Amp(f), where f is γ-hard if small circuits fail to compute f on at least a γ fraction of the inputs. Typically, ε,δ are ...
Query complexity in errorless hardness amplification
APPROX'11/RANDOM'11: Proceedings of the 14th international workshop and 15th international conference on Approximation, randomization, and combinatorial optimization: algorithms and techniques

An errorless circuit for a boolean function is one that outputs the correct answer or "don't know" on each input (and never outputs the wrong answer). The goal of errorless hardness amplification is to show that if f has no size s errorless circuit that ...
Hardness Amplification Proofs Require Majority

Hardness amplification is the fundamental task of converting a $\delta$-hard function $f:\{0,1\}^n\to\{0,1\}$ into a $(1/2-\epsilon)$-hard function $\mathit{Amp}(f)$, where $f$ is $\gamma$-hard if small circuits fail to compute $f$ on at least a $\gamma$...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

FCT'07: Proceedings of the 16th international conference on Fundamentals of Computation Theory

August 2007

505 pages

ISBN:3540742395

Editors:
Erzsébet Csuhaj-Varjú
Hungarian Academy of Sciences, Computer and Automation Research Institute, Budapest, Hungary
,
Zoltán Ésik
University of Szeged, Department of Computer Science, Szeged, Hungary

Sponsors

Hungarian Academy of Sciences: The Hungarian Academy of Sciences
Department of Computer Science, University of Szeged: Department of Computer Science, University of Szeged

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 27 August 2007

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 07 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Applebaum BArtemenko SShaltiel RYang GZuckerman D(2015)Incompressible functions, relative-error extractors, and the power of nondeterministic reductions (extended abstract)Proceedings of the 30th Conference on Computational Complexity10.5555/2833227.2833256(582-600)Online publication date: 17-Jun-2015
https://dl.acm.org/doi/10.5555/2833227.2833256
Shaltiel RViola ELadner RDwork C(2008)Hardness amplification proofs require majorityProceedings of the fortieth annual ACM symposium on Theory of computing10.1145/1374376.1374461(589-598)Online publication date: 17-May-2008
https://dl.acm.org/doi/10.1145/1374376.1374461

View Options

View options

Media

Figures

Other

Tables

View Table of Contents