Article

Lower Bounds for Static Dictionaries on RAMs with Bit Operations But No Multiplication

Author:

Peter Bro MiltersenAuthors Info & Claims

ICALP '96: Proceedings of the 23rd International Colloquium on Automata, Languages and Programming

Pages 442 - 453

Published: 08 July 1996 Publication History

Abstract

No abstract available.

Cited By

View all

Aamand AKnudsen JKnudsen MRasmussen PThorup MMakarychev KMakarychev YTulsiani MKamath GChuzhoy J(2020)Fast hashing with strong concentration boundsProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3357713.3384259(1265-1278)Online publication date: 22-Jun-2020
https://dl.acm.org/doi/10.1145/3357713.3384259
Goodrich M(2017)Answering Spatial Multiple-Set Intersection Queries Using 2-3 Cuckoo Hash-FiltersProceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/3139958.3140021(1-4)Online publication date: 7-Nov-2017
https://dl.acm.org/doi/10.1145/3139958.3140021
Eppstein DGoodrich MMitzenmacher MTorres MSallinger EVan den Bussche JGeerts F(2017)2-3 Cuckoo Filters for Faster Triangle Listing and Set IntersectionProceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3034786.3056115(247-260)Online publication date: 9-May-2017
https://dl.acm.org/doi/10.1145/3034786.3056115
Show More Cited By

Lower Bounds for Static Dictionaries on RAMs with Bit Operations But No Multiplication
1. Theory of computation

Recommendations

Decimal Floating-Point Multiplication

Decimal multiplication is important in many commercial applications including financial analysis, banking, tax calculation, currency conversion, insurance, and accounting. This paper presents the design of two decimal floating-point multipliers: one ...
Bit-Serial and Bit-Parallel Montgomery Multiplication and Squaring over GF(2^m)

Multiplication and squaring are main finite field operations in cryptographic computations and designing efficient multipliers and squarers affect the performance of cryptosystems. In this paper, we consider the Montgomery multiplication in the binary ...
Montgomery Multiplication with Twice the Bit-Length of Multipliers

We present a novel approach for computing 2 n -bit Montgomery multiplications with n -bit hardware Montgomery multipliers. Smartcards are usually equipped with such hardware Montgomery multipliers; however, due to progresses in factoring algorithms, the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ICALP '96: Proceedings of the 23rd International Colloquium on Automata, Languages and Programming

July 1996

680 pages

ISBN:3540614400

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 08 July 1996

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Aamand AKnudsen JKnudsen MRasmussen PThorup MMakarychev KMakarychev YTulsiani MKamath GChuzhoy J(2020)Fast hashing with strong concentration boundsProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3357713.3384259(1265-1278)Online publication date: 22-Jun-2020
https://dl.acm.org/doi/10.1145/3357713.3384259
Goodrich M(2017)Answering Spatial Multiple-Set Intersection Queries Using 2-3 Cuckoo Hash-FiltersProceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/3139958.3140021(1-4)Online publication date: 7-Nov-2017
https://dl.acm.org/doi/10.1145/3139958.3140021
Eppstein DGoodrich MMitzenmacher MTorres MSallinger EVan den Bussche JGeerts F(2017)2-3 Cuckoo Filters for Faster Triangle Listing and Set IntersectionProceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3034786.3056115(247-260)Online publication date: 9-May-2017
https://dl.acm.org/doi/10.1145/3034786.3056115
Christiani TPagh RThorup MServedio RRubinfeld R(2015)From Independence to Expansion and Back AgainProceedings of the forty-seventh annual ACM symposium on Theory of Computing10.1145/2746539.2746620(813-820)Online publication date: 14-Jun-2015
https://dl.acm.org/doi/10.1145/2746539.2746620
Thorup M(2003)On AC0 implementations of fusion trees and atomic heapsProceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/644108.644221(699-707)Online publication date: 12-Jan-2003
https://dl.acm.org/doi/10.5555/644108.644221
(2002)Randomized Sorting in O(nloglogn) Time and Linear Space Using Addition, Shift, and Bit-wise Boolean OperationsJournal of Algorithms10.1006/jagm.2002.121142:2(205-230)Online publication date: 1-Feb-2002
https://dl.acm.org/doi/10.1006/jagm.2002.1211
Thorup MSaks M(1997)Randomized sorting in O(n log log n) time and linear space using addition, shift, and bit-wise boolean operationsProceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms10.5555/314161.314319(352-359)Online publication date: 5-Jan-1997
https://dl.acm.org/doi/10.5555/314161.314319

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

Cited By

Recommendations

Decimal Floating-Point Multiplication

Bit-Serial and Bit-Parallel Montgomery Multiplication and Squaring over GF(2^m)

Montgomery Multiplication with Twice the Bit-Length of Multipliers

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations