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

Learn More →

AC0 Unpredictability

AC0 Unpredictability We prove that for every distribution D on n bits with Shannon entropy n a, at most O(2da logd+1g)/5 of the bits Di can be predicted with advantage by an AC0 circuit of size g and depth D that is a function of all of the bits of D except Di. This answers a question by Meir and Wigderson, who proved a corresponding result for decision trees. We also show that there are distributions D with entropy n O(1) such that any subset of O(n/ log n) bits of D on can be distinguished from uniform by a circuit of depth 2 and size poly(n). This separates the notions of predictability and distinguishability in this context. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

AC0 Unpredictability

Download PDF
8 pages

Loading next page...
 
/lp/association-for-computing-machinery/ac0-unpredictability-QvKJ0TMgo0
Publisher
Association for Computing Machinery
Copyright
Copyright © 2021 ACM
ISSN
1942-3454
eISSN
1942-3462
DOI
10.1145/3442362
Publisher site
See Article on Publisher Site

Abstract

We prove that for every distribution D on n bits with Shannon entropy n a, at most O(2da logd+1g)/5 of the bits Di can be predicted with advantage by an AC0 circuit of size g and depth D that is a function of all of the bits of D except Di. This answers a question by Meir and Wigderson, who proved a corresponding result for decision trees. We also show that there are distributions D with entropy n O(1) such that any subset of O(n/ log n) bits of D on can be distinguished from uniform by a circuit of depth 2 and size poly(n). This separates the notions of predictability and distinguishability in this context.

Journal

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

Published: Mar 17, 2021

Keywords: AC0

References

  • Deterministic simulation of probabilistic constant-depth circuits
    Ajtai, Miklos; Wigderson, Avi
  • Random oracles and non-uniformity
    Coretti, Sandro; Dodis, Yevgeniy; Guo, Siyao; Steinberger, John
  • Elements in Information Theory
    Cover, Thomas; Thomas, Joy
  • Fixing cracks in the concrete: Random oracles with auxiliary input, revisited
    Dodis, Yevgeniy; Guo, Siyao; Katz, Jonathan
  • Communication complexity towards lower bounds on circuit depth
    Edmonds, Jeff; Impagliazzo, Russell; Rudich, Steven; Sgall, Jiri
  • On beating the hybrid argument
    Fefferman, Bill; Shaltiel, Ronen; Umans, Christopher; Viola, Emanuele
  • Foundations of Cryptography: Volume 1, Basic Tools
    Goldreich, Oded
  • Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs
    Grinberg, Aryeh; Shaltiel, Ronen; Viola, Emanuele
  • On the correlation of parity and small-depth circuits
    Håstad, Johan
  • Probability inequalities for sums of bounded random variables
    Hoeffding, Wassily
  • Prediction from partial information and hindsight, with application to circuit lower bounds
    Meir, Or; Wigderson, Avi
  • A parallel repetition theorem
    Raz, Ran
  • Hardness amplification proofs require majority
    Shaltiel, Ronen; Viola, Emanuele
  • Prediction from partial information and hindsight, an alternative proof
    Smal, Alexander; Talebanfard, Navid
  • A note on approximate counting for k-DNF
    Trevisan, Luca
  • Random oracles and auxiliary input
    Unruh, Dominique
  • Theory and applications of trapdoor functions
    Yao, Andrew