TY - GEN
T1 - Local Correlation Breakers and Applications to Three-Source Extractors and Mergers
AU - Cohen, Gil
N1 - Publisher Copyright:
© 2015 IEEE.
PY - 2015/12/11
Y1 - 2015/12/11
N2 - We introduce and construct a pseudorandom object which we call a local correlation breaker (LCB). Informally speaking, an LCB is a function that gets as input a sequence of r (arbitrarily correlated) random variables and an independent weak-source. The output of the LCB is a sequence of r random variables with the following property. If the i'th input random variable is uniform then the i'th output variable is uniform even given a bounded number of any other output variables. That is, an LCB uses the weak-source to break local correlations between random variables. Our construction of LCBs has applications to three-source extractors, mergers with weak-seeds, and a variant of non-malleable extractors, that we introduce.
AB - We introduce and construct a pseudorandom object which we call a local correlation breaker (LCB). Informally speaking, an LCB is a function that gets as input a sequence of r (arbitrarily correlated) random variables and an independent weak-source. The output of the LCB is a sequence of r random variables with the following property. If the i'th input random variable is uniform then the i'th output variable is uniform even given a bounded number of any other output variables. That is, an LCB uses the weak-source to break local correlations between random variables. Our construction of LCBs has applications to three-source extractors, mergers with weak-seeds, and a variant of non-malleable extractors, that we introduce.
KW - mergers
KW - multi-source extractors
KW - non-malleable extractors
UR - http://www.scopus.com/inward/record.url?scp=84960452677&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84960452677&partnerID=8YFLogxK
U2 - 10.1109/FOCS.2015.57
DO - 10.1109/FOCS.2015.57
M3 - Conference contribution
AN - SCOPUS:84960452677
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 845
EP - 862
BT - Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015
PB - IEEE Computer Society
T2 - 56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015
Y2 - 17 October 2015 through 20 October 2015
ER -