The computational complexity of universal hashing

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

Noam Nisan, Prasoon Tiwari, Yishay Mansour

Publication date: 16 May 1993

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

Full work available at URL: https://doi.org/10.1016/0304-3975(93)90257-t

zbMATH Keywords

universal family of hash functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Theory of data (68P99)

Related Items

On lower bounds for read-\(k\)-times branching programs ⋮ The average sensitivity of bounded-depth circuits ⋮ 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 ⋮ Universal Hashing via Integer Arithmetic Without Primes, Revisited ⋮ Input locality and hardness amplification ⋮ A subquadratic algorithm for 3XOR ⋮ RIV for Robust Authenticated Encryption ⋮ Pseudorandom generators for space-bounded computation ⋮ Authenticating ad hoc networks by comparison of short digests ⋮ Trade-offs between communication throughput and parallel time ⋮ : Increasing the Security and Efficiency of ⋮ Tight time-space lower bounds for finding multiple collision pairs and their applications ⋮ Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle ⋮ Bounds on the OBDD-size of integer multiplication via universal hashing ⋮ Time-space tradeoffs for branching programs

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