{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T16:58:22Z","timestamp":1725469102810},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642325113"},{"type":"electronic","value":"9783642325120"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32512-0_36","type":"book-chapter","created":{"date-parts":[[2012,7,20]],"date-time":"2012-07-20T22:21:08Z","timestamp":1342822868000},"page":"423-434","source":"Crossref","is-referenced-by-count":1,"title":["Optimal Hitting Sets for Combinatorial Shapes"],"prefix":"10.1007","author":[{"given":"Aditya","family":"Bhaskara","sequence":"first","affiliation":[]},{"given":"Devendra","family":"Desai","sequence":"additional","affiliation":[]},{"given":"Srikanth","family":"Srinivasan","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"36_CR1","doi-asserted-by":"crossref","unstructured":"Aleliunas, R., Karp, R.M., Lipton, R.J., Lov\u00e1sz, L., Rackoff, C.: Random walks, universal traversal sequences, and the complexity of maze problems. In: 20th Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, October 29-31, pp. 29\u201331. IEEE (1979)","DOI":"10.1109\/SFCS.1979.34"},{"key":"36_CR2","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/BF01277956","volume":"5","author":"N. Alon","year":"1995","unstructured":"Alon, N., Feige, U., Wigderson, A., Zuckerman, D.: Derandomized graph products. Computational Complexity\u00a05, 60\u201375 (1995), doi:10.1007\/BF01277956","journal-title":"Computational Complexity"},{"issue":"4","key":"36_CR3","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N. Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM\u00a042(4), 844\u2013856 (1995)","journal-title":"J. ACM"},{"key":"36_CR4","first-page":"412","volume-title":"37th Annual Symposium on Foundations of Computer Science, Burlington, VT","author":"R. Armoni","year":"1996","unstructured":"Armoni, R., Saks, M., Wigderson, A., Zhou, S.: Discrepancy sets and pseudorandom generators for combinatorial rectangles. In: 37th Annual Symposium on Foundations of Computer Science, Burlington, VT, pp. 412\u2013421. IEEE Comput. Soc. Press, Los Alamitos (1996)"},{"issue":"4","key":"36_CR5","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1145\/792538.792543","volume":"50","author":"A. Blum","year":"2003","unstructured":"Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM\u00a050(4), 506\u2013519 (2003)","journal-title":"J. ACM"},{"issue":"1","key":"36_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/(SICI)1098-2418(199808)13:1<1::AID-RSA1>3.0.CO;2-W","volume":"13","author":"G. Even","year":"1998","unstructured":"Even, G., Goldreich, O., Luby, M., Nisan, N., Veli\u010dkovi\u0107, B.: Efficient approximation of product distributions. Random Structures Algorithms\u00a013(1), 1\u201316 (1998)","journal-title":"Random Structures Algorithms"},{"key":"36_CR7","unstructured":"Feller, W.: An Introduction to Probability Theory and its Applications, vol.\u00a02. Wiley (1971)"},{"issue":"3","key":"36_CR8","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"M.L. Fredman","year":"1984","unstructured":"Fredman, M.L., Koml\u00f3s, J., Szemer\u00e9di, E.: Storing a sparse table with 0(1) worst case access time. J. ACM\u00a031(3), 538\u2013544 (1984)","journal-title":"J. ACM"},{"key":"36_CR9","doi-asserted-by":"crossref","unstructured":"Gopalan, P., Meka, R., Reingold, O., Zuckerman, D.: Pseudorandom generators for combinatorial shapes. In: STOC, pp. 253\u2013262 (2011)","DOI":"10.1145\/1993636.1993671"},{"issue":"4","key":"36_CR10","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","volume":"43","author":"S. Hoory","year":"2006","unstructured":"Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bulletin of the AMS\u00a043(4), 439\u2013561 (2006)","journal-title":"Bulletin of the AMS"},{"key":"36_CR11","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Wigderson, A.: P\u2009=\u2009BPP if E requires exponential circuits: Derandomizing the XOR lemma. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, El Paso, Texas, May 4-6, pp. 220\u2013229 (1997)","DOI":"10.1145\/258533.258590"},{"key":"36_CR12","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/BF01200907","volume":"17","author":"N. Linial","year":"1997","unstructured":"Linial, N., Luby, M., Saks, M., Zuckerman, D.: Efficient construction of a small hitting set for combinatorial rectangles in high dimension. Combinatorica\u00a017, 215\u2013234 (1997), doi:10.1007\/BF01200907","journal-title":"Combinatorica"},{"key":"36_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1007\/978-3-642-03685-9_46","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"S. Lovett","year":"2009","unstructured":"Lovett, S., Reingold, O., Trevisan, L., Vadhan, S.: Pseudorandom Bit Generators That Fool Modular Sums. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX and RANDOM 2009. LNCS, vol.\u00a05687, pp. 615\u2013630. Springer, Heidelberg (2009)"},{"key":"36_CR14","doi-asserted-by":"crossref","unstructured":"Lu, C.-J.: Hyper-encryption against space-bounded adversaries from on-line strong extractors, pp. 257\u2013271","DOI":"10.1007\/3-540-45708-9_17"},{"key":"36_CR15","doi-asserted-by":"crossref","unstructured":"Meka, R., Zuckerman, D.: Small-bias spaces for group products. These proceedings (2009)","DOI":"10.1007\/978-3-642-03685-9_49"},{"key":"36_CR16","doi-asserted-by":"crossref","unstructured":"Moser, R.A., Tardos, G.: A constructive proof of the general lov\u00e1sz local lemma. J. ACM\u00a057(2) (2010)","DOI":"10.1145\/1667053.1667060"},{"issue":"4","key":"36_CR17","doi-asserted-by":"publisher","first-page":"838","DOI":"10.1137\/0222053","volume":"22","author":"J. Naor","year":"1993","unstructured":"Naor, J., Naor, M.: Small-bias probability spaces: Efficient constructions and applications. SIAM Journal on Computing\u00a022(4), 838\u2013856 (1993)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"36_CR18","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/BF01305237","volume":"12","author":"N. Nisan","year":"1992","unstructured":"Nisan, N.: Pseudorandom generators for space-bounded computation. Combinatorica\u00a012(4), 449\u2013461 (1992)","journal-title":"Combinatorica"},{"issue":"2","key":"36_CR19","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"N. Nisan","year":"1994","unstructured":"Nisan, N., Wigderson, A.: Hardness vs. randomness. J. Comput. Syst. Sci.\u00a049(2), 149\u2013167 (1994)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"36_CR20","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1006\/jcss.1996.0004","volume":"52","author":"N. Nisan","year":"1996","unstructured":"Nisan, N., Zuckerman, D.: Randomness is linear in space. Journal of Computer and System Sciences\u00a052(1), 43\u201352 (1996)","journal-title":"Journal of Computer and System Sciences"},{"issue":"8","key":"36_CR21","doi-asserted-by":"publisher","first-page":"3501","DOI":"10.1137\/090764190","volume":"39","author":"Y. Rabani","year":"2010","unstructured":"Rabani, Y., Shpilka, A.: Explicit construction of a small epsilon-net for linear threshold functions. SIAM J. Comput.\u00a039(8), 3501\u20133520 (2010)","journal-title":"SIAM J. Comput."},{"key":"36_CR22","doi-asserted-by":"crossref","unstructured":"Schmidt, J.P., Siegel, A.: The analysis of closed hashing under limited randomness (extended abstract). In: STOC, pp. 224\u2013234 (1990)","DOI":"10.1145\/100216.100245"},{"issue":"4","key":"36_CR23","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1007\/s00037-007-0218-9","volume":"15","author":"R. Shaltiel","year":"2006","unstructured":"Shaltiel, R., Umans, C.: Pseudorandomness for approximate counting and sampling. Computational Complexity\u00a015(4), 298\u2013341 (2006)","journal-title":"Computational Complexity"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32512-0_36.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T12:05:32Z","timestamp":1620129932000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32512-0_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642325113","9783642325120"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32512-0_36","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}