Optimality of Correlated Sampling Strategies

by Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald L. Rivest, and Madhu Sudan

Theory of Computing, Volume 16(12), pp. 1-18, 2020

Bibliography with links to cited articles

[1]   Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev, and David Steurer: Rounding parallel repetitions of unique games. In Proc. 49th FOCS, pp. 374–383. IEEE Comp. Soc., 2008. [doi:10.1109/FOCS.2008.55]

[2]   Andrei Z. Broder: On the resemblance and containment of documents. In Proc. Compression and Complexity of Sequences (SEQUENCES’97), pp. 21–29. IEEE Comp. Soc., 1997. [doi:10.1109/SEQUEN.1997.666900]

[3]   Moses S. Charikar: Similarity estimation techniques from rounding algorithms. In Proc. 34th STOC, pp. 380–388. ACM Press, 2002. [doi:10.1145/509907.509965]

[4]   Sreenivas Gollapudi and Rina Panigrahy: A dictionary for approximate string search and longest prefix search. In 15th Internat. Conf. on Information and Knowledge Managment (CIKM’06), pp. 768–775. ACM Press, 2006. [doi:10.1145/1183614.1183723]

[5]   Bernhard Haeupler, Mark Manasse, and Kunal Talwar: Consistent weighted sampling made fast, small, and easy, 2014. [arXiv:1410.4266]

[6]   Thomas Holenstein: Parallel repetition: simplifications and the no-signaling case. Theory of Computing, 5(8):141–172, 2009. Preliminary version in STOC’07. [doi:10.4086/toc.2009.v005a008]

[7]   Jon Kleinberg and √Čva Tardos: Approximation algorithms for classification problems with pairwise relationships: Metric labeling and Markov random fields. J. ACM, 49(5):616–639, 2002. Preliminary version in FOCS’99. [doi:10.1145/585265.585268]

[8]   Jacobus Hendricus van Lint and Richard Michael Wilson: A Course in Combinatorics. Cambridge Univ. Press, 2001. [doi:10.1017/CBO9780511987045]

[9]   Mark Manasse, Frank McSherry, and Kunal Talwar: Consistent weighted sampling. Technical Report MSR-TR 2010-73, 2010.

[10]   Udi Manber: Finding similar files in a large file system. In USENIX Winter Tech. Conf. (WTEC’94), pp. 1–10. USENIX Assoc., 1994. Link at ACM DL.  Available as U. Arizona CS TR93-33.

[11]   Michael Mitzenmacher and Eli Upfal: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge Univ. Press, 2005.

[12]   Anup Rao: Parallel repetition in projection games and a concentration bound. SIAM J. Comput., 40(6):1871–1891, 2011. Preliminary version in STOC’08. [doi:10.1137/080734042]

[13]   Ronald L. Rivest: Symmetric Encryption via Keyrings and ECC, 2016. Slide presentation, available on author’s home page.

[14]   Hermann Thorisson: Coupling, Stationarity, and Regeneration. Springer, 2000.