Randomized Algorithms Everywhere: Why Randomness Beats Determinism in Production
arpit_bhayani · x · 2026-11-05
Engineer Arpit Bhayani explains why randomized algorithms are so practical: random pivot selection turns Quicksort's worst-case O(n²) into expected O(n log n) with no predictable bad inputs.
- Shrinkable error: Miller-Rabin errs with probability ≤1/4 per round; 40 independent rounds bring it to 4^-40 — far below the odds of a cosmic ray flipping a bit in your RAM
- Where randomness shows up in production: hash tables (thwarting adversarial collisions), skip lists (expected balanced-tree performance with no rebalancing), Bloom filters and HyperLogLog (tiny error for big memory savings), power-of-two-choices load balancing
- What randomization buys: simplicity, adversarial-input protection, and speed when the best deterministic algorithm is slower or unknown
His takeaway: sometimes the simplest way to make an algorithm reliable is to stop trying to make it deterministic.
More from Research
- Berkeley team shows LLMs lose info via recursive self-summarization, fixes it with RL — berkeley_ai · 2026-11-05
- ReproEvalCard: a reporting standard for reproducible LLM pipeline evaluation — kalyan_kpl · 2026-11-05
- Harvard's Gary King Team Launches Certify: Agent-Automated Replication Certification for Journals — RexDouglass · 2026-11-05
- RETROGRADE benchmark round 0: 14 frontier models blind-tested, obfuscation hurts every one — amplifiedamp · 2026-11-05
- imec Ball-Lens Scheme Cuts Photonic Chip-to-Board Coupling Loss to 3.4dB via Substrate Vias — jwt0625 · 2026-11-05
- Google Paper Details 81-Satellite Cluster for Orbital AI Datacenters — sebkrier · 2026-11-05