Main Content

Signal Processing

• The Fast Fourier Transform Algorithm, and Denoising a Sound Clip
• The Two-Dimensional Fourier Transform and Digital Watermarking
• Making Hybrid Images
• The Welch-Berlekamp Algorithm for Correcting Errors in Data

Machine Learning and Data Mining

• Introduction
• K-Nearest-Neighbors and Handwritten Digit Classification The Perceptron, and All the Things it Can’t Perceive
• Decision Trees and Political Party Classification
• Neural Networks and the Backpropagation Algorithm
• K-Means Clustering and Birth Rates
• Linear Regression
• Regression and Linear Combinations
• Eigenfaces, for Facial Recognition (via Principal Component Analysis)
• Bandit Learning: the UCB1 Algorithm
• Bandit Learning: the EXP3 Algorithm
• Bandits and Stocks
• Weak Learning, Boosting, and the AdaBoost Algorithm
• Fairness in machine learning
  • Introduction - Statistical parity
• The Johnson-Lindenstrauss Transform
• Singular Value Decomposition
  • Motivation
  • Algorithms
• Support Vector Machines
  • Inner products
  • Primal problem - Dual problem

Graphs and Network Science

• Binary Search on Graphs
• Trees and Tree Traversal
• Breadth-First and Depth-First Search
• The Erdős-Rényi Random Graph
• The Giant Component and Explosive Percolation
• Zero-One Laws for Random Graphs
• Community Detection in Graphs, a Casual Tour
• Google’s PageRank Algorithm: Introduction
• A First Attempt
• The Final Product
• Why It Doesn’t Work Anymore

Combinatorial Optimization

• When Greedy is Good Enough: Submodularity and the 1 – 1/e Approximation
• When Greedy Algorithms are Perfect: the Matroid
• Linear Programming and Healthy Diets Part 1
• Linear Programming and the Simplex Algorithm
• Linear Programming and Healthy Diets Part 2
• The Many Faces of Set Cover
• Optimization Models for Subset Cover

Art & Graphics

• Making Hybrid Images
• Bezier Curves and Picasso
• Random Psychedelic Art
• Seam-carving for Content-Aware Image Scaling
• The Cellular Automaton Method for Procedural Cave Generation
• Designing Non-repeating Patterns with Prime Numbers

Algorithmic Game Theory

• Stable Marriages and Designing Markets
• Serial Dictatorships and Housing Allocation
• Silent Duels and an Old Paper of Restrepo
• Silent Duels—Parsing the Construction
• Silent Duels—Constructing the Solution part 1
• Silent Duels—Constructing the Solution part 2

Software Engineering

• Searching for RH Counterexamples
  • Setting up Pytest
  • Adding a Database
  • Search Strategies
  • Unbounded Integers
  • Deploying with Docker
  • Performance Profiling
  • Productionizing
  • Exploring data

Quantum Computing

• A Motivation for Quantum Computing
• The Quantum Bit
• Multiple Qubits and the Quantum Circuit
• Concrete Examples of Quantum Gates

Cryptography

• RSA
• Elliptic curves
  • Introduction
  • Elliptic Curves as Elementary Equations
  • Elliptic Curves as Algebraic Structures
  • Elliptic Curves as Python Objects (over the rational numbers)
  • Programming with Finite Fields
  • Connecting Elliptic Curves with Finite Fields
  • Elliptic Curve Diffie-Hellman
  • Sending and Authenticating Messages with Elliptic Curves (Shamir-Massey-Omura and ElGamal)
• The Mathematics of Secret Sharing
• Zero Knowledge Proofs
  • A Primer
  • Zero Knowledge Proofs for NP
  • Definitions and Theory
• Fully homomorphic encryption:
  • A High-Level Technical Overview of Fully Homomorphic Encryption
  • Fully Homomorphic Encryption in Production Systems
  • The Gadget Decomposition in FHE
  • Modulus Switching in LWE
  • Key Switching in LWE
  • Sample Extraction from RLWE to LWE
  • Negacyclic Polynomial Multiplication
  • Estimating the Security of Ring Learning With Errors
  • Encoding schemes in FHE
  • Shift Networks
  • Packing Matrix-Vector Multiplication
  • Google’s Fully Homomorphic Encryption Compiler (Tutorial)

Streaming and Sublinear Algorithms

• Load Balancing and the Power of Hashing
• Program Gallery entries

Natural Language

• Metrics on Words
• Word Segmentation, or Makingsenseofthis
• Cryptanalysis with N-Grams

Computational Category Theory

• A Sample of Standard ML (and a Preview of Monoids)
• Categories, What’s the Point?
• Introducing Categories
• Categories as Types
• Properties of Morphisms
• Universal Properties
• Functoriality
• The Universal Properties of Map, Fold, and Filter

Computational Topology

• Computing Homology
• Fixing Bugs in Computing Homology
• The Čech complex and the Vietoris-Rips complex

Games

• The Wild World of Cellular Automata
• Turing Machines and Conway’s Dreams
• Conway’s Game of Life in Conway’s Game of Life
• Optimally Stacking the Deck: Kicsi Poker
• Optimally Stacking the Deck: Texas Hold ‘Em
• Want to make a great puzzle game? Get inspired by theoretical computer science
• Socks: a matching game based on an additive combinatorics problem

Miscellaneous

• Two’s Complement and Group Theory
• Group Actions and Hashing Unordered Multisets
• A Working Mathematician’s Guide to Parsing
• A Quasipolynomial Time Algorithm for Graph Isomorphism: The Details
• The Reasonable Effectiveness of the Multiplicative Weights Update Algorithm
• Taylor Series and Accelerometers
• Hunting Serial Killers
• Learning to Love Complex Numbers
• Holidays and Homicide
• Numerical Integration
• Busy Beavers, and the Quest for Big Numbers
• Row Reduction over a Field
• Complete Sequences and Magic Tricks
• Well Orderings and Search

Essays

• Teaching Mathematics – Graph Theory
• Learning Programming – Finger-Painting and Killing Zombies
• Why There’s no Hitchhiker’s Guide to Mathematics
• Attention spans for math and stories

Guest Posts

• Math and Baking: Torus-Knotted Baklava
• With High Probability: What’s up with Graph Laplacians?