{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,3]],"date-time":"2026-10-03T09:35:08Z","timestamp":1791020108860,"version":"4.1.0"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"4-5","license":[{"start":{"date-parts":[[1996,10,1]],"date-time":"1996-10-01T00:00:00Z","timestamp":844128000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1996,10]]},"DOI":"10.1007\/bf01940873","type":"journal-article","created":{"date-parts":[[2005,7,31]],"date-time":"2005-07-31T10:46:47Z","timestamp":1122806807000},"page":"415-433","source":"Crossref","is-referenced-by-count":32,"title":["On deterministic approximation of DNF"],"prefix":"10.1007","volume":"16","author":[{"given":"M.","family":"Luby","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"B.","family":"Veli\u010dkovi\u0107","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"BF01940873_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","volume":"24","author":"M. Ajtai","year":"1983","unstructured":"Ajtai, M., \u03c31 1 -Formulae on Finite Structures,Annals off Pure andApplied Logic,Vol. 24, 1983, pp. 1\u201348.","journal-title":"Annals off Pure andApplied Logic"},{"key":"BF01940873_CR2","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Wigderson, A., Deterministic Simulation of Probabilistic Constant Depth Circuits,Proceedings of the 26th Annual Symposium on the Foundations of Computer Science, Portland, Oregon, 1985, pp. 11\u201319.","DOI":"10.1109\/SFCS.1985.19"},{"key":"BF01940873_CR3","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"N. Alon","year":"1986","unstructured":"Alon, N., Babai, L., Itai, A., A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem,Journal of Algorithms, Vol. 7, 1986, pp. 567\u2013583.","journal-title":"Journal of Algorithms"},{"key":"BF01940873_CR4","doi-asserted-by":"crossref","unstructured":"Alon, N., Goldreich, O., H\u00e5stad, J., Peralta, R., Simple Constructions of Almostk-Wise Independent Random Variables,Proceedings of the 31st Annual Symposium on the Foundations of Computer Science, St. Louis, Missouri, 1990, pp. 544\u2013553.","DOI":"10.1109\/FSCS.1990.89575"},{"key":"BF01940873_CR5","first-page":"1","volume-title":"Advances in Computer Research, Vol. 5","author":"R. Boppana","year":"1989","unstructured":"Boppana, R., Hirschfeld, R., Pseudo-Random Generators and Complexity Classes, in S. Micali, ed.,Advances in Computer Research, Vol. 5, JAI Press, Greenwich, CT, 1989, pp. 1\u201326."},{"key":"BF01940873_CR6","doi-asserted-by":"crossref","unstructured":"Erd\u00f6s, P., Rado, R, Intersection Theorems for Systems of Sets,Journal of the London Mathematical Society, Vol. 35, pp. 85\u201390.","DOI":"10.1112\/jlms\/s1-35.1.85"},{"key":"BF01940873_CR7","doi-asserted-by":"crossref","unstructured":"Even, G., Goldreich, O., Luby, M., Nisan, N., Veli\u010dkovi\u0107, B., Approximations of General Independent Distributions,Proceedings of the 24th Annual Symposium on the Theory of Computing, Victoria, British Columbia, 1992, pp. 10\u201316.","DOI":"10.1145\/129712.129714"},{"key":"BF01940873_CR8","doi-asserted-by":"crossref","unstructured":"Furst, M., Saxe, J., Sipser, M., Parity, Circuits and the Polynomial Time Hierarchy,Proceedings of the 22nd Annual Symposium on the Foundations of Computer Science, 1981, pp. 260\u2013270.","DOI":"10.1109\/SFCS.1981.35"},{"key":"BF01940873_CR9","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J., Computational Limitations for Small Depth Circuits, Ph.D. thesis, M.I.T., 1986.","DOI":"10.1145\/12130.12132"},{"key":"BF01940873_CR10","doi-asserted-by":"crossref","unstructured":"Karp, R., Luby, M., Monte-Carlo Algorithms for Enumeration and Reliability Problems,Proceedings of the 24th Annual ACM Symposium on the Theory of Computing, 1983, pp. 54\u201363.","DOI":"10.1109\/SFCS.1983.35"},{"issue":"No. 3","key":"BF01940873_CR11","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1016\/0196-6774(89)90038-2","volume":"10","author":"R. Karp","year":"1989","unstructured":"Karp, R., Luby, M., Madras, N., Monte-Carlo Approximation Algorithms for Enumeration Problems,Journal of Algorithms, Vol. 10, No. 3, 1989, pp. 429\u2013448.","journal-title":"Journal of Algorithms"},{"issue":"No. 4","key":"BF01940873_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, Vol. 10, No. 4, 1990, pp. 349\u2013365.","journal-title":"Combinatorica"},{"key":"BF01940873_CR13","doi-asserted-by":"crossref","unstructured":"Luby, M., A Simple Parallel Algorithm for the Maximal Independent Set Problem,Proceedings of the 26th Annual ACM Symposium on the Theory of Computing, 1985, pp. 1\u201310, also inSIAM Journal on Computing, Vol. 15, No. 4, 1986, pp. 1036\u20131053.","DOI":"10.1137\/0215074"},{"key":"BF01940873_CR14","doi-asserted-by":"crossref","unstructured":"Luby, M., Veli\u010dkovi\u0107, B., Wigderson, A., Deterministic Approximate Counting of Depth-2 Circuits,Proceedings of the Second Israeli Symposium on Theory of Computing and Systems, 1993.","DOI":"10.1109\/ISTCS.1993.253488"},{"key":"BF01940873_CR15","doi-asserted-by":"crossref","unstructured":"Naor, M., Naor, S., Small Bias Probability Spaces: Efficient Constructions and Applications,Proceedings of the 22nd Annual ACM Symposium on the Theory of Computing, Baltimore, Maryland, 1990, pp. 213\u2013223.","DOI":"10.1145\/100216.100244"},{"key":"BF01940873_CR16","doi-asserted-by":"crossref","unstructured":"Nisan, N., Wigderson, A., Hardness vs. Randomness,Proceedings of the 29th Annual Symposium on the Foundations of Computer Science, White Plains, New York, 1988, pp. 2\u201311.","DOI":"10.1109\/SFCS.1988.21916"},{"issue":"No. 4","key":"BF01940873_CR17","first-page":"798","volume":"281","author":"A. Razborov","year":"1985","unstructured":"Razborov, A., Lower Bounds on the Monotone Complexity of Some Boolean Functions,Doklady Akademii Nauk SSSR, Vol. 281, No. 4, 1985, pp. 798\u2013801 (in Russian). English translation inSoviet Mathematics Doklady, Vol. 31, pp. 354\u2013357.","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"BF01940873_CR18","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"No. 8","author":"L. G. Valiant","year":"1979","unstructured":"Valiant, L. G., The Complexity of Computing the Permanent,Theoretical Computer Science, No. 8, 1979, pp. 189\u2013201.","journal-title":"Theoretical Computer Science"},{"key":"BF01940873_CR19","volume-title":"Ph.D. thesis","author":"U. Vazirani","year":"1986","unstructured":"Vazirani, U., Randomness, Adversaries and Computation, Ph.D. thesis, University of California, Berkeley, 1986."},{"key":"BF01940873_CR20","volume-title":"Actualit\u00e9s Scientifiques et Industrielles, No. 1041","author":"A. Weil","year":"1948","unstructured":"Weil, A.,Sur les courbes alg\u00e9briques et les vari\u00e9t\u00e9s qui s'en d\u00e9duisent, Actualit\u00e9s Scientifiques et Industrielles, No. 1041, Hermann, Paris, 1948."},{"key":"BF01940873_CR21","doi-asserted-by":"crossref","unstructured":"Yao, A., Separating the Polynomial-Time Hierarchy by Oracles,Proceedings of the 26th Annual Symposium on the Foundations of Computer Science, Portland, Oregon, 1985, pp. 1\u201310.","DOI":"10.1109\/SFCS.1985.49"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01940873.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01940873\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01940873","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,2]],"date-time":"2025-01-02T21:22:32Z","timestamp":1735852952000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01940873"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,10]]},"references-count":21,"journal-issue":{"issue":"4-5","published-print":{"date-parts":[[1996,10]]}},"alternative-id":["BF01940873"],"URL":"https:\/\/doi.org\/10.1007\/bf01940873","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,10]]}}}