Blog
Posts, notes, and articles.
The Complexity Of Approximate Nearest Neighbor Search With Locality Sensitive Hashing: Theoretical Bounds And Practical Tuning
2020-02-03A comprehensive technical exploration of the complexity of approximate nearest neighbor search with locality sensitive hashing: theoretical bounds and practical tuning, covering key concepts, practical implementations, and real-world applications.
Implementing A Distributed Graph Processing System Using Pregel: Vertex Centric Bsp And Checkpointing
2020-02-02A comprehensive technical exploration of implementing a distributed graph processing system using pregel: vertex centric bsp and checkpointing, covering key concepts, practical implementations, and real-world applications.
Submodular Optimization: Diminishing Returns, the (1-1/e) Greedy Guarantee, and Machine Learning Applications
2020-02-01A comprehensive study of submodular functions—the discrete analog of convexity—the greedy algorithm's optimal approximation, and applications in active learning and summarization.
Matroid Theory: The Greedy Exchange Property, Matroid Intersection, and Applications in Spanning Trees and Matching
2020-01-19A thorough exploration of matroid theory—the algebraic abstraction that explains why greedy algorithms work—matroid intersection, and their applications in combinatorial optimization.
The Analysis Of Consistent Hashing Under Churn: Virtual Nodes, Power Law Distributions, And Load Balancing
2020-01-17A comprehensive technical exploration of the analysis of consistent hashing under churn: virtual nodes, power law distributions, and load balancing, covering key concepts, practical implementations, and real-world applications.
Fair Division: Cut-and-Choose, Selfridge-Conway, Brams-Taylor, and the Mathematics of Envy-Freeness
2020-01-15A rigorous exploration of fair division—from cake-cutting protocols to envy-free allocations—and their application to cloud resource allocation and beyond.
A Polynomial Time Algorithm For Minimum Steiner Tree In The Plane Using Dynamic Programming On Decompositions
2020-01-10A comprehensive technical exploration of a polynomial time algorithm for minimum steiner tree in the plane using dynamic programming on decompositions, covering key concepts, practical implementations, and real-world applications.
Building An Online Algorithm For The K Server Problem Using Work Function And Caching Policies
2020-01-09A comprehensive technical exploration of building an online algorithm for the k server problem using work function and caching policies, covering key concepts, practical implementations, and real-world applications.
The Numerical Stability Of Fast Fourier Transform Algorithms: Decimation In Time Vs. Frequency With Twiddle Factors
2020-01-05A comprehensive technical exploration of the numerical stability of fast fourier transform algorithms: decimation in time vs. frequency with twiddle factors, covering key concepts, practical implementations, and real-world applications.
Implementing A Cache Oblivious Matrix Multiplication Algorithm With Block Recursive Layouts
2019-12-30A comprehensive technical exploration of implementing a cache oblivious matrix multiplication algorithm with block recursive layouts, covering key concepts, practical implementations, and real-world applications.
Mechanism Design: VCG Auctions, the Revelation Principle, and the Architecture of Truthfulness
2019-12-23A deep exploration of mechanism design—the VCG mechanism, Myerson optimal auction, incentive compatibility, and how to design games where truth-telling is a dominant strategy.
A Quantitative Comparison Of Sorting Algorithms On Modern Cpu Architectures: Radix Sort Vs. Quicksort With Simd
2019-12-11A comprehensive technical exploration of a quantitative comparison of sorting algorithms on modern cpu architectures: radix sort vs. quicksort with simd, covering key concepts, practical implementations, and real-world applications.
Designing A Mapreduce Framework From Scratch: Job Scheduling, Data Locality, And Fault Tolerance
2019-12-04A comprehensive technical exploration of designing a mapreduce framework from scratch: job scheduling, data locality, and fault tolerance, covering key concepts, practical implementations, and real-world applications.
Algorithmic Game Theory: Nash Equilibrium Computation, PPAD-Completeness, and the Computational Lens on Strategy
2019-11-23A rigorous look at algorithmic game theory—computing Nash equilibria, the PPAD complexity class, and how computational constraints reshape strategic reasoning.
Smoothed Analysis: Why Simplex Works in Practice and the Spielman-Teng Framework
2019-11-19An exploration of smoothed analysis—Spielman and Teng's framework that explains why the simplex method and other algorithms transcend their worst-case bounds.
The Algebra Of Concurrent Programming: Modeling With Process Calculi Like Csp And Pi Calculus
2019-11-16A comprehensive technical exploration of the algebra of concurrent programming: modeling with process calculi like csp and pi calculus, covering key concepts, practical implementations, and real-world applications.
Implementing A Work Stealing Task Scheduler With Locality Aware Dequeues In Rust
2019-11-14A comprehensive technical exploration of implementing a work stealing task scheduler with locality aware dequeues in rust, covering key concepts, practical implementations, and real-world applications.
The Empirical Performance Of Spin Locks, Mutexes, And Sleep Locks On Multicore Systems
2019-10-30A comprehensive technical exploration of the empirical performance of spin locks, mutexes, and sleep locks on multicore systems, covering key concepts, practical implementations, and real-world applications.
Building A Concurrent B Tree With Optimistic Lock Coupling And Smo Safety
2019-10-22A comprehensive technical exploration of building a concurrent b tree with optimistic lock coupling and smo safety, covering key concepts, practical implementations, and real-world applications.
Average-Case Complexity: Levin's Distributional Problems, AvgP, and Cryptographic Implications
2019-10-20A deep examination of average-case complexity—Levin's theory of distributional NP-completeness, the class AvgP, and why cryptography needs hard-on-average problems.
Descriptive Complexity: Fagin's Theorem, Logic, and an Alternative to Turing Machines
2019-10-12An exploration of descriptive complexity—where computational classes are characterized by logical definability—and Fagin's theorem that NP equals existential second-order logic.
A Deep Dive Into The Memory Model Of C++11: Acquire Release Semantics And Sequential Consistency
2019-10-11A comprehensive technical exploration of a deep dive into the memory model of c++11: acquire release semantics and sequential consistency, covering key concepts, practical implementations, and real-world applications.
Designing A Transactional Memory System With Hardware Support: Htm Vs. Software Tm On Modern Cpus
2019-10-02A comprehensive technical exploration of designing a transactional memory system with hardware support: htm vs. software tm on modern cpus, covering key concepts, practical implementations, and real-world applications.
Circuit Complexity: AC0, NC, P/poly, and the PARITY ∉ AC0 Proof
2019-09-29A rigorous journey through circuit complexity classes—AC0, NC, P/poly—and the landmark result that PARITY cannot be computed by constant-depth polynomial-size circuits.