article

Pseudorandomness for Approximate Counting and Sampling

Authors:

Ronen Shaltiel,

Christopher UmansAuthors Info & Claims

Computational Complexity, Volume 15, Issue 4

Pages 298 - 341

https://doi.org/10.1007/s00037-007-0218-9

Published: 01 December 2006 Publication History

Abstract

We study computational procedures that use both randomness and nondeterminism. The goal of this paper is to derandomize such procedures under the weakest possible assumptions.

Our main technical contribution allows one to "boost" a given hardness assumption: We show that if there is a problem in EXP that cannot be computed by poly-size nondeterministic circuits then there is one which cannot be computed by poly-size circuits that make non-adaptive NP oracle queries. This in particular shows that the various assumptions used over the last few years by several authors to derandomize Arthur-Merlin games (i.e., show AM = NP) are in fact all equivalent .

We also define two new primitives that we regard as the natural pseudorandom objects associated with approximate counting and sampling of NP-witnesses. We use the "boosting" theorem and hashing techniques to construct these primitives using an assumption that is no stronger than that used to derandomize AM.

We observe that Cai's proof that $$\rm S^{P}_{2} \subseteq ZPP^{NP}$$ and the learning algorithm of Bshouty et al. can be seen as reductions to sampling that are not probabilistic. As a consequence they can be derandomized under an assumption which is weaker than the assumption that was previously known to suffice.

References

[1]

E. ALLENDER, M. KOUCKY, D. RONNEBURGER & S. ROY (2003). Derandomization and Distinguishing Complexity. In Proceedings of the 18th Annual IEEE Conference on Computational Complexity , 209-220.

[2]

V. ARVIND & J. KÖBLER (2001). On Pseudorandomness and Resource-bounded Measure. Theoretical Computer Science 255 .

[3]

L. BABAI (1985). Trading group theory for randomness. In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing .

[4]

L. BABAI, L. FORTNOW, N. NISAN & A. WIGDERSON (1993). BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs. Computational Complexity 3 (4), 307-318.

Digital Library

[5]

D. BEAVER & J. FEIGENBAUM (1990). Hiding Instances in Multioracle Queries. In 7th Annual Symposium on Theoretical Aspects of Computer Science , volume 415 of LNCS , 37-48. Springer.

[6]

M. BELLARE, O. GOLDREICH & E. PETRANK (2000). Uniform Generation of NP-Witnesses Using an NP-Oracle. Information and Computation (formerly Information and Control) 163 .

[7]

M. BELLARE & J. ROMPEL (1994). Randomness-efficient oblivious sampling. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science , SHAFI GOLDWASSER, editor, 276-287.

[8]

S. BEN-DAVID, B. CHOR, O. GOLDREICH & M. LUBY (1990). On the theory of average case complexity. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing , 379-386.

[9]

M. BLUM & S. MICALI (1984). How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits. SIAM Journal on Computing 13 (4), 850-864.

Digital Library

[10]

N. H. BSHOUTY, R. CLEVE, R. GAVALDA, S. KANNAN & C. TAMON (1996). Oracles and queries that are sufficient for exact learning. Journal of Computer and System Sciences 52 (3), 421-433.

Digital Library

[11]

J.-Y. CAI (2001). S ₂ ^P ¿ ZPP ^NP. In Proceedings of the 42nd Annual Symposium on Foundations of Computer Science , 620-629.

[12]

R. CANETTI (1996). On BPP and the Polynomial-Time Hierarchy. Information Processing Letters 57 , 237-241.

Digital Library

[13]

J. FEIGENBAUM & L. FORTNOW (1993). Random-Self-Reducibility of Complete Sets. SIAM J. Comput. 22 (5), 994-1005.

Digital Library

[14]

L. FORTNOW & A. KLIVANS (2005). NP with Small Advice. In Proceedings of the 20th Annual IEEE Conference on Computational Complexity , 228-234.

[15]

