13 Research and Industry Applications - Where Algorithms Meet Reality
From theory to durable computational ideas
13.1 Introduction: Algorithms in the Wild
Algorithms connect mathematical models to deployed systems. Search and recommendation combine indexing, graph methods, optimization, and learning; distributed data processing relies on partitioning and fault-tolerant coordination; and scientific computing combines numerical algorithms with learned models. AlphaGo demonstrated how tree search and deep learning can work together (Silver et al. 2016), while AlphaFold showed that learned systems can produce highly accurate protein-structure predictions (Jumper et al. 2021). These examples matter because of their algorithmic structure, not transient valuations or usage statistics.
In this chapter, we’ll explore: 1. What problems algorithm researchers are tackling right now 2. How algorithms power modern AI and machine learning 3. The challenges of processing data at planetary scale 4. How cryptography keeps our digital world secure 5. The ethical implications when algorithms make life-changing decisions 6. How you can contribute to algorithmic research
Let’s see where algorithms are taking us!
13.2 Current Directions in Algorithm Research
13.2.1 Beyond Worst-Case Analysis: Algorithms for the Real World
For decades, algorithm analysis focused obsessively on worst-case complexity. If quicksort has \(O(n^2)\) worst case, we worried about it constantly, even though it almost never happens in practice.
But around 2000, researchers started asking: “What if we analyzed algorithms the way they actually perform?”
This led to several revolutionary frameworks:
13.2.1.1 Smoothed Analysis
Smoothed analysis asks how an algorithm performs when an adversarial input is subjected to a small random perturbation (Spielman and Teng 2004).
Why this matters: Real-world inputs are never perfectly adversarial. There’s always some randomness—measurement errors, rounding, unpredictable human behavior.
Classic example - The Simplex Algorithm:
The simplex algorithm (1947) for linear programming has exponential worst-case complexity, but works incredibly well in practice. For 50 years, this was a mystery.
Spielman and Teng proved a polynomial smoothed-complexity bound for a particular simplex pivot rule under a Gaussian perturbation model (Spielman and Teng 2004). This is more precise than claiming that arbitrary noise makes every simplex implementation polynomial.
Impact: This earned Spielman the Nevanlinna Prize (essentially the Nobel of computer science). It explained why many algorithms work far better than their worst-case suggests.
import random
def demonstrate_smoothed_analysis():
"""
Illustrate input perturbation with an explicit deterministic quicksort.
Worst-case input: sorted array → O(n²)
Perturbation often reduces the comparison count substantially.
This experiment is an illustration, not a proof of a smoothed bound.
"""
print("=== Smoothed Analysis: Quicksort ===\n")
def quicksort_comparisons(values):
"""Sort a copy using last-element pivots and count comparisons."""
values = values.copy()
comparisons = 0
stack = [(0, len(values) - 1)]
while stack:
low, high = stack.pop()
if low >= high:
continue
pivot = values[high]
boundary = low
for index in range(low, high):
comparisons += 1
if values[index] <= pivot:
values[boundary], values[index] = values[index], values[boundary]
boundary += 1
values[boundary], values[high] = values[high], values[boundary]
stack.extend(((low, boundary - 1), (boundary + 1, high)))
return values, comparisons
n = 2000
# Worst-case input: sorted array
sorted_array = list(range(n))
# Add tiny noise (smoothing)
smoothed_array = sorted_array.copy()
noise_level = 0.01 # Swap 1% of elements
num_swaps = max(1, int(n * noise_level))
rng = random.Random(2026)
for _ in range(num_swaps):
i, j = rng.randrange(n), rng.randrange(n)
smoothed_array[i], smoothed_array[j] = smoothed_array[j], smoothed_array[i]
worst_result, worst_comparisons = quicksort_comparisons(sorted_array)
smoothed_result, smoothed_comparisons = quicksort_comparisons(smoothed_array)
assert worst_result == sorted(sorted_array)
assert smoothed_result == sorted(smoothed_array)
print(f"Array size: {n:,}")
print(f"Noise level: {noise_level*100}% element swaps")
print(f"\nSorted-input comparisons: {worst_comparisons:,}")
print(f"Perturbed-input comparisons: {smoothed_comparisons:,}")
print("\nKey insight: this pivot rule is highly sensitive to input order.")
print("A single experiment does not establish an asymptotic smoothed bound.")13.2.1.2 Instance-Optimal Algorithms
An algorithm is instance-optimal if it’s the best possible for every input, not just worst-case.
Example: Fagin et al.’s instance-optimal join algorithms (2003) for database queries. These algorithms detect what kind of join you’re doing (easy or hard) and adapt automatically.
Why this matters: Traditional “one-size-fits-all” algorithms are being replaced by algorithms that adapt to input characteristics.
13.2.1.3 Fine-Grained Complexity
Around 2015, researchers realized: many problems seem to require specific running times (like \(O(n^2)\) for edit distance), and we can’t do better even though we can’t prove it.
The Strong Exponential Time Hypothesis (SETH): A conjecture that k-SAT requires 2^n time for some k.
If SETH is true, it implies lower bounds for hundreds of problems: - Edit distance requires \(\Omega(n^2)\) - Longest common subsequence requires \(\Omega(n^2)\) - Frequent itemset mining requires exponential time
Impact: Conditional lower bounds explain why improving one problem beyond a conjectured threshold would also require breakthroughs for a broader class of problems. They are conditional results, not unconditional proofs of impossibility.
Research direction: Fine-grained reductions map which problems share conjectured time barriers. An improvement for one problem can therefore imply improvements for others connected by those reductions.
13.2.2 Quantum Algorithms and Engineering Constraints
Quantum processors are available through laboratories and cloud services, but qubit count alone does not measure useful computational capability. Gate fidelity, connectivity, error rates, circuit depth, and error-correction overhead determine which algorithms can run meaningfully. Large-scale fault-tolerant quantum computation remains an active engineering challenge.
But here’s the crucial question: What can quantum computers actually do?
13.2.2.1 Shor’s Algorithm and Public-Key Cryptography
Shor gave polynomial-time quantum algorithms for integer factorization and discrete logarithms (Shor 1997). Exact gate complexity depends on the arithmetic model and implementation, so a single simplified exponent is not universal.
Why this matters: RSA relies on arithmetic assumptions that do not hold against a sufficiently capable fault-tolerant quantum computer. Running the attack would still require a large error-corrected computation; “polynomial time” does not mean instantaneous.
How it works (simplified): 1. Factoring N reduces to finding the period of a function f(x) = a^x mod N 2. Quantum computers can find periods exponentially faster using the Quantum Fourier Transform 3. Once you know the period, you can factor N efficiently
No reliable date can be assigned to a cryptographically relevant quantum computer. The durable engineering response is risk-managed migration: NIST finalized FIPS 203, 204, and 205 in 2024 for quantum-resistant key establishment and signatures and continues to publish transition guidance (National Institute of Standards and Technology 2024).
13.2.2.2 Grover’s Algorithm: Quantum Search
Grover’s algorithm gives a quadratic quantum query improvement for unstructured search, from linear to \(O(\sqrt N)\) oracle queries (Grover 1996).
Why this matters: This is a provable quadratic speedup for a fundamental problem.
Implications: - Brute-force search: If classical takes 2^128 operations, quantum takes 2^64 (still hard, but concerning) - Symmetric cryptography: Need to double key sizes (AES-128 → AES-256) - NP-complete problems: Get √ speedup (not enough to solve them efficiently, but still significant)
The intuition: Classical search checks possibilities one by one. Quantum search uses “amplitude amplification” to boost the probability of the correct answer, checking many possibilities simultaneously through superposition.
13.2.2.3 Quantum Simulation
Quantum simulation is a central motivation for quantum computing because the state space of a general quantum system grows exponentially with the number of modeled components.
Why classical computers struggle: Simulating n quantum particles requires 2^n classical bits. For just 300 particles, that’s more atoms than in the universe!
Quantum advantage: Quantum computers naturally simulate quantum systems efficiently.
Research targets include molecular energy estimation, materials models, optimization subroutines, and quantum machine-learning methods. A proposed quantum algorithm should be evaluated against the best classical baseline and include state preparation, error correction, and measurement costs.
13.2.2.4 The Limitations
Important reality check: Quantum computers aren’t magic.
What quantum computers DON’T speed up: - Sorting: Still \(\Omega(n log n)\) (maybe √n speedup on some measures) - Graph problems: Most remain hard - Matrix multiplication: No proven speedup - Database operations: No fundamental speedup beyond Grover
The engineering challenge: Noise and decoherence corrupt quantum states. Useful resource estimates must model gate errors, circuit depth, connectivity, measurement, and correction overhead.
Error correction: A logical qubit is encoded across many physical components, with overhead determined by the code, hardware error model, and target reliability. Fixed ratios and arrival dates quickly become misleading; resource estimates must state their assumptions.
13.2.3 Learning-Augmented Algorithms: When ML Meets Classical CS
Imagine combining the worst-case guarantees of classical algorithms with the pattern-recognition power of machine learning. That’s the promise of learning-augmented algorithms.
13.2.3.1 The Concept
Traditional algorithms: Designed by humans, work for all inputs, worst-case guarantees.
Machine learning: Learn from data, work great on typical inputs, no guarantees.
Learning-augmented algorithms: Use ML predictions + classical algorithms as backup.
The framework (Lykouris and Vassilvitskii 2018): - ML provides “hints” or predictions - Algorithm uses hints when they’re good - Falls back to classical algorithm when predictions are wrong - Guarantee: Never worse than \(O(α)\) × classical, often much better
13.2.3.2 Learned Index Structures
Learned index structures model the position of a key in an ordered collection and use a conventional correction step when the prediction is imperfect (Kraska et al. 2018).
Traditional B-tree index: \(O(log n)\) lookup, works for any data distribution.
Learned index: Train neural network to predict position of key in sorted array. When predictions are accurate, lookup is \(O(1)\)!
The trick: Use B-tree as safety net. Structure is:
Prediction: NN(key) → approximate position
Verify: Check nearby positions
Fallback: If not found quickly, use B-treeReported results depend on the dataset, baseline, model size, and hardware. Prediction and correction costs must both be included in a comparison.
Why it works: Real data has patterns! Dates, IDs, names follow distributions ML can learn.
13.2.3.3 Learned Caching
Cache eviction (which item to remove when cache is full) is fundamental to systems performance.
Traditional: LRU (Least Recently Used) - Evict item unused for longest time - No lookahead, purely reactive
Learning-augmented: Belady-inspired - ML predicts when items will be used next - Evict item that won’t be needed for longest time - Falls back to LRU if predictions are poor
The theoretical objective is consistency when predictions are accurate and robustness when they are not; empirical hit-rate improvements remain workload-dependent (Lykouris and Vassilvitskii 2018).
13.2.3.4 Learned Optimizers
Database query optimization is NP-hard. Traditional optimizers use heuristics.
Learned optimizers (Marcus & Papaemmanouil, 2018): - Train on past query execution times - Learn which join orders, which indexes to use - Adapt to specific workload patterns
Results: PostgreSQL with learned optimizer: 2-3x faster on analytics workloads.
Deployment: Still mostly research, but major databases (Oracle, SQL Server) are incorporating ML.
13.2.3.5 The Theory
Consistency-robustness tradeoff: You can’t be arbitrarily good when predictions are accurate AND arbitrarily close to optimal when they’re wrong.
Formal results: For many problems, we now know: - The best possible consistency (how good with perfect predictions) - The best possible robustness (how bad with worst predictions) - The tradeoff curve between them
Open problems: Most learning-augmented algorithms are still being discovered. Active research areas: - Learned scheduling - Learned routing - Learned compression - Learned streaming algorithms
13.2.4 Differential Privacy: Computing on Sensitive Data
Statistical disclosure risk motivates a precise question: Can an analysis reveal population-level information while limiting what it reveals about any one participant?
13.2.4.1 The Problem
Removing direct identifiers is not, by itself, a privacy guarantee. Auxiliary information and distinctive behavioral patterns can permit records in a nominally anonymized release to be linked back to individuals.
The insight: Simply removing names doesn’t protect privacy. Statistical patterns can reveal individuals.
13.2.4.2 Differential Privacy
Definition: An algorithm is ε-differentially private if changing one person’s data changes the output distribution by at most e^ε (Dwork et al. 2006).
Intuitive meaning: Observing the output teaches you almost nothing about any individual.
How it works: Add carefully calibrated random noise to results.
Example: Census data
True count of city population: 1,234,567
Add Laplace noise: ±300 (depending on privacy parameter ε)
Released count: 1,234,823
Privacy guarantee: Even if you know everyone else's data,
you can't tell if any specific person is in the dataset.13.2.4.3 Deployment Considerations
Differential privacy has moved from theory into official statistics and telemetry systems. A deployment must document its adjacency relation, privacy accounting, clipping or sensitivity bounds, and the interpretation of its published privacy parameters. Merely adding unspecified noise does not establish the guarantee.
13.2.4.4 The Algorithms
Laplace mechanism: For a numeric query \(f\), release
\[ \mathcal M(D)=f(D)+Z, \qquad Z\sim\operatorname{Laplace}\!\left(0,\frac{\Delta f}{\epsilon}\right), \]
where \(\Delta f\) is the query sensitivity under the stated adjacency relation and \(\epsilon>0\) is the privacy parameter.
Exponential mechanism: For choosing from a set of options \[ \Pr[\mathcal M(D)=o]\propto \exp\!\left(\frac{\epsilon\,q(D,o)}{2\Delta q}\right), \]
where \(q(D,o)\) is the option’s quality score and \(\Delta q\) is its sensitivity.
Sparse vector technique: For answering many queries efficiently.
13.2.4.5 The Cost of Privacy
Accuracy vs. Privacy tradeoff: More privacy (smaller ε) means more noise, less accurate results.
The meaning of a numerical ε value depends on the threat model, unit of privacy, composition across releases, and the consequences of disclosure. It should therefore be justified for the application rather than classified by a universal table of “strong” or “weak” values.
Composition: Privacy budget depletes with each query. Answer n queries → effective privacy ≈ √n × ε (with advanced composition).
Research questions: - How to allocate privacy budget optimally? - Can we get better accuracy for the same privacy? - Local vs. central differential privacy tradeoffs
13.2.5 Algorithmic Fairness: Eliminating Bias
Algorithms are making life-changing decisions: loan approvals, hiring, criminal sentencing, medical diagnoses. But what if the algorithms are biased?
13.2.5.1 How Bias Creeps In
Historical bias: Training data can encode earlier institutional decisions, causing a model to reproduce patterns that should not be treated as desirable targets.
Representation bias: Training data doesn’t represent everyone - Example: Facial recognition works worse for darker skin tones (Buolamwini & Gebru, 2018) - Why: Training datasets over-represented lighter skin tones
Measurement bias: Labels reflect biased decisions - Example: COMPAS recidivism prediction (Northpointe) - Why: Historical arrest data reflects policing patterns, not just crime patterns
13.2.5.2 Defining Fairness
Turns out, “fairness” isn’t one thing. Multiple mathematical definitions exist, and they’re mutually exclusive!
Individual fairness: Similar people treated similarly - Formally: d(x₁, x₂) small → |f(x₁) - f(x₂)| small - Problem: Defining “similar” is subjective
Group fairness (Demographic parity): Equal outcomes across groups - Formally: P(Ŷ=1|A=a) = P(Ŷ=1|A=b) for protected attribute A - Example: Loan approval rate same for all races - Problem: May be unfair if groups have different qualification distributions
Equal opportunity: Equal true positive rates across groups - Formally: P(Ŷ=1|Y=1,A=a) = P(Ŷ=1|Y=1,A=b) - Example: Among qualified applicants, approval rate same for all races - Used when false negatives are more concerning than false positives
Calibration: Predictions equally accurate across groups - Formally: P(Y=1|Ŷ=p,A=a) = P(Y=1|Ŷ=p,A=b) = p - Example: If algorithm says 70% risk, actual risk should be 70% for all groups
Impossibility result (Kleinberg et al., 2016): You can’t satisfy calibration, equal opportunity, AND balance (equal positive predictive value) simultaneously unless base rates are equal or the classifier is perfect.
This means: We must make value judgments about which fairness criterion matters most for each application.
13.2.5.3 Fairness Algorithms
Preprocessing: Clean training data - Reweighing (Kamiran & Calders, 2012): Weight training examples to balance groups - Learning fair representations (Zemel et al., 2013): Transform features to remove bias
In-processing: Constrained optimization - Zafar et al. (2017): Add fairness constraints to loss function - Agarwal et al. (2018): Reduction approach—convert any ML algorithm to fair version
Post-processing: Adjust predictions - Hardt et al. (2016): Calibrate thresholds per group to achieve equal opportunity - Pleiss et al. (2017): Isotonic regression for calibration across groups
13.2.5.4 Applied Evaluation
In consequential domains such as hiring, lending, health care, and criminal justice, aggregate accuracy is insufficient. An evaluation should report error rates by relevant groups, examine calibration and threshold choices, document the provenance of labels, and identify who bears the cost of each error type. Because fairness definitions can conflict, the selected criterion is a normative design decision that must be stated and defended.
13.2.5.5 Research Questions
Multi-objective optimization: Can we be fair to multiple groups simultaneously?
Long-term fairness: Short-term equal outcomes might not lead to long-term fairness. Example: If algorithm rejects qualified minority applicants, they don’t build credit history, perpetuating inequality.
Feedback loops: Biased predictions → biased actions → biased future data → more biased predictions. How to break the cycle?
Fairness without demographics: Can we ensure fairness without knowing sensitive attributes? (Important for privacy, but algorithmically challenging)
13.3 Algorithms in AI and Machine Learning
Machine learning has transformed from academic curiosity to world-changing technology. Let’s understand the algorithms that make it work.
13.3.1 Deep Learning: The Revolution
In 2012, a neural network called AlexNet won the ImageNet competition by a shocking margin. It started the deep learning revolution that gave us: - Image recognition better than humans - Real-time language translation - Self-driving cars - ChatGPT and Large Language Models
But how do neural networks actually learn?
13.3.1.1 Backpropagation: The Learning Algorithm
The setup: A neural network is a function \(f(x;\theta)\) where \(\theta\) contains its parameters. We want to minimize the loss \(L(f(x;\theta),y)\).
The challenge: Networks have millions of parameters. How do we compute \(\partial L/\partial\theta_i\) for each one?
Naive approach: Finite differences \[ \frac{\partial L}{\partial\theta_i} \approx \frac{L(\theta+\epsilon e_i)-L(\theta)}{\epsilon}. \] For n parameters, this requires n forward passes. For a million parameters, that’s impossibly slow!
Backpropagation (Rumelhart et al., 1986): Use the chain rule to compute all gradients in one backward pass.
How it works:
Forward pass: Compute network output \[ \begin{aligned} h_1&=\sigma(W_1x+b_1),\\ h_2&=\sigma(W_2h_1+b_2),\\ &\ \vdots\\ \widehat y&=\sigma(W_nh_{n-1}+b_n),\\ L&=(\widehat y-y)^2. \end{aligned} \]
Backward pass: Compute gradients layer by layer \[ \begin{aligned} \frac{\partial L}{\partial\widehat y}&=2(\widehat y-y),\\ \frac{\partial L}{\partial W_n} &=\frac{\partial L}{\partial\widehat y} \frac{\partial\widehat y}{\partial W_n},\\ \frac{\partial L}{\partial h_{n-1}} &=\frac{\partial L}{\partial\widehat y} \frac{\partial\widehat y}{\partial h_{n-1}}. \end{aligned} \]
The magic: Each gradient computation reuses calculations from the layer above. Total cost: one forward pass + one backward pass, regardless of number of parameters!
Time complexity: \(O(E)\) where E = number of edges in network (typically E ≈ n for n parameters).
Why this matters: Without backpropagation, training deep networks would be impossible. It’s the algorithm that makes deep learning feasible.
13.3.1.2 Stochastic Gradient Descent: The Optimization Workhorse
Once we have gradients, how do we optimize?
Gradient descent uses \(\theta\leftarrow\theta-\eta\nabla L(\theta)\), where \(\eta>0\) is the learning rate.
Problem: Computing L(θ) requires entire dataset. For millions of examples, one update takes forever!
Stochastic Gradient Descent (SGD): Use one random example at a time For a sampled example \((x,y)\), SGD computes \(\nabla_\theta L(f(x;\theta),y)\) and applies
\[ \theta\leftarrow\theta-\eta\nabla_\theta L. \]
Mini-batch SGD: Use small batches (typically 32-256 examples) - Balances speed vs. gradient accuracy - Enables parallel computation on GPUs - Reduces gradient noise
Why SGD works: Individual gradients are noisy, but on average point toward optimum. The noise even helps escape bad local minima!
13.3.1.3 Modern Optimizers
Momentum (1964): Accelerate in consistent directions \[ v\leftarrow\beta v+\nabla L, \qquad \theta\leftarrow\theta-\eta v. \] Effect: Smoother optimization, faster convergence, dampens oscillations.
Adam (Kingma & Ba, 2014): Adaptive learning rates per parameter \[ \begin{aligned} m_t&\leftarrow\beta_1m_{t-1}+(1-\beta_1)g_t,\\ v_t&\leftarrow\beta_2v_{t-1}+(1-\beta_2)g_t^2,\\ \widehat m_t&=\frac{m_t}{1-\beta_1^t}, &\widehat v_t&=\frac{v_t}{1-\beta_2^t},\\ \theta_t&\leftarrow\theta_{t-1}-\eta \frac{\widehat m_t}{\sqrt{\widehat v_t}+\epsilon}. \end{aligned} \]
Here \(g_t=\nabla_\theta L_t\); squares, roots, and division are applied componentwise. Effect: Parameters with large gradients get smaller updates (more conservative). Parameters with small gradients get larger updates (more aggressive).
Why Adam is popular: Works well with minimal hyperparameter tuning. Default choice for many applications.
Current research: Better optimizers (AdamW, LAMB), understanding why SGD generalizes better than sophisticated methods, adversarial examples.
13.3.2 Transformers: The Architecture Revolution
The Transformer introduced a sequence architecture based primarily on attention rather than recurrence (Vaswani et al. 2017). Variants now support language modeling, translation, vision, and scientific prediction, but their task-specific behavior depends on training data, objective, scale, and inference design.
13.3.2.1 The Self-Attention Mechanism
The problem: Understanding context in sequences. In “The animal didn’t cross the street because it was too tired”, what does “it” refer to?
RNNs/LSTMs: Process sequentially, struggle with long-range dependencies.
Transformers: Process entire sequence simultaneously using attention.
How attention works:
For each position i, compute how much to “attend” to each other position j:
- Query, Key, Value: For each word, compute three vectors \[ Q_i=W_Qx_i,\qquad K_i=W_Kx_i,\qquad V_i=W_Vx_i. \]
\(Q_i\) represents what position \(i\) seeks, \(K_i\) what it contains, and \(V_i\) what it contributes.
Attention scores: How relevant is position j to position i? \[ s_{ij}=\frac{Q_i\cdot K_j}{\sqrt d}. \]
Softmax: Convert scores to probabilities \[ \alpha_{ij}=\frac{\exp(s_{ij})}{\sum_k\exp(s_{ik})}. \]
Weighted sum: Output is weighted combination of values \[ \operatorname{output}_i=\sum_j\alpha_{ij}V_j. \tag{13.1}\]
The weights \(\alpha_{ij}\) are nonnegative and sum to one over \(j\). The \(1/\sqrt d\) scale controls dot-product magnitude; the mechanism still has quadratic pairwise cost in the sequence length.
Intuition: “The animal” has high attention to “it” and “tired”, learning that “it” refers to the animal, not the street.
Time complexity: \(O(n^2d)\) where n = sequence length, d = dimension - Quadratic in sequence length (problem for long sequences!) - But parallelizes perfectly (unlike RNNs)
13.3.2.2 Multi-Head Attention
Run attention multiple times in parallel with different learned projections:
\[ \operatorname{head}_i=\operatorname{Attention}(Q_i,K_i,V_i), \qquad \operatorname{output}=\operatorname{Concat}(\operatorname{head}_1,\ldots,\operatorname{head}_h)W_O. \]
Why: Different heads learn different relationships. One might focus on syntax, another on semantics, another on coreference.
The number and width of heads are architectural hyperparameters; more heads do not automatically imply a better model.
13.3.2.3 Positional Encoding
Problem: Attention is permutation-invariant. “Dog bites man” and “Man bites dog” look the same!
Solution: Add position information to input embeddings
PE(pos, 2i) = sin(pos/10000^(2i/d))
PE(pos, 2i+1) = cos(pos/10000^(2i/d))Why sinusoidal: Allows model to learn relative positions. Also extrapolates to longer sequences than training.
13.3.2.4 The Full Transformer Architecture
Encoder (for understanding):
Input → Embedding + Positional Encoding
→ Multi-Head Attention
→ Add & Normalize
→ Feed-Forward Network
→ Add & Normalize
→ (repeat for multiple layers)Decoder (for generation):
(similar to encoder, but with masked attention
to prevent looking at future tokens)Training objective: Predict next token
Given "The cat sat on the"
Predict "mat"Scaling laws (Kaplan et al., 2020): Performance improves smoothly with: - Model size (number of parameters) - Data size (number of training tokens) - Compute (GPU hours)
Power law: Loss ∝ N^(-α) where N is model size.
Scaling results are empirical relationships within a stated experimental regime, not a guarantee that increasing a single resource will improve every downstream property. Parameter counts also reveal little about data quality, inference cost, or reliability on a particular task.
13.3.2.5 Efficient Transformers
The n² problem: Standard attention is quadratic in sequence length.
Solutions:
Sparse attention (Child et al., 2019): Only attend to subset of positions - Local attention: nearby tokens - Global attention: special tokens - Reduces to \(O(n\sqrt n)\) or \(O(n log n)\)
Linformer (Wang et al., 2020): Project keys/values to lower dimension - Reduces to \(O(nd)\) where d << n
Flash Attention (Dao et al., 2022): Optimize memory access patterns - Same complexity, but 2-4x faster wall-clock time - Key innovation: algorithmic improvements for GPUs
Efficient-attention methods trade exactness, memory traffic, sparsity structure, and implementation complexity in different ways. Context length is therefore a model-and-system parameter, not a stable field-wide threshold.
13.3.3 Reinforcement Learning: Learning by Doing
Reinforcement learning (RL) has produced strong results in games, control, and preference-guided model adaptation. AlphaGo is a prominent example of combining search, learned value estimates, and policy networks (Silver et al. 2016).
How does RL work?
13.3.3.1 The RL Framework
Setup: - Agent in environment - At each timestep: observe state s, take action a, receive reward r - Goal: maximize cumulative reward
The challenge: Actions have delayed consequences. Sacrificing a piece in chess might lead to winning 20 moves later.
Value function: \(V(s)\) is the expected cumulative reward starting from state \(s\).
Q-function: \(Q(s,a)\) is the expected cumulative reward after taking action \(a\) in state \(s\).
The Bellman equation: \[ Q(s,a)=r+\gamma\max_{a'}Q(s',a'). \tag{13.2}\]
Here \(s'\) is the next state and \(0\le\gamma<1\) is the discount factor. The equation assumes the Markov state captures the information needed to model the next-state distribution.
Intuitive meaning: Value of state = immediate reward + discounted future value.
13.3.3.2 Q-Learning: The Classic Algorithm
Q-learning (Watkins, 1989): Learn Q-function through experience
Algorithm:
Initialize Q(s,a) arbitrarily
Loop:
Observe state s
Choose action a (ε-greedy: random with probability ε)
Take action, observe reward r and next state s'
Update: Q(s,a) ← Q(s,a) + α[r + γ max_a' Q(s',a') - Q(s,a)]The update rule: Move Q-value toward observed reward + future value.
Exploration vs. exploitation: ε-greedy balances trying new actions (exploration) with using known good actions (exploitation).
Convergence: Provably converges to optimal Q-function if all state-action pairs are visited infinitely often.
13.3.3.3 Deep Q-Networks (DQN)
The scaling problem: Q-learning stores Q(s,a) in table. For Atari games: 10^9 states × 18 actions = 18 billion entries!
Solution (Mnih et al., 2015): Approximate Q with neural network \[ Q(s,a;\theta)\approx Q^*(s,a). \]
Training: Use TD (temporal difference) error as loss \[ L(\theta)=\left[r+\gamma\max_{a'}Q(s',a';\theta^-)-Q(s,a;\theta)\right]^2, \]
where \(\theta^-\) denotes periodically updated target-network parameters.
Key innovations:
Experience replay: Store past experiences (s,a,r,s’) in buffer, sample randomly for training - Breaks correlation between consecutive samples - Improves data efficiency
Target network: Use old parameters θ⁻ for computing targets - Stabilizes learning (target isn’t constantly moving) - Update periodically (every 10k steps)
Results: DQN learned to play 49 Atari games from pixels, achieving human-level performance on many.
13.3.3.4 Policy Gradient Methods
Alternative approach: Learn policy π(a|s) directly (probability of action a in state s).
REINFORCE (Williams, 1992): Increase probability of actions that led to high reward \[ \nabla J(\theta) =\mathbb E\!\left[R\,\nabla_\theta\log\pi(a\mid s;\theta)\right], \]
where \(R\) is cumulative return. The estimator can have high variance, motivating baselines and actor–critic methods.
Intuition: If an action led to good outcome, make it more likely. If bad outcome, make it less likely.
Actor-Critic: Combine value function (critic) with policy (actor) The actor is \(\pi(a\mid s;\theta)\) and the critic is \(V(s;w)\); the critic’s value estimate serves as a baseline for the actor update.
Advantage: Reduces variance, learns faster.
13.3.3.5 Proximal Policy Optimization (PPO)
PPO (Schulman et al., 2017): Current state-of-the-art policy gradient method.
The problem: Policy gradients are unstable. One bad update can destroy learned policy.
PPO’s solution: Constrain policy updates \[ \max_\theta\;\mathbb E\!\left[ \min\!\left(r_t(\theta)A_t, \operatorname{clip}(r_t(\theta),1-\epsilon,1+\epsilon)A_t\right) \right], \tag{13.3}\]
where \(r_t(\theta)=\pi_\theta(a_t\mid s_t)/\pi_{\mathrm{old}}(a_t\mid s_t)\), \(A_t\) is an advantage estimate, and \(\epsilon\) is the clipping parameter. Clipping limits a single policy update; it does not by itself guarantee global convergence.
Effect: Limits how much policy can change per update. More stable, more reliable.
Applications: - OpenAI Five (Dota 2) - AlphaStar (StarCraft II) - ChatGPT (RLHF: Reinforcement Learning from Human Feedback)
13.3.3.6 AlphaGo: Putting It All Together
AlphaGo combined multiple techniques:
- Supervised learning: Train on expert human games
Policy network: predict human moves
Value network: evaluate board positions- Self-play RL: Play against itself millions of times
Policy improvement via policy gradient
Value updates via TD learning- Monte Carlo Tree Search: Smart exploration during game play
Selection: Choose promising moves (UCB formula)
Expansion: Add new nodes
Simulation: Use neural nets to evaluate
Backpropagation: Update statisticsThe innovation: Deep learning (pattern recognition) + tree search (planning)
Results: - AlphaGo beat Lee Sedol 4-1 (2016) - AlphaGo Zero learned from scratch, beat AlphaGo 100-0 (2017) - AlphaZero generalized to chess and shogi (2017)
Impact: Showed that RL + deep learning could master complex strategic games, opening path to real-world applications.
13.4 Big Data Algorithms: Computing at Planetary Scale
When a data set exceeds the memory, storage bandwidth, or fault-tolerance capacity of one machine, algorithm design must account for partitioning and communication. Large-scale data algorithms explicitly model those costs.
13.4.1 The MapReduce Revolution
13.4.1.1 The Problem
Traditional algorithm analysis assumes: data fits in RAM, you can access any element instantly.
The engineering setting described by the original MapReduce work included: - Web: billions of pages - Indexing: terabytes of data - Distributed across thousands of machines - Machines fail constantly
Traditional approach doesn’t work: Can’t load everything into one machine’s memory. Can’t write algorithms assuming reliable hardware.
13.4.1.2 The MapReduce Paradigm
Key insight: Most data processing has two phases: 1. Map: Apply function to each element independently 2. Reduce: Aggregate results
Example - Word Count:
Input: Millions of documents
Map phase:
Document 1 → ("hello", 1), ("world", 1), ("hello", 1)
Document 2 → ("world", 1), ("foo", 1)
...
Shuffle phase (automatic):
("hello", [1, 1, ...])
("world", [1, 1, ...])
("foo", [1, ...])
Reduce phase:
("hello", [1, 1, ...]) → ("hello", 4521)
("world", [1, 1, ...]) → ("world", 3892)
("foo", [1, ...]) → ("foo", 1023)What makes MapReduce powerful:
Automatic parallelization: Framework handles distributing work - No explicit thread management - No message passing - Just write map() and reduce() functions
Fault tolerance: If machine fails, rerun just that task - Map tasks are idempotent (can rerun safely) - Output written to distributed file system - Automatic retry on failure
Data locality: Move computation to data - Minimize network transfer - Process data where it’s stored
Scalability: Independent tasks can be distributed, but speedup is limited by skew, shuffle volume, synchronization, stragglers, and serial work. MapReduce made these tradeoffs accessible through a simple programming abstraction (Dean and Ghemawat 2004).
13.4.1.3 MapReduce Algorithms
Many algorithms can be expressed in MapReduce:
PageRank:
Map: For each page, emit (link_target, pagerank/num_links)
Reduce: Sum contributions to get new pagerank
Iterate until convergenceInverted index (Google Search):
Map: For each document, emit (word, doc_id)
Reduce: Collect all doc_ids for each wordJoin (database operation):
Map: Emit (join_key, (table_name, record))
Reduce: Combine records with same key from different tablesMatrix multiplication:
A × B where A is n×m, B is m×p
Map: For each A[i,k], emit ((i,j), A[i,k] × B[k,j]) for all j
Reduce: Sum all contributions for each (i,j)13.4.1.4 Limitations and Evolution
MapReduce limitations: - High latency (disk I/O between stages) - Not great for iterative algorithms - Programmer has to think in map/reduce paradigm
Apache Spark (2012): In-memory successor - Keep data in RAM between operations - 10-100x faster for iterative algorithms - More expressive programming model
Apache Flink (2014): True streaming - Process data as it arrives (real-time) - Event time processing - Exactly-once guarantees even with failures
13.4.2 Streaming Algorithms: Computing in One Pass
The constraint: Data arrives as stream, you can only look at it once, using limited memory.
Applications: - Network monitoring (terabytes/day of traffic) - Social media analytics (millions of posts/second) - Financial trading (microsecond decisions) - Sensor networks (billions of IoT devices)
13.4.2.1 Count-Min Sketch
Problem: Count frequency of millions of distinct items, but you only have memory for thousands of counters.
Naive approach: Hash table → \(O(n)\) space where n = number of distinct items. If n = billions, you’re out of memory.
Count-Min Sketch (Cormode and Muthukrishnan 2005):
Data structure: w × d array of counters (typically w=2000, d=5)
Hash functions: h₁, h₂, ..., hₐ
Update(item):
for i = 1 to d:
count[i][hᵢ(item)]++
Query(item):
return min(count[i][hᵢ(item)] for i = 1 to d)Why it works: - True count ≤ returned count (never underestimate) - With high probability: returned count ≤ true count + ε × total_items - Space: \(O((1/ε) × log(1/δ))\) where δ = failure probability
Applications: - Network traffic analysis - Top-k frequent items - Heavy hitters detection
Its one-sided error is useful when overestimation is acceptable and the width and depth are selected from explicit error and failure-probability targets.
13.4.2.2 HyperLogLog
Problem: Count number of distinct items in stream.
Naive approach: Hash set → \(O(n)\) space.
HyperLogLog (Flajolet et al. 2007):
Per-register space: O(log log n) bits for cardinality n
Total register space: O(m log log n) bits for m registers
Algorithm:
1. Hash each item to binary string
2. Count leading zeros: ρ(hash(item))
3. Keep maximum: M = max(ρ(hash(item)) for all items)
4. Estimate: distinct_count ≈ 2^M
Refinement: Use m buckets, combine estimatesWhy it works: If you’ve seen n distinct items, you expect one hash to have log₂(n) leading zeros.
Accuracy: Error ≈ 1.04/√m where m = number of buckets.
Example: 1% error with just 16 KB of memory, for billions of distinct items!
Implementations often expose HyperLogLog-style cardinality estimation as a compact alternative to retaining every distinct key. Production variants may differ in hashing, bias correction, sparse representation, and register width.
13.4.2.3 Bloom Filters
Problem: Test set membership (“have I seen this before?”) with limited memory.
Bloom filter (Bloom 1970):
Data structure: bit array of size m
Hash functions: k different hash functions
Add(item):
for each hash function h:
set bit[h(item)] = 1
Query(item):
for each hash function h:
if bit[h(item)] = 0:
return "definitely not present"
return "probably present"Properties: - No false negatives (if it says “not present”, it’s really not present) - Possible false positives (if it says “present”, might be wrong) - False positive probability ≈ (1 - e(-kn/m))k
Optimal parameters: k = (m/n) × ln(2) hash functions minimizes false positives.
Applications: - Web browsers: Check if URL is malicious before visiting - Databases: Avoid expensive disk lookups - Distributed systems: Check if data is cached
The false-positive rate must be included in system-level cost analysis: a positive result ordinarily triggers a more authoritative lookup rather than a final decision.
13.4.3 Graph Processing at Scale
The challenge: Social networks have billions of users, trillions of connections. How do you compute PageRank, find communities, detect fraud?
13.4.3.1 Pregel: Thinking Like a Vertex
Pregel introduced a vertex-centric bulk-synchronous abstraction for large graph computations (Malewicz et al. 2010).
Programming model:
class Vertex:
def compute(self, messages):
# Process messages from neighbors
# Update vertex state
# Send messages to neighbors
# Vote to halt or continue
Computation proceeds in supersteps:
1. All vertices process messages in parallel
2. Send messages for next superstep
3. Repeat until all vertices haltExample - PageRank:
def compute(self, messages):
if superstep > 0:
self.pagerank = 0.15 + 0.85 × sum(messages)
if superstep < 30: # 30 iterations
for neighbor in self.neighbors:
send_message(neighbor, self.pagerank / len(self.neighbors))
else:
vote_to_halt()Why this works at scale: - Vertices process independently (massive parallelism) - Only send messages to neighbors (limited communication) - Automatic fault tolerance (rerun failed partitions) - Graph partitioning optimizes locality
Related systems differ in partitioning strategy, recovery model, messaging semantics, and integration with general-purpose dataflow engines.
13.4.3.2 GraphX and GraphFrames
Built on Spark, these provide graph algorithms with: - Connected components - PageRank - Triangle counting - Shortest paths - Community detection
Integration with machine learning: Can combine graph structure with node features for: - Node classification - Link prediction - Graph neural networks
13.5 Security and Cryptographic Algorithms
Cryptographic systems combine mathematical assumptions, protocols, implementations, and operational key management. This section focuses on the algorithmic ideas and the assumptions on which their guarantees depend.
13.5.1 Public-Key Cryptography: The Mathematics of Secrets
13.5.1.1 The Problem That Seemed Impossible
Before 1976, secret communication required shared secret keys. If Alice and Bob wanted secure communication: 1. Meet in person to exchange key 2. Or trust a courier 3. Or use complex key distribution centers
For the internet: How do billions of people establish shared secrets?
Diffie and Hellman established the public-key model and key-agreement direction (Diffie and Hellman 1976); RSA supplied an influential public-key encryption and signature construction (Rivest et al. 1978).
The idea: Two keys - Public key: Freely shared, used to encrypt - Private key: Kept secret, used to decrypt
Amazing property: Knowing the public key doesn’t help you figure out the private key (assuming certain mathematical problems are hard).
13.5.1.2 RSA and Its Security Assumption
RSA is based on modular exponentiation and a trapdoor construction related to the difficulty of factoring a product of large primes (Rivest et al. 1978).
Key generation chooses large primes \(p\) and \(q\), forms \(N=pq\) and \(\varphi(N)=(p-1)(q-1)\), selects a public exponent \(e\), and computes \(d\) such that
\[ ed\equiv1\pmod{\varphi(N)}. \]
The public key is \((N,e)\) and the private key is \((N,d)\).
Encryption: \(c\equiv m^e\pmod N\).
Decryption: \(m\equiv c^d\pmod N\).
Why it works (mathematically): \[ (m^e)^d\equiv m^{ed}\equiv m\pmod N, \]
under the number-theoretic conditions used by RSA. The congruence \(ed\equiv1\pmod{\varphi(N)}\) explains the basic exponent relation; complete correctness also handles messages not coprime to \(N\).
Security basis: Recovering the factors of a properly generated modulus is believed to be computationally infeasible for suitable parameters with known classical methods. Secure practice also requires standardized padding, protected key generation, and resistance to implementation attacks; textbook RSA alone is not a deployable encryption scheme.
13.5.1.3 The Quantum Threat to RSA
Shor’s algorithm shows that integer factorization has a polynomial-time quantum algorithm (Shor 1997). Whether and when hardware can run it against cryptographic parameters is an engineering question involving logical error rates, correction overhead, circuit depth, and architecture; a calendar prediction is not an algorithmic guarantee.
NIST finalized its first three post-quantum cryptography standards in 2024 and continues related evaluation and migration work (National Institute of Standards and Technology 2024).
Selected algorithms: - ML-KEM, derived from CRYSTALS-Kyber, for key establishment - ML-DSA, derived from CRYSTALS-Dilithium, for digital signatures - SLH-DSA, derived from SPHINCS+, for hash-based digital signatures
Why lattices: Best known quantum algorithms only achieve modest speedup against lattice problems. Believed to be quantum-resistant.
13.5.2 Blockchain and Cryptocurrencies
Cryptocurrency protocols provide useful case studies in consensus, incentives, cryptographic commitments, and adversarial distributed computation. Their guarantees must be separated from claims about price or social value.
13.5.2.1 The Byzantine Generals Problem
The challenge: How do distributed parties agree on something when some might be malicious?
Byzantine Generals Problem (Lamport, 1982): - n generals surrounding city, need to coordinate attack - Some generals might be traitors - Communication by messenger (can be intercepted) - Goal: All loyal generals decide on same plan
Classical result: Need n ≥ 3f + 1 generals to tolerate f traitors.
Blockchain’s innovation: Use computational work (proof-of-work) instead of assuming number of honest parties.
13.5.2.2 Bitcoin’s Proof-of-Work
The algorithm:
Block contains:
- Previous block hash
- Transactions
- Nonce (random number)
Mining:
repeat:
nonce = random()
hash = SHA256(SHA256(block_data || nonce))
if hash < target:
broadcast block
breakThe target: Periodically adjusted so the expected block interval remains near the protocol target. The required work changes with the target and should not be represented by a fixed number of leading zero bits.
Why this secures Bitcoin:
Immutability: To change past transaction, you’d need to: 1. Recompute proof of work for that block under the applicable target 2. Remine all subsequent blocks 3. Outpace the rest of the network
Consensus: Nodes follow the valid chain with the greatest accumulated proof of work. Majority hash power is a useful simplified attack threshold, but network behavior, confirmation depth, incentives, and attack duration also matter.
Incentives: Miners receive protocol-defined issuance and transaction fees. Security arguments analyze when honest participation is more profitable than deviations; they do not follow from a fixed coin price or reward value.
13.5.2.3 The Energy Cost
Proof of work intentionally makes leader election computationally expensive. Its resource cost varies with hardware efficiency, energy sources, market incentives, and protocol parameters, so empirical comparisons must state their measurement date and methodology. Most attempted hashes do not become blocks, although their aggregate cost is the mechanism used to deter rewriting history.
13.5.2.4 Alternative Consensus: Proof-of-Stake
Proof of stake selects and penalizes validators using locked economic stake rather than repeated hashing.
Algorithm:
1. Validators lock protocol-defined stake
2. Randomly selected to propose blocks (probability ∝ stake)
3. Other validators vote on validity
4. Rewards for honest behavior, penalties for malicious behaviorPotential advantages: - substantially lower computational energy demand than proof of work - explicit finality mechanisms in some designs - attacks can expose bonded assets to protocol penalties
Challenge: “Nothing at stake” problem—validators could vote for multiple chains. Solved through slashing (destroying stake of malicious validators).
Energy and finality comparisons depend on protocol design and system boundary. They should be reported from a dated, reproducible measurement rather than treated as permanent constants.
13.5.3 Zero-Knowledge Proofs: Proving Without Revealing
The amazing idea: Prove you know something without revealing what you know.
Example: Prove you know solution to Sudoku puzzle without showing the solution.
Applications: - Anonymous credentials (prove you’re over 18 without showing ID) - Private blockchain transactions (Zcash) - Scaling blockchains (zkRollups) - Password-less authentication
13.5.3.1 Interactive Zero-Knowledge
Original protocol (Goldwasser, Micali, Rackoff, 1985):
Prover-Verifier interaction (for graph 3-coloring):
Prover knows valid coloring of graph
Verifier wants to verify, but not learn coloring
Repeat many times:
1. Prover randomly permutes colors, commits to new coloring
2. Verifier randomly picks an edge
3. Prover reveals colors of both endpoints
4. Verifier checks: different colors? If yes, continue
After n rounds:
If prover is honest: always passes
If prover is cheating: probability of passing = (1 - 1/|E|)^n ≈ 0Properties: - Completeness: Honest prover convinces verifier - Soundness: Cheating prover caught with high probability - Zero-knowledge: Verifier learns nothing except validity
13.5.3.2 Non-Interactive Zero-Knowledge (SNARKs)
Problem with interactive: Requires back-and-forth. Not suitable for blockchain.
SNARKs (Succinct Non-interactive ARguments of Knowledge): - Prover generates single proof - Anyone can verify - Proof is short (hundreds of bytes) - Verification is fast (milliseconds)
How it works (simplified):
1. Convert statement to arithmetic circuit
2. Use cryptographic pairing to create proof
3. Proof: π = combination of circuit values and randomness
4. Verification: Check pairing equation e(π, g) = e(h, vk)Applications:
Zcash: Private transactions - Prove “I have money to send” without revealing how much or to whom - Transaction size: ~300 bytes - Verification: ~5ms
zkRollups: Scaling Ethereum - Bundle thousands of transactions - Generate proof that all transitions are valid - Post proof to blockchain (not all transaction data) - Result: 100x increase in throughput
Challenges: - Trusted setup (some schemes require initial ceremony) - Computational cost of proof generation (seconds to minutes) - Complexity of writing circuits
Current research: STARK proofs (no trusted setup), recursive composition (proofs of proofs), practical tooling.
13.6 Ethical Implications: When Algorithms Make Decisions
Algorithms aren’t neutral. They encode choices, reflect biases, and have real impacts on people’s lives. Let’s confront the ethical challenges head-on.
13.6.1 The Accountability Problem
Question: When an algorithm makes a mistake, who’s responsible?
13.6.1.1 Case Study: Tesla Autopilot
March 2018: Tesla Model X on Autopilot crashes into highway barrier, killing driver.
The algorithm: Neural network trained on millions of miles of driving data. Makes predictions 10 times per second.
The failure: Misclassified concrete barrier as continuation of road.
Questions: - Was the algorithm defective? - Was the driver misusing it? - Did Tesla adequately communicate limitations? - Should the algorithm have recognized its own uncertainty?
Current state: No clear legal framework. Liability unclear. Regulations being developed.
13.6.1.2 Case Study: Algorithmic Hiring
Amazon’s hiring algorithm (disclosed 2018): - Trained on 10 years of résumés from successful hires - Automatically ranked candidates - Discovered to penalize résumés mentioning “women’s” (as in women’s chess club)
The problem: Historical hires were biased → algorithm learned bias.
Amazon’s response: Discontinued the tool.
Questions: - Is it illegal? (Disparate impact under Civil Rights Act) - Even if algorithm is more accurate than humans, is it fair? - Should protected attributes be included (to ensure fairness) or excluded (to prevent discrimination)?
No easy answers: Companies now use fairness-aware ML, but what “fair” means is contested.
13.6.2 Transparency vs. Performance
The dilemma: Most accurate models (deep learning) are least interpretable.
Example: COMPAS recidivism prediction - Predicts whether criminal defendant will reoffend - Used in sentencing decisions across U.S. - Proprietary algorithm, opaque to defendants and judges
Arguments for opacity: - More accurate predictions - Gaming prevention (can’t manipulate score if don’t know how it works) - Trade secrets
Arguments for transparency: - Right to explanation (GDPR) - Ability to challenge decisions - Public oversight and accountability - Trust
Current approaches:
LIME (Local Interpretable Model-Agnostic Explanations): - Approximate black-box model locally with simple model - “For this specific case, decision was based on…”
SHAP (Shapley Additive Explanations): - Use game theory to assign importance to features - “Feature X contributed +0.3 to prediction”
Attention visualization: For neural networks, show what parts of input the model focused on.
Limitations: Explanations are post-hoc. Don’t guarantee the model makes sense globally.
13.6.3 Privacy vs. Utility
The fundamental tradeoff: More data and less privacy → better algorithms. But at what cost?
13.6.3.1 Surveillance Capitalism
Business model: 1. Collect data on user behavior 2. Train algorithms to predict behavior 3. Sell predictions to advertisers 4. Use algorithms to manipulate behavior (maximize engagement)
Concerns: - Filter bubbles: Algorithms show you content you’ll engage with, creating echo chambers - Addiction: Algorithms optimized for engagement, not well-being - Manipulation: Political microtargeting, radicalization - Surveillance: Everything tracked, profiled, monetized
13.6.3.2 Case Study Pattern: Profiling and Microtargeting
A recurring risk pattern is the reuse of data collected for one purpose to infer personal traits and target persuasive messages for another. A rigorous assessment asks whether consent covered the secondary use, whether inferred attributes are valid, how targeting outcomes are measured, and whether affected people can inspect or contest the process. Applicable legal requirements vary by jurisdiction and change over time, so a project making legal claims should cite the current authoritative text.
13.6.4 Autonomous Weapons
The prospect: Weapons that select and engage targets without human intervention.
Current state: - Military drones (human in loop) - Autonomous defensive systems (ship/base protection) - Research into fully autonomous systems
The trolley problem, militarized:
Scenario: Autonomous drone identifies target in civilian area. Estimates: - 90% chance of eliminating high-value target - 10% chance of civilian casualties
Should it engage?
Arguments against: - Lack of human judgment - Risk of accidents (misidentification) - Lowering threshold for using force - Arms race concerns - Violation of human dignity (killed by algorithm)
Arguments for: - Potentially more discriminate than human soldiers - Faster reaction time (defensive systems) - Protects own soldiers - Enemies will develop anyway
Current policy: - UN discussing regulation - Many AI researchers oppose autonomous weapons - Some nations committed to keeping “human in loop” - No international treaty (yet)
13.6.5 Algorithmic Justice
The reality: Algorithms are increasingly used in criminal justice.
Applications: - Predictive policing (where to patrol) - Risk assessment (bail, sentencing, parole) - Facial recognition (identifying suspects) - Gang databases (often algorithmic)
13.6.5.1 Predictive Policing
The algorithm: Predict where crime likely to occur - Input: Historical crime data - Output: “hotspots” for patrol
Problem: Historical data reflects biased policing - More patrols in minority neighborhoods → more arrests → algorithm predicts more crime in those areas → more patrols (feedback loop)
Studies: - Lum & Isaac (2016): Showed predictive policing amplifies bias - Algorithmic bias compounds over time
Real impact: - Oakland Police discontinued use (2018) - LAPD scaled back program (2020)
13.6.5.2 Risk Assessment
COMPAS scores: Predict recidivism risk (1-10 scale)
ProPublica investigation (2016): - False positive rate (predicted to reoffend, didn’t): 45% for Black defendants, 23% for white defendants - False negative rate (predicted not to reoffend, did): 28% for Black defendants, 48% for white defendants
Northpointe response: Algorithm is calibrated - Among defendants scored 7, recidivism rate is similar across races - Both perspectives are mathematically correct (impossibility theorem!)
Policy questions: - Should risk assessment be used at all? - If used, which fairness criterion matters? - Should it be open source for auditing? - What role for human judgment?
13.6.6 The Path Forward
What can we do?
For researchers: - Publish datasets and code for reproducibility - Report failures, not just successes - Consider societal impact, not just technical novelty - Engage with ethicists, policymakers, affected communities
For practitioners: - Algorithmic impact assessments - Diverse teams (not just demographics, but perspectives) - Regular audits for bias - Clear documentation of limitations - Channels for feedback and recourse
For regulators: - Right to explanation for consequential decisions - Auditing requirements for high-risk applications - Liability frameworks for algorithmic harm - Funding for algorithmic accountability research
For individuals: - Data literacy: understand what algorithms can/can’t do - Advocate for transparency and accountability - Support ethical AI organizations - Vote for representatives who prioritize these issues
The goal: Harness the power of algorithms while protecting human rights, dignity, and autonomy.
13.7 Reading and Analyzing Research Papers
Want to contribute to algorithmic research? Start by reading papers. Here’s how.
13.7.1 Anatomy of a Research Paper
Typical structure:
- Abstract: 150-300 words summarizing contribution
- What to look for: Main result, key innovation, performance improvement
- Introduction: Motivation and context
- What to look for: What problem are they solving? Why does it matter? What’s new?
- Related Work: Comparison to prior work
- What to look for: How does this improve on previous approaches? What gap does it fill?
- Technical Content: The meat of the paper
- Algorithm description: Precise steps
- Theoretical analysis: Correctness proofs, complexity bounds
- Experimental evaluation: Benchmarks, comparisons
- Results: What they achieved
- What to look for: Quantitative improvements, limitations, when it works well/poorly
- Conclusion: Summary and future work
- What to look for: Open problems, potential applications
13.7.2 How to Read a Paper (Three-Pass Method)
First pass (5-10 minutes): - Read title, abstract, introduction, conclusion - Skim section headings - Goal: What is this paper about? Is it relevant to me?
Second pass (1 hour): - Read carefully, but skip proofs - Look at figures, tables, graphs - Note key contributions and techniques - Goal: Understand the main ideas and results
Third pass (several hours): - Read everything in detail - Work through proofs and derivations - Try to reproduce key results - Think critically: What assumptions? What limitations? What’s missing? - Goal: Deep understanding, ability to critique and extend
13.7.3 Critical Reading Questions
For algorithms: - Is the algorithm clearly described? Could you implement it? - Is the complexity analysis tight? Are there hidden constants? - What assumptions are made? Do they hold in practice? - Are there cases where the algorithm fails or performs poorly?
For experiments: - Are benchmarks realistic? Representative? - Is comparison fair? (Same hardware, fair baselines?) - Are error bars / confidence intervals provided? - Can results be reproduced? (Code/data available?)
For theory: - Are proofs rigorous? Any gaps? - Are bounds tight? Lower bounds provided? - Do theorems match experimental results? - What about constants hidden by big-O notation?
13.7.4 Where to Find Papers
Major venues:
Theory: - FOCS (Foundations of Computer Science) - STOC (Symposium on Theory of Computing) - SODA (Algorithms and Discrete Algorithms)
Machine Learning: - NeurIPS (Neural Information Processing Systems) - ICML (International Conference on Machine Learning) - ICLR (International Conference on Learning Representations)
Databases/Systems: - SIGMOD (Management of Data) - VLDB (Very Large Databases) - OSDI (Operating Systems Design and Implementation)
Archives: - arXiv.org: Preprints (not peer-reviewed, but most recent) - Google Scholar: Search engine for papers - Semantic Scholar: AI-powered paper search
Recommendation: Start with survey papers and tutorial articles, then dive into specific papers.
13.8 Chapter Project: Research Paper Analysis
Let’s put it all together by analyzing a real research paper.
13.8.1 Project Description
Choose an algorithmic research paper whose publication date and venue are clearly stated. Select either a recent contribution or a historically important paper whose claims can be evaluated against later work, and perform a comprehensive analysis:
- Summary: Summarize the paper in your own words (1-2 pages)
- What problem does it solve?
- What is the key innovation?
- What are the main results?
- Technical Deep Dive: Explain the algorithm in detail
- Provide pseudocode
- Explain time/space complexity
- Describe key proof techniques
- Implementation: Implement the algorithm
- Test on example inputs
- Compare with baseline approaches
- Reproduce key experimental results
- Critical Analysis:
- What are the strengths?
- What are the limitations?
- What assumptions might not hold?
- Where might the algorithm fail?
- Extensions: Propose improvements or variations
- Can you extend to related problems?
- Can you improve worst-case or average-case performance?
- Can you simplify the algorithm?
- Impact Assessment: Consider broader implications
- What are potential applications?
- Are there ethical concerns?
- What future research does this enable?
13.8.2 Example Paper Choices
Learning-Augmented Algorithms: - Lykouris & Vassilvitskii (2018): “Competitive Caching with Machine Learned Advice”
Differential Privacy: - Dwork et al. (2014): “The Algorithmic Foundations of Differential Privacy”
Graph Algorithms: - Cohen et al. (2017): “Sketching and Streaming Algorithms for Analyzing Massive Graphs”
Quantum Algorithms: - Harrow et al. (2009): “Quantum Algorithm for Linear Systems of Equations” (HHL)
ML/Deep Learning: - Vaswani et al. (2017): “Attention is All You Need” (Transformers) - He et al. (2015): “Deep Residual Learning for Image Recognition” (ResNet)
Fairness: - Hardt et al. (2016): “Equality of Opportunity in Supervised Learning”
13.8.3 Analysis Template
# Paper Analysis: [Title]
## 1. Citation
[Full citation in standard format]
## 2. One-Sentence Summary
[What is the single most important contribution?]
## 3. Problem Statement
- **What problem does this paper address?**
- **Why is this problem important?**
- **What makes this problem challenging?**
## 4. Prior Work
- **What did previous approaches do?**
- **What were their limitations?**
- **What gap does this paper fill?**
## 5. Key Innovation
- **What is the main new idea?**
- **What makes this approach better?**
## 6. Algorithm Description
- **High-level overview**
- **Detailed pseudocode**
- **Key subroutines**
- **Data structures used**
## 7. Theoretical Analysis
- **Time complexity**: [with derivation]
- **Space complexity**: [with derivation]
- **Correctness proof**: [sketch]
- **Optimality**: [lower bounds, if provided]
## 8. Experimental Evaluation
- **Datasets used**
- **Baselines compared against**
- **Key results** [with numbers]
- **Where it works well / poorly**
## 9. Implementation
[Your implementation with code]
## 10. Reproduction
- **Were you able to reproduce results?**
- **Any discrepancies?**
- **Insights from implementation**
## 11. Critical Analysis
### Strengths
- [What does this paper do well?]
### Limitations
- [What are the weaknesses?]
### Assumptions
- [What assumptions are made? Are they realistic?]
## 12. Extensions
- **Possible improvements**
- **Related problems this could solve**
- **Open questions**
## 13. Broader Impact
- **Applications**
- **Ethical considerations**
- **Future research directions**
## 14. Your Assessment
- **Would you recommend this paper? Why?**
- **What did you learn?**
- **How might you build on this work?**13.9 Summary: Algorithms Shaping the Future
We’ve journeyed through the cutting edge of algorithmic research and seen how algorithms are transforming our world:
Current research trends: - Beyond worst-case analysis: algorithms for real-world data - Quantum algorithms: the coming revolution - Learning-augmented algorithms: ML meets classical CS - Differential privacy: computing on sensitive data - Algorithmic fairness: eliminating bias
AI and ML: - Deep learning: backpropagation and SGD - Transformers: attention revolutionizing everything - Reinforcement learning: algorithms that learn by doing
Big Data: - MapReduce and Spark: distributed computing at scale - Streaming algorithms: processing infinite data - Graph processing: analyzing networks with billions of edges
Cryptography: - Public-key cryptography securing the internet - Quantum threat to current systems - Blockchain and cryptocurrencies - Zero-knowledge proofs: proving without revealing
Ethics: - Accountability for algorithmic decisions - Transparency vs. performance tradeoffs - Privacy vs. utility - Algorithmic justice
The future is algorithmic. The problems we’ll solve, the technologies we’ll build, and the challenges we’ll face will all be shaped by the algorithms we design.
Your role: You now have the foundation to understand, analyze, and contribute to this future. The algorithms you’ve learned in this book are the building blocks. What you build with them is up to you.
13.10 Exercises
13.10.1 Understanding
Smoothed Analysis: Explain why sorted input (worst-case for quicksort) is fragile under perturbation.
Quantum Advantage: Why do quantum computers provide exponential speedup for factoring but not for sorting?
Fairness Impossibility: Prove that you can’t simultaneously achieve calibration and equal opportunity with different base rates.
13.10.2 Analysis
Paper Reading: Choose a paper from a recent or historically significant STOC, FOCS, or SODA proceedings. Apply the three-pass method. Write a five-page analysis.
Algorithm Comparison: Compare Count-Min Sketch vs. exact counting. For what error rates does Count-Min Sketch use less space?
Privacy-Utility Tradeoff: For Census data with differential privacy (ε=1), calculate expected error in population count.
13.10.3 Implementation
Learning-Augmented Cache: Implement LRU and learning-augmented caching. Generate realistic workload with patterns. Compare hit rates.
Streaming Distinct Count: Implement HyperLogLog. Test on stream of web requests. Compare space usage vs. exact hash set.
Fair Classifier: Take a biased dataset (COMPAS or equivalent). Train fair classifier using different fairness definitions. Compare accuracy-fairness tradeoffs.
13.10.4 Research
Extend an Algorithm: Choose a streaming algorithm. Propose and implement an improvement for a specific use case.
Fairness Metrics: Design a new fairness metric for recommendation systems. Prove it’s achievable (or show it conflicts with existing metrics).
Literature Survey: State a defensible publication window, survey papers on one topic from this chapter, and identify trends and open problems. Record the search date and databases used.
13.11 Further Reading
13.11.1 Books
Algorithms: - Mitzenmacher & Upfal: “Probability and Computing” (randomized algorithms) - Roughgarden: “Twenty Lectures on Algorithmic Game Theory”
Machine Learning: - Goodfellow, Bengio, Courville: “Deep Learning” - Sutton & Barto: “Reinforcement Learning: An Introduction”
Cryptography: - Katz & Lindell: “Introduction to Modern Cryptography” - Boneh & Shoup: “A Graduate Course in Applied Cryptography”
Ethics: - O’Neil: “Weapons of Math Destruction” - Noble: “Algorithms of Oppression” - Eubanks: “Automating Inequality”
13.11.2 Papers (Foundational)
Algorithms: - Spielman & Teng (2001): “Smoothed Analysis of Algorithms” - Muthukrishnan (2005): “Data Streams: Algorithms and Applications”
Machine Learning: - Vaswani et al. (2017): “Attention is All You Need” - Goodfellow et al. (2014): “Generative Adversarial Networks”
Fairness: - Dwork et al. (2012): “Fairness Through Awareness” - Hardt et al. (2016): “Equality of Opportunity in Supervised Learning”
13.11.3 Online Resources
- arXiv.org: Latest research preprints
- Papers With Code: Papers + implementations
- Distill.pub: Clear ML explanations
- CACM Research Highlights: Accessible explanations
You’ve completed your journey through advanced algorithms! From ancient algorithmic ideas to the cutting edge of quantum computing and AI, you now understand the foundations of computer science and the algorithms shaping our future.
The next chapter is yours to write.
What will you build? What problems will you solve? What algorithms will you invent?
The future of computing awaits. Go make it happen.