Software Consulting & Engineering Requirements to Production

Polkadot: Erasure-decoding algorithm optimization

2020-2022

← Back to portfolio

  • Open source
  • Rust
  • Erasure coding

Reduced the algorithmic complexity of Polkadot's erasure decoding from O(n³) to O(n log n). The improvement changed how the decoding algorithm's computational cost grows with input size, from cubic to quasilinear complexity.