Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
A new model for weak random physical sources is presented. The new model strictly generalizes previous models (e.g. the Santha and Vazirani model [26]). The sources considered output strings according to probability distributions in which no single string is too probable. The new model provides a fr...
| Main Authors: | , |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149092 |
| _version_ | 1826203879302234112 |
|---|---|
| author | Chor, Benny Goldreich, Oded |
| author_facet | Chor, Benny Goldreich, Oded |
| author_sort | Chor, Benny |
| collection | MIT |
| description | A new model for weak random physical sources is presented. The new model strictly generalizes previous models (e.g. the Santha and Vazirani model [26]). The sources considered output strings according to probability distributions in which no single string is too probable. The new model provides a fruitful viewpoint on problems studied previously as: 1) Extracting almost perfect bits from sources of weak randomness: the question of possibility as well as the question of efficiency of such extraction schemes are addressed. 2) Probabilistic Communication Complexity: it is shown that most functions have linear communication complexity in a very strong probabilistic sense. 3) Robustness of BPP with respect to sources of weak randomness (generalizing a result of Vazirani and Vazirani [29]). |
| first_indexed | 2024-09-23T12:44:48Z |
| id | mit-1721.1/149092 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T12:44:48Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1490922023-03-30T03:43:33Z Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity Chor, Benny Goldreich, Oded A new model for weak random physical sources is presented. The new model strictly generalizes previous models (e.g. the Santha and Vazirani model [26]). The sources considered output strings according to probability distributions in which no single string is too probable. The new model provides a fruitful viewpoint on problems studied previously as: 1) Extracting almost perfect bits from sources of weak randomness: the question of possibility as well as the question of efficiency of such extraction schemes are addressed. 2) Probabilistic Communication Complexity: it is shown that most functions have linear communication complexity in a very strong probabilistic sense. 3) Robustness of BPP with respect to sources of weak randomness (generalizing a result of Vazirani and Vazirani [29]). 2023-03-29T14:26:37Z 2023-03-29T14:26:37Z 1986-09 https://hdl.handle.net/1721.1/149092 MIT-LCS-TM-283 application/pdf |
| spellingShingle | Chor, Benny Goldreich, Oded Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity |
| title | Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity |
| title_full | Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity |
| title_fullStr | Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity |
| title_full_unstemmed | Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity |
| title_short | Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity |
| title_sort | unbiased bits from sources of weak randomness and probabilistic communication complexity |
| url | https://hdl.handle.net/1721.1/149092 |
| work_keys_str_mv | AT chorbenny unbiasedbitsfromsourcesofweakrandomnessandprobabilisticcommunicationcomplexity AT goldreichoded unbiasedbitsfromsourcesofweakrandomnessandprobabilisticcommunicationcomplexity |