O. GOLDREICH (1997). A Sample of Samplers - A Computational Perspective on Sampling (survey). In Electronic Colloquium on Computational Complexity, technical report TR 97-020 .

[16]

O. GOLDREICH (1998). Modern Cryptography, Probabilistic Proofs and Pseudorandomness . Springer-Verlag, Algorithms and Combinatorics.

[17]

S. GOLDWASSER, S. MICALI & C. RACKOFF (1989). The knowledge complexity of interactive proof systems. SIAM Journal of Computing 18 (1), 186-208.

Digital Library

[18]

Y. HAN, L. A. HEMASPAANDRA & T. THIERAUF (1997). Threshold Computation and Cryptographic Security. SIAM J. Comput. 26 (1), 59-78.

Digital Library

[19]

R. IMPAGLIAZZO (1995). Hard-core distributions for somewhat hard problems. In 36th Annual Symposium on Foundations of Computer Science , 538-545.

[20]

R. IMPAGLIAZZO, R. SHALTIEL & A. WIGDERSON (1999). Near-optimal conversion of hardness into pseudo-randomness. In 40th Annual Symposium on Foundations of Computer Science , 181-190.

[21]

R. IMPAGLIAZZO, R. SHALTIEL & A. WIGDERSON (2000). Extractors and pseudo-random generators with optimal seed length. In Proceedings of the thirty second annual Symposium on Theory of Computing , 1-10.

Digital Library

[22]

R. IMPAGLIAZZO & A. WIGDERSON (1997). P=BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing , 220-229.

[23]

M. R. JERRUM, L. G. VALIANT & V. V. VAZIRANI (1986). Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science 43 (2-3), 169-188.

Digital Library

[24]

V. KABANETS (2002). Derandomization: A Brief Overview. In Electronic Colloquium on Computational Complexity, technical report, TR 02-008 .

[25]

A. R. KLIVANS & D. VAN MELKEBEEK (2002). Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses. SIAM Journal on Computing 31 (5), 1501-1526.

Digital Library

[26]

P. B. MILTERSEN & N. V. VINODCHANDRAN (1999). Derandomizing Arthur-Merlin games using hitting sets. In 40th Annual Symposium on Foundations of Computer Science , 71-80.

[27]

N. NISAN & A. WIGDERSON (1994). Hardness vs Randomness. Journal of Computer and System Sciences 49 (2), 149-167.

Digital Library

[28]

A. RUSSELL & R. SUNDARAM (1998). Symmetric Alternation Captures BPP. Computational Complexity 7 (2), 152-162.

Digital Library

[29]

R. SHALTIEL & C. UMANS (2001). Simple extractors for all min-entropies and a new pseudo-random generator. In Proceedings of the 42nd Symposium on Foundations of Computer Science , 648-657.

[30]

L. STOCKMEYER (1983). The complexity of approximate counting. In Proceedings of the fifteenth annual Symposium on Theory of Computing , 118-126.

[31]

M. SUDAN, L. TREVISAN & S. VADHAN (2001). Pseudorandom generators without the XOR Lemma. Journal of Computer and System Sciences 62 , 236-266.

Digital Library

[32]

C. UMANS (2003). Pseudo-Random Generators for all Hardnesses. Journal of Computer and System Sciences 67 , 419-440.

Digital Library

[33]

L. R. WELCH & E. R. BERLEKAMP (1986). Error correction for algebraic block codes. U.S. Patent No. 4,633,470, issued December 30.

[34]

A. C. YAO (1982). Theory and Applications of Trapdoor Functions. In Proceedings of the 23th Annual Symposium on Foundations of Computer Science , 80-91.

Cited By

Shaltiel RSilbak JMohar BShinkar IO'Donnell R(2024)Explicit Codes for Poly-Size Circuits and Functions That Are Hard to Sample on Low Entropy DistributionsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649735(2028-2038)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649735
Ball MShaltiel RSilbak J(2024)Non-malleable Codes with Optimal Rate for Poly-Size CircuitsAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58737-5_2(33-54)Online publication date: 26-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-58737-5_2
Chen LTell RSaha BServedio R(2023)When Arthur Has Neither Random Coins Nor Time to Spare: Superfast Derandomization of Proof SystemsProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585215(60-69)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585215
Show More Cited By

