Are bitvectors optimal?

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Are bitvectors optimal?

Full text

Pdf (1.01 MB)

Source

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

Portland, Oregon, United States

Pages: 449 - 458

Year of Publication: 2000

ISBN:1-58113-184-4

Authors

H. Buhrman	CWI, PO Box 94079, 1090 GB Amsterdam, The Netherlands
P. B. Miltersen	BRICS and Department of Computer Science, University of Aarhus, 8000 Aarhus C, Denmark
J. Radhakrishnan	School of Technology and Computer Science, Tata Institute of Fundamental Research, Mumbai-400005, India
S. Venkatesh	School of Technology and Computer Science, Tata Institute of Fundamental Research, Mumbai-400005, India and BRICS at the University of Aarhus

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 26, Citation Count: 12

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	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/335305.335357 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. Bollob~s, Random Graphs, Academic Press, 1985.
	2	László Babai , Lance Fortnow , Leonid A. Levin , Mario Szegedy, Checking computations in polylogarithmic time, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.21-32, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103428]
	3	Andrej Brodnik , J. Ian Munro, Membership in Constant Time and Minimum Space, Proceedings of the Second Annual European Symposium on Algorithms, p.72-81, September 26-28, 1994
	4	V. Chv~tal, The tail of hypergeometric distribution, Discrete Mathematics, 25y285-287, 1979.
	5	Shiva Chaudhuri , Jaikumar Radhakrishnan, Deterministic restrictions in circuit complexity, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.30-36, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237824]
	6	A.G. Dyachkov and V.V. Rykov, Bounds on the length of disjunctive codes, Problemy Peredachi Informatsii, 18, No.3(1982), 7-13 {Russian}.
	7	Peter Elias , Richard A. Flower, The Complexity of Some Simple Retrieval Problems, Journal of the ACM (JACM), v.22 n.3, p.367-379, July 1975 [doi>10.1145/321892.321899]
	8	P. Erd6s, P. Frankl, and Z. F/iredi, Families of finite sets in which no set is covered by the union of r others, Israel Journal o/Mathematics, 51:79-89, 1985.
	9	Amos Fiat , Moni Naor, Implicit O(1) probe search, SIAM Journal on Computing, v.22 n.1, p.1-10, Feb. 1993 [doi>10.1137/0222001]
	10	Amos Fiat , Moni Naor , Jeanette P. Schmidt , Alan Siegel, Nonoblivious hashing, Journal of the ACM (JACM), v.39 n.4, p.764-782, Oct. 1992 [doi>10.1145/146585.146591]
	11	Gudmund Skovbjerg Frandsen , Peter Bro Miltersen , Sven Skyum, Dynamic word problems, Journal of the ACM (JACM), v.44 n.2, p.257-271, March 1997 [doi>10.1145/256303.256309]
	12	M.L. Fredman, Observations on the complexity of generating quasi-Gray codes, SIAM Journal o/Computing, 7:134-146, 1978.
	13	Michael L. Fredman, The Complexity of Maintaining an Array and Computing Its Partial Sums, Journal of the ACM (JACM), v.29 n.1, p.250-260, Jan. 1982 [doi>10.1145/322290.322305]
	14	Michael L. Fredman , János Komlós , Endre Szemerédi, Storing a Sparse Table with 0(1) Worst Case Access Time, Journal of the ACM (JACM), v.31 n.3, p.538-544, July 1984 [doi>10.1145/828.1884]
	15	Zoltán Füredi, On r-cover-free families, Journal of Combinatorial Theory Series A, v.73 n.1, p.172-173, Jan. 1996 [doi>10.1006/jcta.1996.0012 ]
	16	C T M Jacobs , P van Emde Boas, Two results on tables, Information Processing Letters, v.22 n.1, p.43-48, January 2, 1986 [doi>10.1016/0020-0190(86)90041-4 ]
	17	Eyal Kushilevitz , Rafail Ostrovsky , Yuval Rabani, Efficient search for approximate nearest neighbor in high dimensional spaces, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.614-623, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276877]
	18	Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276876]
	19	Peter Bro Miltersen, The Bit Probe Complexity Measure Revisited, Proceedings of the 10th Annual Symposium on Theoretical Aspects of Computer Science, p.662-671, February 25-27, 1993
	20	Peter Bro Miltersen , Noam Nisan , Shmuel Safra , Avi Wigderson, On data structures and asymmetric communication complexity, Journal of Computer and System Sciences, v.57 n.1, p.37-49, Aug. 1998 [doi>10.1006/jcss.1998.1577 ]
	21	M. Minsky and S. Papert, Perceptrons. MIT Press, Cambridge, Mass., 1969.
	22	Rasmus Pagh, Low Redundancy in Static Dictionaries with O(1) Worst Case Lookup Time, Proceedings of the 26th International Colloquium on Automata, Languages and Programming, p.595-604, July 11-15, 1999
	23	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]
	24	Noam Nisan , Avi Wigderson, Hardness vs. randomness, Journal of Computer and System Sciences, v.49 n.2, p.149-167, Oct. 1994 [doi>10.1016/S0022-0000(05)80043-1]
	25	Miklós Ruszinkó, On the upper bound of the size of the r-cover-free families, Journal of Combinatorial Theory Series A, v.66 n.2, p.302-310, May 1994 [doi>10.1016/0097-3165(94)90067-1]
	26	Andrew C. Yao , Frances F. Yao, Dictionary look-up with one error, Journal of Algorithms, v.25 n.1, p.194-202, Oct. 1997 [doi>10.1006/jagm.1997.0875 ]
	27	Andrew Chi-Chih Yao, Should Tables Be Sorted?, Journal of the ACM (JACM), v.28 n.3, p.615-628, July 1981 [doi>10.1145/322261.322274]

