Local Correlation Breakers and Applications to Three-Source Extractors and Mergers

Gil Cohen

doi:10.1109/FOCS.2015.57

Local Correlation Breakers and Applications to Three-Source Extractors and Mergers

Gil Cohen

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

17 Scopus citations

Abstract

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.

Original language	English (US)
Title of host publication	Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015
Publisher	IEEE Computer Society
Pages	845-862
Number of pages	18
Volume	2015-December
ISBN (Electronic)	9781467381918
DOIs	https://doi.org/10.1109/FOCS.2015.57
State	Published - Dec 11 2015
Externally published	Yes
Event	56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015 - Berkeley, United States Duration: Oct 17 2015 → Oct 20 2015

Other

Other	56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015
Country/Territory	United States
City	Berkeley
Period	10/17/15 → 10/20/15

All Science Journal Classification (ASJC) codes

Computer Science(all)

Access to Document

10.1109/FOCS.2015.57

Cite this

@inproceedings{b3f56520341744b2be03fc0dbc693d86,

title = "Local Correlation Breakers and Applications to Three-Source Extractors and Mergers",

abstract = "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.",

author = "Gil Cohen",

year = "2015",

month = dec,

day = "11",

doi = "10.1109/FOCS.2015.57",

language = "English (US)",

volume = "2015-December",

pages = "845--862",

booktitle = "Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015",

publisher = "IEEE Computer Society",

address = "United States",

note = "56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015 ; Conference date: 17-10-2015 Through 20-10-2015",

}

Cohen, G 2015, Local Correlation Breakers and Applications to Three-Source Extractors and Mergers. in Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015. vol. 2015-December, 7354431, IEEE Computer Society, pp. 845-862, 56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, United States, 10/17/15. https://doi.org/10.1109/FOCS.2015.57

TY - GEN

T1 - Local Correlation Breakers and Applications to Three-Source Extractors and Mergers

AU - Cohen, Gil

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.

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

VL - 2015-December

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 -

Local Correlation Breakers and Applications to Three-Source Extractors and Mergers

Abstract

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this