The computational complexity of universal hashing

DOI10.1016/0304-3975(93)90257-TzbMath0764.68080MaRDI QIDQ1208411

Noam Nisan, Yishay Mansour, Prasoon Tiwari

Publication date: 16 May 1993

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

universal family of hash functions

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68P99: Theory of data

Related Items

: Increasing the Security and Efficiency of, Trade-offs between communication throughput and parallel time, A note on the decoding complexity of error-correcting codes, A construction method for optimally universal hash families and its consequences for the existence of RBIBDs, Pseudorandom generators for space-bounded computation, Time-space tradeoffs for branching programs, Input locality and hardness amplification, On lower bounds for read-\(k\)-times branching programs, Authenticating ad hoc networks by comparison of short digests, Bounds on the OBDD-size of integer multiplication via universal hashing

Cites Work

• Unnamed Item
• Unnamed Item
• Time-space tradeoffs for matrix multiplication and the discrete Fourier transform on any general sequential random-access computer
• Time-space tradeoffs for computing functions, using connectivity properties of their circuits
• A time-space tradeoff for sorting on non-oblivious machines
• Universal classes of hash functions
• Method of determining lower bounds for the complexity of \(\Pi\)-circuits
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
• Parallel computation for well-endowed rings and space-bounded probabilistic machines
• A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
• Communication-Space Tradeoffs for Unrestricted Protocols