On deterministic approximation of DNF

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On deterministic approximation of DNF

Full text

Pdf (743 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-third annual ACM symposium on Theory of computing table of contents

New Orleans, Louisiana, United States

Pages: 430 - 438

Year of Publication: 1991

ISBN:0-89791-397-3

Authors

Michael Luby	International Computer Science Institute, Berkeley, CA
Boban Veličkovic	Univ. of California, Berkeley

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 23, Citation Count: 5

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/103418.103464 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alon, N., Goldreich, O., H~stad, J., Peralta, R., "Simple constructions of almost kwise independent random variables", FOCS 90.
	2	Ajtai M "#l-Formulae on Finite Structures", Annals of Pure and Applied Logzc, 24, 1983, pp. 1-48.
	3	Ajtai, M., Wigderson, A., "Deterministic Simulation of Probabilistic constant depth circuits", FOCS 85.
	4	Noga Alon , László Babai , Alon Itai, A fast and simple randomized parallel algorithm for the maximal independent set problem, Journal of Algorithms, v.7 n.4, p.567-583, Dec. 1986 [doi>10.1016/0196-6774(86)90019-2]
	5	ErdSs, P., Ratio, R, "Intersection theorems for systems of sets", Journal of the London Math. Society, vol.35, pp.85-90.
	6	Furst, M., Saxe, J., Sipser, M., "Parity, Circuits and the Polynomial Time Hierarchy", FOCS 81.
	7	H~stad, J., "Computational limitations for small depth circuits", Ph.D. thesis, M.I.T. press, 1986.
	8	Karp, R., Luby, M., "Monte-Carlo algorithms for enumeration and reliability problems", STOC 83.
	9	R. M. Kapp , M. Luby , N. Madras, Monte-Carlo approximation algorithms for enumeration problems, Journal of Algorithms, v.10 n.3, p.429-448, September 1989 [doi>10.1016/0196-6774(89)90038-2]
	10	N. Linial , N. Nisan, Approximate inclusion-exclusion, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.260-270, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100250]
	11	Michael Luby, A simple parallel algorithm for the maximal independent set problem, SIAM Journal on Computing, v.15 n.4, p.1036-1055, Nov. 1986 [doi>10.1137/0215074]
	12	J. Naor , M. Naor, Small-bias probability spaces: efficient constructions and applications, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.213-223, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100244]
	13	Nisan, N., Wigderson, A., "Hardness vs. Randomness", FOCS 89, pp. 2-11.
	14	Valiant, L. G., "The complexity of computing the permanent", Theoretical Computer Science, 1979, No. 8, pp 189-201.
	15	Umesh Virkumar Vazirani, Randomness, adversaries and computation (random polynomial time), 1986
	16	Weil, A., "Sur les courbes alg#briques et les vari#t#s qui s'en deduisenL", Actualzles 5c#. Ind. No. 1041, 1948.
	17	Andrew C-C. Yao, Separating the polynomial-time hierarchy by oracles, Proc. 26th annual symposium on Foundations of computer science, p.1-10, October 1985, Portland, Oregon, United States

CITED BY 5

	Guy Even , Oded Goldreich , Michael Luby , Noam Nisan , Boban Veličkovic, Approximations of general independent distributions, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.10-16, May 04-06, 1992, Victoria, British Columbia, Canada
	Yishay Mansour, An O(nlog log n) learning algorithm for DNF under the uniform distribution, Proceedings of the fifth annual workshop on Computational learning theory, p.53-61, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
	Nati Linial , Michael Luby , Michael Saks , David Zuckerman, Efficient construction of a small hitting set for combinatorial rectangles in high dimension, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.258-267, May 16-18, 1993, San Diego, California, United States
	Marek Karpinski , Michael Luby, Approximating the number of zeroes of a GF[2] polynomial, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.300-303, January 28-30, 1991, San Francisco, California, United States
	Elazar Birnbaum , Eliezer L. Lozinskii, The good old Davis-Putnam procedure helps counting models, Journal of Artificial Intelligence Research, v.10 n.1, p.457-477, January 1999