{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:18:38Z","timestamp":1725455918953},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540626169"},{"type":"electronic","value":"9783540683421"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/bfb0023475","type":"book-chapter","created":{"date-parts":[[2005,11,19]],"date-time":"2005-11-19T07:06:33Z","timestamp":1132383993000},"page":"387-398","source":"Crossref","is-referenced-by-count":2,"title":["Efficient constructions of Hitting Sets for systems of linear functions"],"prefix":"10.1007","author":[{"given":"Alexander E.","family":"Andreev","sequence":"first","affiliation":[]},{"given":"Andrea E. F.","family":"Clementi","sequence":"additional","affiliation":[]},{"given":"Jos\u00e9 D. P.","family":"Rolim","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,10]]},"reference":[{"key":"32_CR1","doi-asserted-by":"crossref","unstructured":"Andreev A.E., Clementi A.E.F. and Rolim J.D.P. (1996), \u201cTowards efficient constructions of hitting sets that derandomize BPP\u201d, Research Report in ECCC, TR-96-029.","DOI":"10.1007\/3-540-61440-0_142"},{"key":"32_CR2","doi-asserted-by":"crossref","unstructured":"Allender E, Beals R, and Ogihara M. (1996), \u201cThe complexity of matrix rank and feasible systems of linear equations\u201d, in Proc. of 28-th ACM STOC, to appear. Also available by ftp\/www in ECCC (Tech. Rep. 1996).","DOI":"10.1145\/237814.237856"},{"key":"32_CR3","unstructured":"Andreev, A.E. (1989), On the complexity of the realization of partial Boolean functions by circuits of functional elements, Diskret. mat. 1, pp.36\u201345. (In Russian). English translation in Discrete Mathematics and Applications 1, pp.251\u2013262."},{"key":"32_CR4","doi-asserted-by":"crossref","unstructured":"Andreev A.E., Clementi A.E.F. and Rolim J.D.P. (1996), \u201cHitting Sets derandomize BPP\u201d, in Proc. of 23-th ICALP LNCS, Springer-Verlag, to appear. Also available by ftp\/www in ECCC (Tech. Rep. 1996).","DOI":"10.1007\/3-540-61440-0_142"},{"key":"32_CR5","unstructured":"Andreev A.E., Clementi A.E.F. and Rolim J.D.P. (1996), \u201cOptimal bounds for the approximation of boolean functions and some applications\u201d, in Proc. of 13-th STACS, LNCS, Springer-Verlag (1996). Also available by ftp\/www in ECCC (Tech. Rep. 1995)."},{"key":"32_CR6","unstructured":"Andreev A.E., Clementi A.E.F. and Rolim J.D.P. (1996), \u201cOn the parallel computation of boolean functions on unrelated inputs\u201d, in Proc. of 4-th Israeli Symposium on Theory of Computing and Systems (ISTCS'96), to appear."},{"key":"32_CR7","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/0885-064X(89)90015-0","volume":"5","author":"B. Chor","year":"1989","unstructured":"Chor B., and O. Goldreich (1989), \u201cOn the Power of Two-Point Based Sampling\u201d, J. Complexity, 5, 96\u2013106.","journal-title":"J. Complexity"},{"key":"32_CR8","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/BF01864160","volume":"4","author":"Z. Furedi","year":"1988","unstructured":"Furedi, Z. (1988) \u201cMatchings and Covers in Hypergraphs\u201d, Graphs and Combinatorics, 4, 115\u2013206.","journal-title":"Graphs and Combinatorics"},{"key":"32_CR9","unstructured":"Karp R., Pippenger N., and Sipser M. (1982) \u201cTime-Randomness, Tradeoff\u201d, presented at AMS Conference on Probabilistic Computational Complexity."},{"key":"32_CR10","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1006\/jagm.1993.1014","volume":"14","author":"M. Karpinski","year":"1993","unstructured":"Karpinski, M., and Luby, M. (1993), \u201cApproximating the number of solutions to a GF(2) Formula\u201d, J. Algorithms, 14, pp.280\u2013287.","journal-title":"J. Algorithms"},{"key":"32_CR11","doi-asserted-by":"crossref","unstructured":"Linial N., Luby M., Saks M., and Zuckerman D. (1993), \u201cEfficient construction of a small hitting set for combinatorial rectangles in high dimension\u201d, in Proc. 25th ACM STOC, 258\u2013267.","DOI":"10.1145\/167088.167166"},{"key":"32_CR12","first-page":"31","volume":"14","author":"O.B. Lupanov","year":"1965","unstructured":"Lupanov, O.B. (1965), \u201cAbout a method circuits design \u2014 local coding principle\u201d, Problemy Kibernet. 14, pp.31\u2013110. (in Russian). Systems Theory Res. v.14, 1966 (in English).","journal-title":"Problemy Kibernet."},{"key":"32_CR13","first-page":"40","volume":"163","author":"E.I. Nechiporuk","year":"1965","unstructured":"Nechiporuk, E.I. (1965), About the complexity of gating circuits for the partial boolean matrix, Dokl. Akad. Nauk SSSR 163, pp.40\u201342. (In Russian). English translation in Soviet Math. Docl.","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"32_CR14","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., and Wigderson A. (1994), \u201cHardness vs Randomness\u201d, J. Comput. System Sci. 49, 149\u2013167 (also presented at the 29th IEEE FOCS, 1988).","journal-title":"J. Comput. System Sci."},{"key":"32_CR15","first-page":"325","volume":"223","author":"M. Sipser","year":"1986","unstructured":"Sipser M. (1986), \u201cExpanders, Randomness or Time vs Space\u201d, in Proc. of 1st Conference on Structures in Complexity Theory, LNCS 223, 325\u2013329.","journal-title":"LNCS"}],"container-title":["Lecture Notes in Computer Science","STACS 97"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0023475","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T01:32:03Z","timestamp":1586568723000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0023475"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540626169","9783540683421"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/bfb0023475","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}