Document Open Access Logo

Space Pseudorandom Generators by Communication Complexity Lower Bounds

Authors Anat Ganor, Ran Raz

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2014.692.pdf
  • Filesize: 491 kB
  • 12 pages

Document Identifiers

Author Details

Anat Ganor
Ran Raz

Cite As Get BibTex

Anat Ganor and Ran Raz. Space Pseudorandom Generators by Communication Complexity Lower Bounds. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 692-703, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.692

Abstract

In 1989, Babai, Nisan and Szegedy gave a construction of a pseudorandom generator for logspace, based on lower bounds for multiparty communication complexity. The seed length of their pseudorandom generator was relatively large, because the best lower bounds for multiparty communication complexity are relatively weak. Subsequently, pseudorandom generators for logspace with seed length O(log^2 n) were given by Nisan, and Impagliazzo, Nisan and Wigderson.

In this paper, we show how to use the pseudorandom generator construction of Babai, Nisan and Szegedy to obtain a third construction of a pseudorandom generator with seed length O(log^2 n), achieving the same parameters as Nisan, and Impagliazzo, Nisan and Wigderson. We achieve this by concentrating on protocols in a restricted model of multiparty communication complexity that we call the conservative one-way unicast model and is based on the conservative one-way model of Damm, Jukna and Sgall. We observe that bounds in the conservative one-way unicast model (rather than the standard Number On the Forehead model) are sufficient for the pseudorandom generator construction of Babai, Nisan and Szegedy to work.

Roughly speaking, in a conservative one-way unicast communication protocol, the players speak in turns, one after the other in a fixed order, and every message is visible only to the next player. Moreover, before the beginning of the protocol, each player only knows the inputs of the players that speak after she does and a certain function of the inputs of the players that speak before she does. We prove a lower bound for the communication complexity of conservative one-way unicast communication protocols that compute a family of functions obtained by compositions of strong extractors. Our final pseudorandom generator construction is related to, but different from the constructions of Nisan, and Impagliazzo, Nisan and Wigderson.

Subject Classification

Keywords
  • Communication complexity
  • Logspace
  • Pseudorandom generator

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Miklos Ajtai, Janos Komlos, and Endre Szemeredi. Deterministic simulation in logspace. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC'87, pages 132-140, New York, NY, USA, 1987. ACM. Google Scholar
  2. László Babai, Noam Nisan, and Mario Szegedy. Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs. J. Comput. Syst. Sci., 45(2):204-232, 1992. Google Scholar
  3. Andrej Bogdanov, Zeev Dvir, Elad Verbin, and Amir Yehudayoff. Pseudorandomness for width-2 branching programs. Theory of Computing, 9:283-293, 2013. Google Scholar
  4. Mark Braverman, Faith Ellen, Rotem Oshman, Toniann Pitassi, and Vinod Vaikuntanathan. Tight bounds for set disjointness in the message passing model. CoRR, abs/1305.4696, 2013. Google Scholar
  5. Mark Braverman, Anup Rao, Ran Raz, and Amir Yehudayoff. Pseudorandom generators for regular branching programs. In FOCS, pages 40-47, 2010. Google Scholar
  6. Joshua Brody and Elad Verbin. The coin problem and pseudorandomness for branching programs. In FOCS, pages 30-39, 2010. Google Scholar
  7. Amit Chakrabarti. Lower bounds for multi-player pointer jumping. In IEEE Conference on Computational Complexity, pages 33-45, 2007. Google Scholar
  8. Carsten Damm, Stasys Jukna, and Jiri Sgall. Some bounds on multiparty communication complexity of pointer jumping. Computational Complexity, 7(2):109-127, 1998. Google Scholar
  9. Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, and Adam Smith. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. SIAM J. Comput., 38(1):97-139, 2008. Google Scholar
  10. Yevgeniy Dodis and Daniel Wichs. Non-malleable extractors and symmetric key cryptography from weak secrets. In STOC, pages 601-610, 2009. Google Scholar
  11. Stefan Dziembowski and Krzysztof Pietrzak. Intrusion-resilient secret sharing. In FOCS, pages 227-237, 2007. Google Scholar
  12. Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. J. ACM, 32(2):374-382, April 1985. Google Scholar
  13. Oded Goldreich and Avi Wigderson. Tiny families of functions with random properties: A quality-size trade-off for hashing. Random Struct. Algorithms, 11(4):315-343, 1997. Google Scholar
  14. Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, and Salil P. Vadhan. Better pseudorandom generators from milder pseudorandom restrictions. In FOCS, pages 120-129, 2012. Google Scholar
  15. Russell Impagliazzo, Noam Nisan, and Avi Wigderson. Pseudorandomness for network algorithms. In STOC, pages 356-364, 1994. Google Scholar
  16. Richard M. Karp, Christian Schindelhauer, Scott J. Shenker, and Berthold Vocking. Randomized rumor spreading. In In IEEE Symposium on Foundations of Computer Science, pages 565-574, 2000. Google Scholar
  17. David Kempe, Alin Dobra, and Johannes Gehrke. Gossip-based computation of aggregate information. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS'03, pages 482-, Washington, DC, USA, 2003. IEEE Computer Society. Google Scholar
  18. Michal Koucky, Prajakta Nimbhorkar, and Pavel Pudlak. Pseudorandom generators for group products. Electronic Colloquium on Computational Complexity (ECCC), 17:113, 2010. Google Scholar
  19. Noam Nisan. Pseudorandom generators for space-bounded computation. Combinatorica, 12(4):449-461, 1992. Google Scholar
  20. Noam Nisan and Amnon Ta-Shma. Extracting randomness: A survey and new constructions. J. Comput. Syst. Sci., 58(1):148-173, 1999. Google Scholar
  21. Noam Nisan and David Zuckerman. More deterministic simulation in logspace. In STOC, pages 235-244, 1993. Google Scholar
  22. Noam Nisan and David Zuckerman. Randomness is linear in space. J. Comput. Syst. Sci., 52(1):43-52, 1996. Google Scholar
  23. Ran Raz and Omer Reingold. On recycling the randomness of states in space bounded computation. In STOC, pages 159-168, 1999. Google Scholar
  24. Omer Reingold, Thomas Steinke, and Salil P. Vadhan. Pseudorandomness for regular branching programs via fourier analysis. CoRR, abs/1306.3004, 2013. Google Scholar
  25. Michael E. Saks and Shiyu Zhou. Bp_hspace(s) ⊆ dspace(s^3/2). J. Comput. Syst. Sci., 58(2):376-403, 1999. Google Scholar
  26. Walter J. Savitch. Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci., 4(2):177-192, 1970. Google Scholar
  27. Ronen Shaltiel. Recent developments in explicit constructions of extractors. Bulletin of the EATCS, 77:67-95, 2002. Google Scholar
  28. Salil P. Vadhan. Pseudorandomness. Foundations and Trends in Theoretical Computer Science, 7(1-3):1-336, 2012. Google Scholar
  29. Instructor: Leo Reyzin Scribers: Drew Wolpert and Sophia Yakoubov. Alternating extractors and leakage-resilient stream ciphers. New Developments in Cryptography, MIT, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact