Almost Chor-Goldreich sources and adversarial random walks. (English) Zbl 07844567
Saha, Barna (ed.) et al., Proceedings of the 55th annual ACM SIGACT symposium on theory of computing, STOC ’23, Orlando, FL, USA, June 20–23, 2023. New York, NY: Association for Computing Machinery (ACM). 1-9 (2023).
MSC:
| 68Qxx | Theory of computing |
Keywords:
Santha-Vazirani sources; condensers; expander graphs; extractors; random walks; randomized algorithmReferences:
| [1] | Noga Alon and Michael Capalbo. 2002. Explicit unique-neighbor expanders. In Proceedings of the 43rd Annual Symposium on Foundations of Computer Science (FOCS). 73-79. |
| [2] | Nir Aviv and Amnon Ta-Shma. 2019. On the entropy loss and gap of condensers. ACM Transactions on Computation Theory (TOCT), 11, 3 (2019), 1-14. · Zbl 1497.68167 |
| [3] | Marshall Ball, Oded Goldreich, and Tal Malkin. 2022. Randomness extraction from somewhat dependent sources. In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS). · Zbl 07711596 |
| [4] | Boaz Barak, Yevgeniy Dodis, Hugo Krawczyk, Olivier Pereira, Krzysztof Pietrzak, François-Xavier Standaert, and Yu Yu. 2011. Leftover hash lemma, revisited. In Annual Cryptology Conference. 1-20. · Zbl 1287.94047 |
| [5] | Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, and Avi Wigderson. 2010. Simulating independence: New constructions of condensers, ramsey graphs, dispersers, and extractors. Journal of the ACM (JACM), 57, 4 (2010), 20. · Zbl 1327.68172 |
| [6] | Salman Beigi, Omid Etesami, and Amin Gohari. 2017. Deterministic Randomness Extraction from Generalized and Distributed Santha-Vazirani Sources. SIAM J. Comput., 46, 1 (2017), 1-36. · Zbl 1394.68147 |
| [7] | Avraham Ben-Aroya, Gil Cohen, Dean Doron, and Amnon Ta-Shma. 2019. Two-source condensers with low error and small entropy gap via entropy-resilient functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). · Zbl 07650110 |
| [8] | Avraham Ben-Aroya, Dean Doron, and Amnon Ta-Shma. 2019. An efficient reduction from two-source to nonmalleable extractors: achieving near-logarithmic min-entropy. SIAM J. Comput., STOC17-31. · Zbl 07516619 |
| [9] | Radu Berinde, Anna C. Gilbert, Piotr Indyk, Howard Karloff, and Martin J. Strauss. 2008. Combining geometry and combinatorics: A unified approach to sparse signal recovery. In Proceedings of the 46th Annual Allerton Conference on Communication, Control, and Computing. 798-805. |
| [10] | Michael Capalbo, Omer Reingold, Salil Vadhan, and Avi Wigderson. 2002. Randomness conductors and constant-degree lossless expanders. In Proceedings of the 34th Annual Symposium on Theory of Computing (STOC). ACM, 659-668. · Zbl 1192.68475 |
| [11] | Eshan Chattopadhyay and Jesse Goodman. 2022. Improved extractors for small-space sources. In Proceedings of the 62nd Annual Symposium on Foundations of Computer Science (FOCS). 610-621. |
| [12] | Eshan Chattopadhyay, Jesse Goodman, and Jyun-Jie Liao. 2022. Affine extractors for almost logarithmic entropy. In Proceedings of the 62nd Annual Symposium on Foundations of Computer Science (FOCS). 622-633. |
| [13] | Lijie Chen and Roei Tell. 2021. Simple and fast derandomization from very hard functions: eliminating randomness at almost no cost. In Proceedings of the 53rd Annual Symposium on Theory of Computing (STOC). ACM, 283-291. · Zbl 07765171 |
| [14] | Xue Chen, Kuan Cheng, Xin Li, and Minghui Ouyang. 2022. Improved Decoding of Expander Codes. In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS). · Zbl 07829275 |
| [15] | Benny Chor and Oded Goldreich. 1988. Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM J. Comput., 17, 2 (1988), 230-261. · Zbl 0644.94008 |
| [16] | Anindya De and Thomas Watson. 2012. Extractors and lower bounds for locally samplable sources. ACM Transactions on Computation Theory (TOCT), 4, 1 (2012), 1-21. · Zbl 1322.65009 |
| [17] | Domingos Dellamonica Jr. and Yoshiharu Kohayakawa. 2008. An algorithmic Friedman-Pippenger theorem on tree embeddings and applications. The Electronic Journal of Combinatorics, R127-R127. · Zbl 1165.05318 |
| [18] | Yevgeniy Dodis, Siyao Guo, Noah Stephens-Davidowitz, and Zhiye Xie. 2021. No Time to Hash: On Super-Efficient Entropy Accumulation. In CRYPTO (Lecture Notes in Computer Science, Vol. 12828). Springer, 548-576. · Zbl 1489.94096 |
| [19] | Yevgeniy Dodis, Siyao Guo, Noah Stephens-Davidowitz, and Zhiye Xie. 2021. Online linear extractors for independent sources. In Proceedings of the 2nd Conference on Information-Theoretic Cryptography (ITC). · Zbl 1517.94094 |
| [20] | Yevgeniy Dodis, Krzysztof Pietrzak, and Daniel Wichs. 2014. Key derivation without entropy waste. In Advances in Cryptology-EUROCRYPT 2014. Springer, 93-110. · Zbl 1326.94085 |
| [21] | Yevgeniy Dodis, Thomas Ristenpart, and Salil Vadhan. 2012. Randomness condensers for efficiently samplable, seed-dependent sources. In Theory of Cryptography Conference. 618-635. · Zbl 1304.94047 |
| [22] | Yevgeniy Dodis and Yu Yu. 2013. Overcoming weak expectations. In Theory of Cryptography Conference. 1-22. · Zbl 1296.94107 |
| [23] | Dean Doron, Dana Moshkovitz, Justin Oh, and David Zuckerman. 2020. Nearly optimal pseudorandomness from hardness. In Proceedings of the 61st Annual Symposium on Foundations of Computer Science (FOCS). 1057-1068. |
| [24] | Dean Doron, Dana Moshkovitz, Justin Oh, and David Zuckerman. 2022. Almost Chor-Goldreich Sources and Adversarial Random Walks. In Electronic Colloquium on Computational Complexity (ECCC). |
| [25] | Zeev Dvir. 2012. Extractors for varieties. computational complexity, 21, 4 (2012), 515-572. · Zbl 1280.68293 |
| [26] | Dmitry Gavinsky and Pavel Pudlák. 2020. Santha-Vazirani sources, deterministic condensers and very strong extractors. Theory of Computing Systems, 64, 6 (2020), 1140-1154. · Zbl 1476.68081 |
| [27] | Oded Goldreich and Salil Vadhan. 1999. Comparing entropies in statistical zero knowledge with applications to the structure of SZK. In Proceedings. Fourteenth Annual IEEE Conference on Computational Complexity (Formerly: Structure in Complexity Theory Conference)(Cat. No. 99CB36317). 54-73. |
| [28] | Oded Goldreich and Avi Wigderson. 1997. Tiny families of functions with random properties: A quality-size trade-off for hashing. Random Structures & Algorithms, 11, 4 (1997), 315-343. · Zbl 0891.60010 |
| [29] | Venkatesan Guruswami, Christopher Umans, and Salil Vadhan. 2009. Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes. Journal of the ACM (JACM), 56, 4 (2009), 20. · Zbl 1325.68169 |
| [30] | Jesse Kamp, Anup Rao, Salil Vadhan, and David Zuckerman. 2006. Deterministic extractors for small-space sources. In Proceedings of the 38th Annual Symposium on Theory of Computing (STOC). ACM, 691-700. · Zbl 1301.68193 |
| [31] | Ting-Chun Lin and Min-Hsiu Hsieh. 2022. Good quantum LDPC codes with linear time decoder from lossless expanders. arXiv preprint arXiv:2203.03581. |
| [32] | Chi-Jen Lu, Omer Reingold, Salil Vadhan, and Avi Wigderson. 2003. Extractors: Optimal up to constant factors. In Proceedings of the 35th Annual Symposium on Theory of computing (STOC). 602-611. · Zbl 1192.68859 |
| [33] | Noam Nisan and David Zuckerman. 1996. Randomness is Linear in Space. J. Comput. System Sci., 52, 1 (1996), 43-52. · Zbl 0846.68041 |
| [34] | Jaikumar Radhakrishnan and Amnon Ta-Shma. 2000. Bounds for dispersers, extractors, and depth-two superconcentrators. SIAM Journal on Discrete Mathematics, 13, 1 (2000), 2-24. · Zbl 1023.94025 |
| [35] | Ran Raz and Omer Reingold. 1999. On recycling the randomness of states in space bounded computation. In Proceedings of the 61st Annual Symposium on Theory of Computing (STOC). ACM, 159-168. · Zbl 1345.68135 |
| [36] | Omer Reingold, Ronen Shaltiel, and Avi Wigderson. 2006. Extracting randomness via repeated condensing. SIAM J. Comput., 35, 5 (2006), 1185-1209. · Zbl 1100.68030 |
| [37] | Omer Reingold, Salil Vadhan, and Avi Wigderson. 2002. Entropy waves, the zig-zag graph product, and new constant-degree expanders. Annals of Mathematics, 157-187. · Zbl 1008.05101 |
| [38] | Omer Reingold, Salil Vadhan, and Avi Wigderson. 2004. A note on extracting randomness from Santha-Vazirani sources. Manuscript. In Electronic Colloquium on Computational Complexity (ECCC). |
| [39] | Miklos Santha and Umesh V. Vazirani. 1986. Generating quasi-random sequences from semi-random sources. J. Comput. System Sci., 33, 1 (1986), 75-87. · Zbl 0612.94004 |
| [40] | Ronen Shaltiel and Emanuele Viola. 2022. On Hardness Assumptions Needed for “Extreme High-End” PRGs and Fast Derandomization. In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS). · Zbl 1214.68175 |
| [41] | Aravind Srinivasan and David Zuckerman. 1999. Computing with very weak random sources. SIAM J. Comput., 28, 4 (1999), 1433-1459. · Zbl 0932.60008 |
| [42] | Amnon Ta-Shma, Christopher Umans, and David Zuckerman. 2007. Lossless condensers, unbalanced expanders, and extractors. Combinatorica, 27 (2007), 213-240. · Zbl 1164.68004 |
| [43] | Luca Trevisan and Salil Vadhan. 2000. Extracting randomness from samplable distributions. In Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2000). 32-42. |
| [44] | Emanuele Viola. 2014. Extractors for circuit sources. SIAM J. Comput., 43, 2 (2014), 655-672. · Zbl 1301.68195 |
| [45] | David Zuckerman. 1990. General weak random sources. In Proceedings of the 31st Annual Symposium on Foundations of Computer Science (FOCS). 534-543. |
| [46] | David Zuckerman. 2007. Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number. Theory of Computing, 3 (2007), 103-128. · Zbl 1213.68322 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
