TY - GEN
T1 - Space pseudorandom generators by communication complexity lower bounds
AU - Ganor, Anat
AU - Raz, Ran
N1 - Publisher Copyright:
© Flavio Chierichetti, Anirban Dasgupta, Ravi Kumar, and Silvio Lattanzi.
PY - 2014/9/1
Y1 - 2014/9/1
N2 - In 1989, Babai, Nisan and Szegedy [2] 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 2Θ(√log n), because the best lower bounds for multiparty communication complexity are relatively weak. Subsequently, pseudorandom generators for logspace with seed length O(log2 n) were given by [19] and [15]. In this paper, we show how to use the pseudorandom generator construction of [2] to obtain a third construction of a pseudorandom generator with seed length O(log2 n), achieving the same parameters as [19] and [15]. 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 [8]. 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 [2] 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 [19] and [15].
AB - In 1989, Babai, Nisan and Szegedy [2] 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 2Θ(√log n), because the best lower bounds for multiparty communication complexity are relatively weak. Subsequently, pseudorandom generators for logspace with seed length O(log2 n) were given by [19] and [15]. In this paper, we show how to use the pseudorandom generator construction of [2] to obtain a third construction of a pseudorandom generator with seed length O(log2 n), achieving the same parameters as [19] and [15]. 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 [8]. 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 [2] 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 [19] and [15].
KW - Communication complexity
KW - Logspace
KW - Pseudorandom generator
UR - http://www.scopus.com/inward/record.url?scp=84920155983&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84920155983&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.APPROX-RANDOM.2014.692
DO - 10.4230/LIPIcs.APPROX-RANDOM.2014.692
M3 - Conference contribution
AN - SCOPUS:84920155983
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 692
EP - 703
BT - Leibniz International Proceedings in Informatics, LIPIcs
A2 - Jansen, Klaus
A2 - Rolim, Jose D. P.
A2 - Devanur, Nikhil R.
A2 - Moore, Cristopher
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2014 and the 18th International Workshop on Randomization and Computation, RANDOM 2014
Y2 - 4 September 2014 through 6 September 2014
ER -