## 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 | |

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 | United States |

City | Berkeley |

Period | 10/17/15 → 10/20/15 |

## All Science Journal Classification (ASJC) codes

- Computer Science(all)