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 Veli˘c   ković: 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]