Sample(x)=(a*x<=t) Is a Distinguisher with Probability 1/8

DOI10.1137/16M1059461zbMath1409.68194arXiv1411.4982MaRDI QIDQ4562282

Mikkel Thorup

Publication date: 19 December 2018

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1411.4982

zbMATH Keywords

samplinghashingdistinguishersmall-bias probability spaces

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the power of two-point based sampling
• New hash functions and their use in authentication and set equality
• A probabilistic algorithm for verifying matrix products using \(O(n^ 2)\) time and \(\log_ 2n+O(1)\) random bits
• Universal classes of hash functions
• The space complexity of approximating the frequency moments
• Construction and Impromptu Repair of an MST in a Distributed Network with o(m) Communication
• Tabulation-Based 5-Independent Hashing with Applications to Linear Probing and Second Moment Estimation
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Simple Constructions of Almost k-wise Independent Random Variables
• Addendum to “simple constructions of almost k-wise independent random variables”
• A Reliable Randomized Algorithm for the Closest-Pair Problem
• Universal hashing and k-wise independent random variables via integer arithmetic without primes
• The Power of Simple Tabulation Hashing
• Dynamic graph connectivity in polylogarithmic worst case time

This page was built for publication: Sample(x)=(a*x<=t) Is a Distinguisher with Probability 1/8