Optimal Hitting Sets for Combinatorial Shapes
by Aditya Bhaskara, Devendra Desai, and Srikanth Srinivasan
Theory of Computing, Volume 9(13), pp. 441-470, 2013
Bibliography with links to cited articles
[1] Romas Aleliunas, Richard M. Karp, Richard J. Lipton, László Lovász, and Charles Rackoff: Random walks, universal traversal sequences, and the complexity of maze problems. In Proc. 20th FOCS, pp. 218–223. IEEE Comp. Soc. Press, 1979. [doi:10.1109/SFCS.1979.34]
[2] Noga Alon, László Babai, and Alon Itai: A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms, 7(4):567–583, 1986. [doi:10.1016/0196-6774(86)90019-2]
[3] Noga Alon, Uriel Feige, Avi Wigderson, and David Zuckerman: Derandomized graph products. Comput. Complexity, 5(1):60–75, 1995. [doi:10.1007/BF01277956]
[4] Noga Alon, Oded Goldreich, Johan Håstad, and René Peralta: Simple construction of almost k-wise independent random variables. Random Structures & Algorithms, 3(3):289–304, 1992. Preliminary version in FOCS’90. [doi:10.1002/rsa.3240030308]
[5] Noga Alon, Raphael Yuster, and Uri Zwick: Color-coding. J. ACM, 42(4):844–856, 1995. Preliminary version in STOC’94. [doi:10.1145/210332.210337]
[6] Roy Armoni, Michael E. Saks, Avi Wigderson, and Shiyu Zhou: Discrepancy sets and pseudorandom generators for combinatorial rectangles. In Proc. 37th FOCS, pp. 412–421. IEEE Comp. Soc. Press, 1996. [doi:10.1109/SFCS.1996.548500]
[7] Avrim Blum, Adam Kalai, and Hal Wasserman: Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM, 50(4):506–519, 2003. Preliminary version in STOC’00. [doi:10.1145/792538.792543]
[8] Guy Even, Oded Goldreich, Michael Luby, Noam Nisan, and Boban Veliković: Efficient approximation of product distributions. Random Structures & Algorithms, 13(1):1–16, 1998. Preliminary version in STOC’92. [doi:10.1002/(SICI)1098-2418(199808)13:1¡1::AID-RSA1¿3.0.CO;2-W]
[9] William Feller: An Introduction to Probability Theory and its Applications, Vol 2. Wiley, 1971.
[10] Michael L. Fredman, János Komlós, and Endre Szemerédi: Storing a sparse table with 0(1) worst case access time. J. ACM, 31(3):538–544, 1984. Preliminary version in FOCS’82. [doi:10.1145/828.1884]
[11] Parikshit Gopalan, Raghu Meka, Omer Reingold, and David Zuckerman: Pseudorandom generators for combinatorial shapes. In Proc. 43rd STOC, pp. 253–262. ACM Press, 2011. [doi:10.1145/1993636.1993671]
[12] Shlomo Hoory, Nathan Linial, and Avi Wigderson: Expander graphs and their applications. Bulletin of the AMS, 43(4):439–561, 2006. [doi:10.1090/S0273-0979-06-01126-8]
[13] Russell Impagliazzo and Avi Wigderson: P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In Proc. 29th STOC, pp. 220–229. ACM Press, 1997. [doi:10.1145/258533.258590]
[14] Michal Koucký, Prajakta Nimbhorkar, and Pavel Pudlák: Pseudorandom generators for group products: extended abstract. In Proc. 43rd STOC, pp. 263–272. ACM Press, 2011. [doi:10.1145/1993636.1993672]
[15] Nathan Linial, Michael Luby, Michael E. Saks, and David Zuckerman: Efficient construction of a small hitting set for combinatorial rectangles in high dimension. Combinatorica, 17(2):215–234, 1997. Preliminary version in STOC’93. [doi:10.1007/BF01200907]
[16] Shachar Lovett, Omer Reingold, Luca Trevisan, and Salil P. Vadhan: Pseudorandom bit generators that fool modular sums. In Proc. 13th Internat. Workshop on Randomization and Computation (RANDOM’09), pp. 615–630. Springer, 2009. [doi:10.1007/978-3-642-03685-9_46]
[17] Chi-Jen Lu: Improved pseudorandom generators for combinatorial rectangles. Combinatorica, 22(3):417–434, 2002. Preliminary version in ICALP’98. [doi:10.1007/s004930200021]
[18] Raghu Meka and David Zuckerman: Small-bias spaces for group products. In Proc. 13th Internat. Workshop on Randomization and Computation (RANDOM’09), pp. 658–672, 2009. [doi:10.1007/978-3-642-03685-9_49]
[19] Robin A. Moser and Gábor Tardos: A constructive proof of the general Lovász Local Lemma. J. ACM, 57(2):11, 2010. Preliminary version in STOC’09. [doi:10.1145/1667053.1667060]
[20] Joseph Naor and Moni Naor: Small-bias probability spaces: Efficient constructions and applications. SIAM J. Comput., 22(4):838–856, 1993. Preliminary version in STOC’90. [doi:10.1137/0222053]
[21] Noam Nisan: Pseudorandom generators for space-bounded computation. Combinatorica, 12(4):449–461, 1992. Preliminary version in STOC’90. [doi:10.1007/BF01305237]
[22] Noam Nisan and Avi Wigderson: Hardness vs randomness. J. Comput. System Sci., 49(2):149–167, 1994. [doi:10.1016/S0022-0000(05)80043-1]
[23] Noam Nisan and David Zuckerman: Randomness is linear in space. J. Comput. System Sci., 52(1):43–52, 1996. Preliminary version in STOC’93. [doi:10.1006/jcss.1996.0004]
[24] Yuval Rabani and Amir Shpilka: Explicit construction of a small ϵ-net for linear threshold functions. SIAM J. Comput., 39(8):3501–3520, 2010. Preliminary version in STOC’09. [doi:10.1137/090764190]
[25] Jeanette P. Schmidt and Alan Siegel: The analysis of closed hashing under limited randomness (extended abstract). In Proc. 22nd STOC, pp. 224–234. ACM Press, 1990. [doi:10.1145/100216.100245]
[26] Ronen Shaltiel and Christopher Umans: Pseudorandomness for approximate counting and sampling. Comput. Complexity, 15(4):298–341, 2006. Preliminary version in CCC’05. [doi:10.1007/s00037-007-0218-9]
[27] Thomas Watson: Pseudorandom generators for combinatorial checkerboards. Comput. Complexity, pp. 1 – 43, 2012. Preliminary version in CCC’11. [doi:10.1007/s00037-012-0036-6]