An O(n log n) algorithm for the generalized birthday problem

DOI10.1016/S0167-9473(96)00051-5MaRDI QIDQ1391985zbMATH OpenOpenAlexWikidataFDO

Authors Paul Wright, Frank K. Hwang

Publication date 23 July 1998

Published in Computational Statistics and Data Analysis (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0167-9473(96)00051-5

zbMATH Keywords

Birthday problemsClusteringComplexityReliability

Mathematics Subject Classification ID

Combinatorial probability (60C05) Reliability and life testing (62N05)

Recommendations

• scientific article; zbMATH DE number 58016
• A Generalized Birthday Problem
• scientific article; zbMATH DE number 1942427

Cites work

• A direct algorithm for computing reliability of a consecutive-k cycle
• Coincidence probabilities
• Computing the stationary distribution for infinite Markov chains
• Fast Solutions for Consecutive-k-out-of-n: F System
• scientific article; zbMATH DE number 193132 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 806872 (Why is no real title available?)
• scientific article; zbMATH DE number 3187993 (Why is no real title available?)
• Note on a clustering problem
• On the Consecutive-k-of-n:F System
• Probabilities for a Generalized Birthday Problem
• Recurrent events in a Markov chain
• Reliability of Consecutive-k-out-of-n:F System
• The first run preceded by a quota
• The Generalized Birthday Problem

Cited in

(8)

• A method for calculating probability convolution using ``trinary numbers with application in the determination of twin zygosity.
• An algorithmic framework for the generalized birthday problem
• Refinements of the k-tree Algorithm for the Generalized Birthday Problem
• A non-uniform birthday problem with applications to discrete logarithms
• scientific article; zbMATH DE number 708852 (Why is no real title available?)
• scientific article; zbMATH DE number 1942427 (Why is no real title available?)
• Two Birthday Problems
• Asymptotic results for the number of Wagner's solutions to a generalised birthday problem

This page was built for publication: An O(n log n) algorithm for the generalized birthday problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1391985)