{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T06:04:20Z","timestamp":1775282660972,"version":"3.50.1"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1997,6,1]],"date-time":"1997-06-01T00:00:00Z","timestamp":865123200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[1997,6]]},"DOI":"10.1007\/bf01200907","type":"journal-article","created":{"date-parts":[[2005,2,18]],"date-time":"2005-02-18T15:38:30Z","timestamp":1108741110000},"page":"215-234","source":"Crossref","is-referenced-by-count":34,"title":["Efficient construction of a small hitting set for combinatorial rectangles in high dimension"],"prefix":"10.1007","volume":"17","author":[{"given":"Nathan","family":"Linial","sequence":"first","affiliation":[]},{"given":"Michael","family":"Luby","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Saks","sequence":"additional","affiliation":[]},{"given":"David","family":"Zuckerman","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","unstructured":"M. Ajtai, J. Koml\ufffds, andE. Szemer\ufffddi: Deterministic Simulation in LOGSPACE, in:Proc. of 19th ACM Symposium on Theory of Computing, 1987, 132?140.","DOI":"10.1145\/28395.28410"},{"key":"CR2","unstructured":"R. Armoni, M. Saks, A. Wigderson, andS. Zhou: Discrepancy sets and pseudorandom generators for combinatorial rectangles,Proc. 37th IEEE Symposium on Foundations of Computer Science, 1996."},{"key":"CR3","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","volume":"18","author":"J. L. Carter","year":"1979","unstructured":"J. L. Carter, M. N. Wegman: Universal classes of hash functions,J. Comput. System Sci.,18 (1979), 143?154.","journal-title":"J. Comput. System Sci."},{"key":"CR4","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1016\/0885-064X(89)90015-0","volume":"5","author":"B. Chor","year":"1989","unstructured":"B. Chor, O. Goldreich: On the Power of Two-Point Based Sampling,Journal of Complexity,5 (1989), 96?106.","journal-title":"Journal of Complexity"},{"key":"CR5","unstructured":"G. Even, O. Goldreich, M. Luby, N. Nisan, andB. Boban Veli?kovi?: Approximations of General Independent Distributions. in:Proc. of the 24th ACM Symposium on Theory of Computing, 1992."},{"key":"CR6","doi-asserted-by":"crossref","unstructured":"J. Friedman: ConstructingO(n log(n)) size monotone formulae for thekth threshold function ofn boolean variables.SIAM J. on Computing,15 (1986).","DOI":"10.1137\/0215047"},{"key":"CR7","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1016\/0022-0000(81)90040-4","volume":"22","author":"O. Gabber","year":"1981","unstructured":"O. Gabber, Z. Galil: Explicit constructions of linear-sized superconcentrators,Journal of Computer System Science,22 (1981), 407?420.","journal-title":"Journal of Computer System Science"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1007\/BF01271266","volume":"16","author":"J. Kahn","year":"1996","unstructured":"J. Kahn, N. Linial, andA. Samorodnitsky: Inclusion-Exclusion: Exact and approximate,Combinatorica,16 (1996), 465?477.","journal-title":"Combinatorica"},{"key":"CR9","unstructured":"R. Karp, M. Pippenger, andM. Sipser:Time-Randomness Tradeoff, presented at the AMS conference on probabilistic computational complexity, Durham, New Hampshire, 1982."},{"key":"CR10","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1006\/jagm.1993.1014","volume":"14","author":"M. Karpinski","year":"1993","unstructured":"M. Karpinski, M. Luby: Approximating the Number of Solutions to aGF[2] Formula,Journal of Algorithms,14 (1993), 280?287.","journal-title":"Journal of Algorithms"},{"key":"CR11","doi-asserted-by":"crossref","unstructured":"M. Luby, B. Veli?kovi?: On Deterministic Approximation of DNF, in:Proceedings of 23rd ACM Symposium on Theory of Computing, 1991, 430?438,Algorithmica (special issue devoted to randomized algorithms), Vol. 16, No. 4\/5, October\/November 1996, 415?433.","DOI":"10.1007\/BF01940873"},{"key":"CR12","doi-asserted-by":"crossref","unstructured":"M. Luby, A. Wigderson, andB. Veli?kovi?: Deterministic Approximate Counting of Depth-2 Circuits, in:Proceedings of the Second Israeli Symposium on Theory of Computing and Systems, 1993, 18?24.","DOI":"10.1109\/ISTCS.1993.253488"},{"key":"CR13","first-page":"71","volume":"9","author":"G. A. Margulis","year":"1973","unstructured":"G. A. Margulis: Explicit construction of concentrators,Problemy Pereda?i Informacii 9, (1973) 71?80. (English translation inProblems Inform. Transmission, 1975).","journal-title":"Problemy Pereda?i Informacii"},{"key":"CR14","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1007\/BF01305237","volume":"12","author":"N. Nisan","year":"1992","unstructured":"N. Nisan: Pseudorandom Generators for Space-Bounded Computation,Combinatorica,12 (1992), 449?461.","journal-title":"Combinatorica"},{"key":"CR15","doi-asserted-by":"crossref","first-page":"775","DOI":"10.1137\/0219054","volume":"19","author":"J. Schmidt","year":"1990","unstructured":"J. Schmidt, A. Siegel: The Spatial Complexity of obliviousk-probe hash functions,SIAM Journal on Computing,19 (1990), 775?786.","journal-title":"SIAM Journal on Computing"},{"key":"CR16","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1016\/0022-0000(88)90035-9","volume":"36","author":"M. Sipser","year":"1988","unstructured":"M. Sipser: Expanders, Randomness, or Time vs. Space,Journal of Computer and System Sciences,36 (1988), 379?383.","journal-title":"Journal of Computer and System Sciences"},{"key":"CR17","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1007\/BF01940870","volume":"16","author":"D. Zuckerman","year":"1996","unstructured":"D. Zuckerman: Simulating BPP Using a General Weak Random Source,Algorithmica,16 (1996), 367?391.","journal-title":"Algorithmica"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01200907.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01200907\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01200907","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T12:49:43Z","timestamp":1734958183000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01200907"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,6]]},"references-count":17,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1997,6]]}},"alternative-id":["BF01200907"],"URL":"https:\/\/doi.org\/10.1007\/bf01200907","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,6]]}}}