Graduate-level algorithmic theory with applications to cryptography, blockchain consensus, and distributed systems.
Algorithms & Complexity
- FFT-based integer multiplication achieving O(n log n), disproving Kolmogorov's Ω(n²) conjecture
- Selection algorithm with groups of 6: formal proof of O(n) via recurrence analysis
- Dynamic programming: 2-Knapsack O(nK²), longest increasing subsequence O(n²)
- Graph algorithms: Dijkstra, Bellman-Ford, Floyd-Warshall with correctness proofs
Cryptography & Zero-Knowledge Proofs
- Birthday attack analysis: collision finding in O(2^(n/2)) time with O(2^(n/2)) space
- Fiat-Shamir signatures over finite fields with discrete logarithm security
- Hash function properties: collision resistance vs. puzzle-friendliness separation
- Merkle tree optimization: k-ary trees with (k-1)⌈log_k(n)⌉ proof size
Distributed Systems Theory
- FLP impossibility: proof that asynchronous consensus is impossible with ≥1 crash fault
- Nakamoto consensus analysis: orphaned block rates under network delay Δ
- Bitcoin Script: multisig escrow, hash-locked payment channels, time-locked refunds
- Transaction malleability attacks and SegWit mitigation
Probabilistic Methods
- Chernoff bounds: formal derivation via MGF, proving Pr(X ≤ (1-δ)μ) ≤ e^(-μδ²/2)
- Randomized algorithms: vertex cover 2-approximation, quickselect analysis
- Tail probability applications to blockchain security guarantees
Network Flow & Linear Programming
- Min-cost flow formulation with Python implementation
- Shortest path as LP: flow conservation constraints
- Bipartite matching for constrained assignment problems
All solutions include formal proofs using probability theory, abstract algebra, graph theory, and asymptotic analysis. Topics span P vs NP, computational hardness assumptions, and Byzantine fault tolerance.
Focus Areas: Algorithms • Cryptography • Blockchain • Distributed Consensus • Complexity Theory