CITED BY 12

	Erik D. Demaine , Alejandro López-Ortiz, A linear lower bound on index size for text retrieval, Journal of Algorithms, v.48 n.1, p.2-15, August 2003
	Erik D. Demaine , Alejandro López-Ortiz, A linear lower bound on index size for text retrieval, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.289-294, January 07-09, 2001, Washington, D.C., United States
	Amnon Ta-Shma, Storing information with extractors, Information Processing Letters, v.83 n.5, p.267-274, 15 September 2002
	Rasmus Pagh, On the cell probe complexity of membership and perfect hashing, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.425-432, July 2001, Hersonissos, Greece
	Bernard Chazelle , Joe Kilian , Ronitt Rubinfeld , Ayellet Tal, The Bloomier filter: an efficient data structure for static support lookup tables, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Mette Berger , Esben Rune Hansen , Rasmus Pagh , Mihai Pǎtraşcu , Milan Ružić , Peter Tiedemann, Deterministic load balancing and dictionaries in the parallel disk model, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
	Amnon Ta-Shma , Christopher Umans , David Zuckerman, Loss-less condensers, unbalanced expanders, and extractors, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.143-152, July 2001, Hersonissos, Greece
	Iordanis Kerenidis , Ronald de Wolf, Exponential lower bound for 2-query locally decodable codes via a quantum argument, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Vince Grolmusz, Constructing set systems with prescribed intersection sizes, Journal of Algorithms, v.44 n.2, p.321-337, August 2002
	Anna Gál , Peter Bro Miltersen, The cell probe complexity of succinct data structures, Theoretical Computer Science, v.379 n.3, p.405-417, June, 2007
	Michael Capalbo , Omer Reingold , Salil Vadhan , Avi Wigderson, Randomness conductors and constant-degree lossless expanders, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Iordanis Kerenidis , Ronald de Wolf, Exponential lower bound for 2-query locally decodable codes via a quantum argument, Journal of Computer and System Sciences, v.69 n.3, p.395-420, November 2004