An improved analysis of linear mergers

DOI10.1007/S00037-007-0223-ZMaRDI QIDQ2472428zbMATH OpenOpenAlexFDO

Authors Zeev Dvir, Amir Shpilka

Publication date 22 February 2008

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00037-007-0223-z

zbMATH Keywords

extractorsKakeyamergersrandomness

Mathematics Subject Classification ID

Randomized algorithms (68W20) Analysis of algorithms (68W40)

Recommendations

• Analyzing linear mergers
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Merging by Decomposition Revisited
• scientific article; zbMATH DE number 4001497
• Merging of linear combinations to semistable laws
• Average-case analysis of the merging algorithm of Hwang and Lin
• The analysis of a simple in-place merging algorithm
• A note on merging
• An efficient multiway merging algorithm

Cited in

(9)

• How to extract useful randomness from unreliable sources
• Kakeya sets, new mergers, and old extractors
• Local correlation breakers and applications to three-source extractors and mergers
• Analyzing linear mergers
• Extensions to the method of multiplicities, with applications to Kakeya sets and mergers
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Extractor Lower Bounds, Revisited
• Testing sumsets is hard
• Merging of linear combinations to semistable laws

This page was built for publication: An improved analysis of linear mergers

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