Efficient construction of a small hitting set for combinatorial rectangles in high dimension

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient construction of a small hitting set for combinatorial rectangles in high dimension

Full text

Pdf (678 KB)

Source

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

San Diego, California, United States

Pages: 258 - 267

Year of Publication: 1993

ISBN:0-89791-591-7

Authors

Nati Linial
Michael Luby
Michael Saks
David Zuckerman

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 17, Citation Count: 3

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/167088.167166 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	B. Chor , O. Goldreich, On the power of two-point based sampling, Journal of Complexity, v.5 n.1, p.96-106, March 1989 [doi>10.1016/0885-064X(89)90015-0]
	2	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 [doi>10.1145/129712.129714]
	3	Joel Friedman, Constructing O(nlogn9 size monotone formulae for the kth threshold function of n Boolean variables, SIAM Journal on Computing, v.15 n.3, p.641-654, August 1986 [doi>10.1137/0215047]
	4	Marek Karpinski , Michael Luby, Approximating the number of zeroes of a GF[2] polynomial, Journal of Algorithms, v.14 n.2, p.280-287, March 1993 [doi>10.1006/jagm.1993.1014]
	5	Karp, R. Pippenger, N. and Sipser, M., "Time-Randomness Tradeoff", presented at the AMS conference on probabi:Listic computational complexity, Durham, New Hampshire, 1982.
	6	Michael Luby , Boban Veličkovic, On deterministic approximation of DNF, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.430-438, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103464]
	7	Michael Luby, Avi Wigderson and Boban Veli#kovid, "Deterministic Approximate Counting of Depth-2 Circuits", work in progress, 1992.
	8	N. Nisan, Pseudorandom generators for space-bounded computations, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.204-212, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100242]
	9	Jeanette P. Schmidt , Alan Siegel, The spatial complexity of oblivious k-probe Hash functions, SIAM Journal on Computing, v.19 n.5, p.775-786, Oct. 1990 [doi>10.1137/0219054]
	10	M Sipser, Expanders, randomness, or time versus space, Proc. of the conference on Structure in complexity theory, p.325-329, June 1986, Berkeley, California, United States
	11	David Zuckerman, Simulating BPP using a general weak random source, Proceedings of the 32nd annual symposium on Foundations of computer science, p.79-89, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185351]

CITED BY 3

	Elias Koutsoupias , D. S. Taylor, Tight bounds for 2-dimensional indexing schemes, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.52-58, June 01-04, 1998, Seattle, Washington, United States
	Peter Auer , Philip M. Long , Aravind Srinivasan, Approximating hyper-rectangles: learning and pseudo-random sets, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.314-323, May 04-06, 1997, El Paso, Texas, United States
	Avi Wigderson, The amazing power of pairwise independence (abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.645-647, May 23-25, 1994, Montreal, Quebec, Canada