Index Terms

Pseudorandomness for Approximate Counting and Sampling
1. Theory of computation
  1. Models of computation

Index terms have been assigned to the content through auto-classification.

Recommendations

Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games

In several settings, derandomization is known to follow from circuit lower bounds that themselves are equivalent to the existence of pseudorandom generators. This leaves open the question whether derandomization implies the circuit lower bounds that are ...
Pseudorandomness for Approximate Counting and Sampling
CCC '05: Proceedings of the 20th Annual IEEE Conference on Computational Complexity

We study computational procedures that use both randomness and nondeterminism. Examples are Arthur-Merlin games and approximate counting and sampling of NP-witnesses. The goal of this paper is to derandomize such procedures under the weakest possible ...
Randomness-Efficient Sampling within NC1

We construct a randomness-efficient averaging sampler that is computable by uniform constant-depth circuits with parity gates (i.e., in uniform AC 0 []). Our sampler matches the parameters achieved by random walks on constant-degree expander graphs, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computational Complexity

Computational Complexity Volume 15, Issue 4

December 2006

174 pages

ISSN:1016-3328

Issue’s Table of Contents

Copyright © Copyright © 2007 Birkhäuser Verlag, Basel.

Publisher

Birkhauser Verlag

Switzerland

Publication History

Published: 01 December 2006

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
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

Shaltiel RSilbak JMohar BShinkar IO'Donnell R(2024)Explicit Codes for Poly-Size Circuits and Functions That Are Hard to Sample on Low Entropy DistributionsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649735(2028-2038)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649735
Ball MShaltiel RSilbak J(2024)Non-malleable Codes with Optimal Rate for Poly-Size CircuitsAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58737-5_2(33-54)Online publication date: 26-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-58737-5_2
Chen LTell RSaha BServedio R(2023)When Arthur Has Neither Random Coins Nor Time to Spare: Superfast Derandomization of Proof SystemsProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585215(60-69)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585215
Doron DMoshkovitz DOh JZuckerman D(2022)Nearly Optimal Pseudorandomness from HardnessJournal of the ACM10.1145/355530769:6(1-55)Online publication date: 17-Nov-2022
https://dl.acm.org/doi/10.1145/3555307
Ball MDachman-Soled DLoss J(2022)(Nondeterministic) Hardness vs. Non-malleabilityAdvances in Cryptology – CRYPTO 202210.1007/978-3-031-15802-5_6(148-177)Online publication date: 15-Aug-2022
https://dl.acm.org/doi/10.1007/978-3-031-15802-5_6
Ball MDachman-Soled DKulkarni MLin HMalkin T(2019)Non-Malleable Codes Against Bounded Polynomial Time TamperingAdvances in Cryptology – EUROCRYPT 201910.1007/978-3-030-17653-2_17(501-530)Online publication date: 19-May-2019
https://dl.acm.org/doi/10.1007/978-3-030-17653-2_17
O'Donnell RSay A(2018)The Weakness of CTC Qubits and the Power of Approximate CountingACM Transactions on Computation Theory10.1145/319683210:2(1-22)Online publication date: 23-May-2018
https://dl.acm.org/doi/10.1145/3196832
Artemenko SShaltiel R(2017)Pseudorandom Generators with Optimal Seed Length for Non-Boolean Poly-Size CircuitsACM Transactions on Computation Theory10.1145/30180579:2(1-26)Online publication date: 27-Apr-2017
https://dl.acm.org/doi/10.1145/3018057
Aydınlıoğlu BMelkebeek D(2017)Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin gamesComputational Complexity10.1007/s00037-014-0095-y26:1(79-118)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1007/s00037-014-0095-y
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
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents