Theory

• The Complexity Of Approximate Nearest Neighbor Search With Locality Sensitive Hashing: Theoretical Bounds And Practical Tuning · 2020-02-03

  A 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-02

  A 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-01

  A 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-19

  A 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-17

  A 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-15

  A 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-10

  A 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-09

  A 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-05

  A 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-30

  A 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-23

  A 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-11

  A 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-04

  A 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-23

  A 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-19

  An 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-16

  A 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-14

  A 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-30

  A 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-22

  A 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-20

  A 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-12

  An 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-11

  A 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-02

  A 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-29

  A 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.