{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T06:39:30Z","timestamp":1648881570702},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,5,7]],"date-time":"2016-05-07T00:00:00Z","timestamp":1462579200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"FEA URB, American University of Beirut","award":["288309"],"award-info":[{"award-number":["288309"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2017,2]]},"DOI":"10.1007\/s00224-016-9680-6","type":"journal-article","created":{"date-parts":[[2016,5,7]],"date-time":"2016-05-07T10:18:01Z","timestamp":1462616281000},"page":"324-345","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Small-Bias is Not Enough to Hit Read-Once CNF"],"prefix":"10.1007","volume":"60","author":[{"given":"Louay","family":"Bazzi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nagi","family":"Nahas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,5,7]]},"reference":[{"key":"9680_CR1","doi-asserted-by":"crossref","unstructured":"Alon, N., Ben-Eliezer, I., Krivelevich, M.: Small sample spaces cannot fool low degree polynomials. APPROX-RANDOM 2008, 266 - 275 (2008)","DOI":"10.1007\/978-3-540-85363-3_22"},{"issue":"1","key":"9680_CR2","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1145\/273865.273933","volume":"45","author":"A Andreev","year":"1998","unstructured":"Andreev, A., Clementi, A.E., Rolim, J.D.: A new general derandomization method. J. ACM 45(1), 179\u2013213 (1998)","journal-title":"J. ACM"},{"issue":"3","key":"9680_CR3","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1002\/rsa.3240030308","volume":"3","author":"N Alon","year":"1992","unstructured":"Alon, N., Goldreich, O., Hastad, J., Peralta, R.: Simple constructions of almost k-wise independent random variables. Random Struct. Algoritm. 3(3), 289\u2013304 (1992)","journal-title":"Random Struct. Algoritm."},{"key":"9680_CR4","unstructured":"Bazzi, L.: Minimum distance of error correcting codes versus encoding complexity, symmetry, and pseudorandomness. Ph.D. dissertation MIT (2003)"},{"key":"9680_CR5","doi-asserted-by":"crossref","unstructured":"Bazzi, L.: Polylogarithmic independence can fool DNF formulas. In: Proceedings of 48th Annual IEEE Symposium on Foundations of Computer Science, pp 63\u201373 (2007)","DOI":"10.1109\/FOCS.2007.28"},{"issue":"6","key":"9680_CR6","doi-asserted-by":"crossref","first-page":"2220","DOI":"10.1137\/070691954","volume":"38","author":"L Bazzi","year":"2009","unstructured":"Bazzi, L.: Polylogarithmic independence can fool DNF formulas. SIAM J. Comput. 38(6), 2220\u20132272 (2009)","journal-title":"SIAM J. Comput."},{"key":"9680_CR7","doi-asserted-by":"crossref","unstructured":"Braverman, M.: Poly-logarithmic independence fools AC0 circuits. J. ACM 57 (5) (2010)","DOI":"10.1145\/1754399.1754401"},{"issue":"4","key":"9680_CR8","doi-asserted-by":"crossref","first-page":"850","DOI":"10.1137\/0213053","volume":"13","author":"M Blum","year":"1984","unstructured":"Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudo-random bits. SIAM J Comput. 13(4), 850\u2013864 (1984)","journal-title":"SIAM J Comput."},{"key":"9680_CR9","doi-asserted-by":"crossref","unstructured":"De, A., Etesami, O., Trevisan, L., Tulsiani, M.: Improved pseudorandom generators for depth 2 circuits. APPROX-RANDOM 2010, 504\u2013517 (2010)","DOI":"10.1007\/978-3-642-15369-3_38"},{"key":"9680_CR10","doi-asserted-by":"crossref","unstructured":"Gopalan, P., Meka, R., Reingold, O., Trevisan, L., Vadhan, S.: Better pseudorandom generators from milder pseudorandom restrictions. In: Proceedings of the 53rd IEEE symposium on foundations of computer science, pp 120\u2013129 (2012)","DOI":"10.1109\/FOCS.2012.77"},{"key":"9680_CR11","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Wigderson, A.: P = BPP if E requires exponential circuits: derandomizing the XOR lemma. In: Proceedings of 29th annual ACM symposium on the theory of computing, pp 220\u2013229 (1997)","DOI":"10.1145\/258533.258590"},{"issue":"4","key":"9680_CR12","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/BF02128670","volume":"10","author":"N Linial","year":"1990","unstructured":"Linial, N., Nisan, N.: Approximate inclusion-exclusion. Combinatorica 10 (4), 349\u2013365 (1990)","journal-title":"Combinatorica"},{"key":"9680_CR13","doi-asserted-by":"crossref","unstructured":"Lovett, S., Reingold, O., Trevisan, L., Vadhan, S.: Pseudorandom bit generators that fool modular sums. APPROX-RANDOM, 2009, 615\u2013630 (2009)","DOI":"10.1007\/978-3-642-03685-9_46"},{"key":"9680_CR14","doi-asserted-by":"crossref","unstructured":"Luby, M.: A simple parallel algorithm for the maximal independent set problem. In: Proceedings of 17th annual ACM symposium on the theory of computing, pp 1\u201310 (1985)","DOI":"10.1145\/22145.22146"},{"key":"9680_CR15","doi-asserted-by":"crossref","unstructured":"Luby, M., Velickovic, B., Wigderson, A.: Deterministic approximate counting of depth-2 circuits. In: Proceedings of the 2nd ISTCS, pp. 18\u201324 (1993)","DOI":"10.1109\/ISTCS.1993.253488"},{"key":"9680_CR16","doi-asserted-by":"crossref","unstructured":"Meka, R., Zuckerman, D.: Small-bias spaces for group products. APPROX-RANDOM 2009, 658\u2013672 (2009)","DOI":"10.1007\/978-3-642-03685-9_49"},{"issue":"4","key":"9680_CR17","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/BF01375474","volume":"12","author":"N Nisan","year":"1991","unstructured":"Nisan, N.: Pseudorandom bits for constant depth circuits. Combinatorica 12 (4), 63\u201370 (1991)","journal-title":"Combinatorica"},{"issue":"4","key":"9680_CR18","doi-asserted-by":"crossref","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 J. Comput. 22(4), 838\u2013856 (1993)","journal-title":"SIAM J. Comput."},{"key":"9680_CR19","doi-asserted-by":"crossref","unstructured":"Nisan, N., Wigderson, A.: Hardness vs. randomness. In: Proceedings of 29th IEEE symposium on foundations of computer science, pp 2\u201311 (1988)","DOI":"10.1109\/SFCS.1988.21916"},{"key":"9680_CR20","doi-asserted-by":"crossref","unstructured":"Paturi, R.: On the degree of polynomials that approximate symmetric boolean functions. In: Proceedings of 24th annual ACM symposium on the theory of computing, pp 468\u2013474 (1992)","DOI":"10.1145\/129712.129758"},{"issue":"1","key":"9680_CR21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1490270.1490273","volume":"1","author":"A Razborov","year":"2009","unstructured":"Razborov, A.: A simple proof of Bazzi\u2019s theorem. ACM Trans. Comput. Theory 1(1), 1\u20135 (2009)","journal-title":"ACM Trans. Comput. Theory"},{"key":"9680_CR22","doi-asserted-by":"crossref","unstructured":"Sima, J., Zak, S.: Almost k-wise independent sets establish hitting sets for width 3 1-branching programs. In: 6th international computer science symposium in Russia, pp 120\u2013133 (2011)","DOI":"10.1007\/978-3-642-20712-9_10"},{"key":"9680_CR23","volume-title":"Orthogonal polynomials, 4th edn., vol. 23","author":"S Szego","year":"1975","unstructured":"Szego, S.: Orthogonal polynomials, 4th edn., vol. 23. Colloquium Publications, Providence (1975). Amer. Math. Soc."},{"issue":"3","key":"9680_CR24","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/0021-9045(91)90090-W","volume":"65","author":"L Trefethen","year":"1991","unstructured":"Trefethen, L., Weideman, J.: Two results on polynomial interpolation in equally spaced points. J. Approximation Theory 65(3), 247\u2013260 (1991)","journal-title":"J. Approximation Theory"},{"key":"9680_CR25","doi-asserted-by":"crossref","unstructured":"Trevisan, L., Xue, T.: A derandomized switching lemma and an improved derandomization of AC0. IEEE Conference on Computational Complexity (CCC), 242\u2013247 (2013)","DOI":"10.1109\/CCC.2013.32"},{"key":"9680_CR26","volume-title":"Randomness, adversaries, and computation","author":"U Vazirani","year":"1986","unstructured":"Vazirani, U.: Randomness, adversaries, and computation. Ph.D. dissertation, University of California, Berkeley (1986)"},{"key":"9680_CR27","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Theory and application of Trapdoor functions. In: Proceedings of 23rd IEEE annual symposium on foundations of computer science, pp 80\u201391 (1982)","DOI":"10.1109\/SFCS.1982.45"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9680-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-016-9680-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9680-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9680-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,7]],"date-time":"2019-09-07T07:44:08Z","timestamp":1567842248000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-016-9680-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,7]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,2]]}},"alternative-id":["9680"],"URL":"https:\/\/doi.org\/10.1007\/s00224-016-9680-6","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,5,7]]}}}