Beating Fredman-Komlós for Perfect k-Hashing.

DOI10.4230/LIPICS.ICALP.2019.92MaRDI QIDQ5091253zbMATH OpenOpenAlexFDO

Authors Andrii Riazanov, Venkatesan Guruswami

Publication date 21 July 2022

Full work available at URL http://arxiv.org/pdf/1805.04151.pdf

zbMATH Keywords

coding theorygraph entropyhash familyperfect hashingzero-error information theory

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Recommendations

• Beating Fredman-Komlós for perfect \(k\)-hashing
• New bounds for perfect \(k\)-hashing
• Beating the probabilistic lower bound on \(q\)-perfect hashing
• New bounds for perfect hashing via information theory
• scientific article; zbMATH DE number 1498827

Cites work

• An upper bound on the zero-error list-coding capacity
• Fredman–Komlós bounds and information theory
• scientific article; zbMATH DE number 3468645 (Why is no real title available?)
• scientific article; zbMATH DE number 3261634 (Why is no real title available?)
• New bounds for perfect hashing via information theory
• On the Size of Separating Systems and Families of Perfect Hash Functions
• Perfect Hashing and Probability
• Zero error capacity under list decoding

Cited in

(5)

• A generalization of the Bollobás set pairs inequality
• New bounds for perfect \(k\)-hashing
• Beating the probabilistic lower bound on \(q\)-perfect hashing
• The maximum cardinality of trifferent codes with lengths 5 and 6
• Sharp threshold rates for random codes

This page was built for publication: Beating Fredman-Komlós for Perfect k-Hashing.

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