Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

The Coin Problem for Product Tests

The Coin Problem for Product Tests Let Xm, be the distribution over m bits X1,,Xm where the Xi are independent and each Xi equals 1 with probability (1)/2 and 0 with probability (1 )/2. We consider the smallest value of such that the distributions Xm, and Xm, 0 can be distinguished with constant advantage by a function f : 0,1m S, which is the product of k functions f1,f2,, fk on disjoint inputs of n bits, where each fi : 0,1n S and m = nk. We prove that = (1/√n log k) if S = [1,1], while = (1/√nk) if S is the set of unit-norm complex numbers. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

The Coin Problem for Product Tests

Download PDF
10 pages

Loading next page...
 
/lp/association-for-computing-machinery/the-coin-problem-for-product-tests-xtnCE1tJWj
Publisher
Association for Computing Machinery
Copyright
Copyright © 2018 ACM
ISSN
1942-3454
eISSN
1942-3462
DOI
10.1145/3201787
Publisher site
See Article on Publisher Site

Abstract

Let Xm, be the distribution over m bits X1,,Xm where the Xi are independent and each Xi equals 1 with probability (1)/2 and 0 with probability (1 )/2. We consider the smallest value of such that the distributions Xm, and Xm, 0 can be distinguished with constant advantage by a function f : 0,1m S, which is the product of k functions f1,f2,, fk on disjoint inputs of n bits, where each fi : 0,1n S and m = nk. We prove that = (1/√n log k) if S = [1,1], while = (1/√nk) if S is the set of unit-norm complex numbers.

Journal

ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery

Published: Jun 8, 2018

Keywords: Coin problem

References

  • BQP and the polynomial hierarchy
    Aaronson, Scott
  • Advice coins for classical and quantum computation
    Aaronson, Scott; Drucker, Andrew
  • Σ11-formulae on finite structures
    Ajtai, Miklós
  • Deterministic simulation in LOGSPACE
    Ajtai, Miklós; Komlós, János; Szemerédi, Endre
  • Discrepancy sets and pseudorandom generators for combinatorial rectangles
    Armoni, Roy; Saks, Michael E.; Wigderson, Avi; Zhou, Shiyu
  • The coin problem, and pseudorandomness for branching programs
    Brody, Joshua; Verbin, Elad
  • Efficient multiparty protocols via log-depth threshold formulae (extended abstract)
    Cohen, Gil; Damgård, Ivan Bjerre; Ishai, Yuval; Kölker, Jonas; Miltersen, Peter Bro; Raz, Ran; Rothblum, Ron D.
  • Two sides of the coin problem
    Cohen, Gil; Ganor, Anat; Raz, Ran
  • Efficient approximation of product distributions
    Even, Guy; Goldreich, Oded; Luby, Michael; Nisan, Noam; Velickovic, Boban
  • Pseudorandomness via the discrete fourier transform
    Gopalan, Parikshit; Kane, Daniel; Meka, Raghu
  • Better pseudorandom generators from milder pseudorandom restrictions
    Gopalan, Parikshit; Meka, Raghu; Reingold, Omer; Trevisan, Luca; Vadhan, Salil
  • Inequalities and tail bounds for elementary symmetric polynomials
    Gopalan, Parikshit; Yehudayoff, Amir
  • Bounded independence plus noise fools products
    Haramaty, Elad; Lee, Chin Ho; Viola, Emanuele
  • Learning with finite memory
    Hellman, Martin E.; Cover, Thomas M.
  • Pseudorandomness for network algorithms
    Impagliazzo, Russell; Nisan, Noam; Wigderson, Avi
  • Improved pseudorandom generators for combinatorial rectangles
    Lu, Chi-Jen
  • Pseudorandom generators for space-bounded computation
    Nisan, Noam
  • Randomness is linear in space
    Nisan, Noam; Zuckerman, David
  • Hardness amplification proofs require majority
    Shaltiel, Ronen; Viola, Emanuele
  • The Cauchy-Schwarz Master Class
    Steele, J. Michael
  • The distinguishability of product distributions by read-once branching programs
    Steinberger, John P.
  • Short monotone formulae for the majority function
    Valiant, Leslie G.
  • Randomness buys depth for approximate counting
    Viola, Emanuele
  • Pseudorandom generators for combinatorial checkerboards
    Watson, Thomas