Chapter 165: Modern Research Topics in Algorithms

Prerequisites

Advanced algorithms, complexity theory, probability theory

These topics rarely appear in standard interviews but are essential for research-oriented roles, PhD interviews, and cutting-edge system design at Google Research, Microsoft Research, Meta FAIR, and DeepMind.

165.1 Fine-Grained Complexity

Definition

Fine-grained complexity studies exact polynomial degrees of problems, not just P vs NP. It provides conditional lower bounds: “If problem X has no faster algorithm, then neither does problem Y.”

Motivation

Classical complexity tells us O(n²) and O(n¹⁰⁰) are both “polynomial.” Fine-grained complexity distinguishes between them, proving tight lower bounds based on conjectures.

Key Conjectures

Conjecture	Statement	Implication
SETH (Strong Exponential Time Hk)	No O((2-ε)^n) for CNF-SAT	Many n² lower bounds
OV Conjecture	No O(n^{2-ε}) for Orthogonal Vectors	Graph diameter, edit distance
3SUM Conjecture	No O(n^{2-ε}) for 3SUM	Many geometry problems
APSP Conjecture	No O(n^{3-ε}) for All-Pairs Shortest Path	Many graph problems

Formal Explanation

SETH: For every ε > 0, there exists a k such that k-SAT cannot be solved in O((2-ε)^n) time.

Theorem (SETH implies Edit Distance lower bound): If edit distance of two length-n strings can be computed in O(n^{2-ε}) time, then SETH is false.

Step-by-Step: Reducing SAT to Edit Distance

1. Given a k-SAT formula φ with n variables
2. Construct string A encoding all possible variable assignments
3. Construct string B encoding the formula structure
4. EditDistance(A, B) is small iff φ is satisfiable
5. O(n^{2-ε}) edit distance → O((2-ε')^n) SAT → SETH false

Implications for Practice

// This O(n²) algorithm for edit distance is OPTIMAL under SETH
int editDistance(const std::string& a, const std::string& b) {
    int n = a.size(), m = b.size();
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1));

    for (int i = 0; i <= n; i++) dp[i][0] = i;
    for (int j = 0; j <= m; j++) dp[0][j] = j;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i-1] == b[j-1])
                dp[i][j] = dp[i-1][j-1];
            else
                dp[i][j] = 1 + std::min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
        }
    }
    return dp[n][m];  // O(nm) is tight under SETH
}

165.2 Property Testing

Definition

Given a property P and parameter ε, a property tester determines whether an object has property P or is ε-far from P, using only poly(1/ε) queries (independent of input size n).

Motivation

For massive datasets (terabytes), even reading the entire input is expensive. Property testing provides sublinear-time algorithms that give probabilistic guarantees.

Intuition

Imagine testing whether a massive array is sorted. Instead of checking every pair, sample random adjacent pairs. If the array is sorted, you’ll never find an inversion. If it’s far from sorted, you’ll find one quickly.

Formal Explanation

An (ε, q)-tester for property P is a randomized algorithm that:

Makes at most q queries to the input
If input has property P: accepts with probability ≥ 2/3
If input is ε-far from P: rejects with probability ≥ 2/3

“ε-far” means at least ε·n modifications are needed to satisfy P.

Algorithm: Testing Sortedness

#include <iostream>
#include <vector>
#include <random>
#include <algorithm>

class SortednessTester {
    std::mt19937 rng;

public:
    SortednessTester() : rng(42) {}

    // Returns true if array is "probably sorted"
    // Returns false if array is "definitely far from sorted"
    bool isSorted(const std::vector<int>& arr, double epsilon) {
        int n = arr.size();
        if (n <= 1) return true;

        // Number of samples needed: O(1/epsilon)
        int samples = std::max(100, (int)(2.0 / epsilon));
        std::uniform_int_distribution<int> dist(0, n - 2);

        for (int t = 0; t < samples; t++) {
            int i = dist(rng);
            if (arr[i] > arr[i + 1])
                return false;  // Found inversion
        }
        return true;  // Probably sorted
    }
};

int main() {
    SortednessTester tester;

    std::vector<int> sorted = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::vector<int> almost_sorted = {1, 2, 3, 4, 5, 6, 7, 8, 10, 9};
    std::vector<int> random_arr = {5, 2, 8, 1, 9, 3, 7, 4, 6, 10};

    std::cout << "Sorted: " << tester.isSorted(sorted, 0.1) << "\n";
    std::cout << "Almost sorted: " << tester.isSorted(almost_sorted, 0.1) << "\n";
    std::cout << "Random: " << tester.isSorted(random_arr, 0.1) << "\n";

    return 0;
}

Walkthrough

Input: [1, 2, 3, 4, 5, 6, 7, 8, 10, 9], ε = 0.1
Samples needed: 100

Trial 1: Check indices (3,4): arr[3]=4, arr[4]=5 → OK
Trial 2: Check indices (7,8): arr[7]=8, arr[8]=10 → OK
Trial 3: Check indices (8,9): arr[8]=10, arr[9]=9 → INVERSION!
→ Return false (not sorted)

Complexity

Problem	Queries	Time
Sortedness	O(1/ε)	O(1/ε)
Bipartiteness	O(1/ε)	O(n/ε)
Connectivity	O(1/ε)	O(n·polylog n)
Triangle-freeness	O(1/ε²)	O(n²)

165.3 Sublinear Algorithms

Definition

Algorithms that use o(n) time or space on inputs of size n, typically via sampling, sketching, or streaming.

Motivation

Modern datasets are enormous (petabytes). Loading them entirely is infeasible. Sublinear algorithms process data in a single pass using limited memory.

Streaming Algorithms

#include <iostream>
#include <vector>
#include <random>
#include <cmath>
#include <algorithm>

// Count-Min Sketch: estimate frequency of items in a stream
class CountMinSketch {
    int width, depth;
    std::vector<std::vector<int>> table;
    std::vector<int> hashes_a, hashes_b;
    int p;  // Large prime

public:
    CountMinSketch(int w, int d) : width(w), depth(d),
        table(d, std::vector<int>(w, 0)),
        hashes_a(d), hashes_b(d), p(1000000007) {

        std::mt19937 rng(42);
        for (int i = 0; i < d; i++) {
            hashes_a[i] = std::uniform_int_distribution<int>(1, p-1)(rng);
            hashes_b[i] = std::uniform_int_distribution<int>(0, p-1)(rng);
        }
    }

    void add(int item) {
        for (int i = 0; i < depth; i++) {
            int idx = ((long long)hashes_a[i] * item + hashes_b[i]) % p % width;
            table[i][idx]++;
        }
    }

    int estimate(int item) const {
        int minCount = INT_MAX;
        for (int i = 0; i < depth; i++) {
            int idx = ((long long)hashes_a[i] * item + hashes_b[i]) % p % width;
            minCount = std::min(minCount, table[i][idx]);
        }
        return minCount;
    }
};

int main() {
    CountMinSketch cms(1000, 5);

    // Simulate stream: item 42 appears 1000 times
    for (int i = 0; i < 1000; i++) cms.add(42);
    for (int i = 0; i < 100; i++) cms.add(99);

    std::cout << "Frequency of 42: " << cms.estimate(42) << " (actual: 1000)\n";
    std::cout << "Frequency of 99: " << cms.estimate(99) << " (actual: 100)\n";

    return 0;
}

HyperLogLog: Counting Distinct Elements

import hashlib
import math

class HyperLogLog:
    """Simplified HyperLogLog for counting distinct elements."""
    def __init__(self, precision=10):
        self.p = precision
        self.m = 1 << self.p  # Number of registers
        self.registers = [0] * self.m

    def _hash(self, item):
        h = hashlib.sha256(str(item).encode()).hexdigest()
        return int(h, 16)

    def add(self, item):
        h = self._hash(item)
        idx = h & (self.m - 1)           # First p bits: register index
        remaining = h >> self.p
        self.registers[idx] = max(self.registers[idx],
                                   self._trailing_zeros(remaining) + 1)

    def _trailing_zeros(self, x):
        # Counts the number of trailing zero bits in x (i.e., the position
        # of the lowest set bit, minus 1). Used by HyperLogLog to estimate
        # the rarity of the hash prefix.
        if x == 0:
            return 64 - self.p
        count = 0
        while (x & 1) == 0:
            count += 1
            x >>= 1
        return count

    def count(self):
        alpha = 0.7213 / (1 + 1.079 / self.m)
        raw = alpha * self.m * self.m / sum(2**(-r) for r in self.registers)
        return int(raw)

# Usage
hll = HyperLogLog()
for i in range(100000):
    hll.add(i)
print(f"Estimated distinct: {hll.count()}")  # ~100000

165.4 Quantum Algorithms

Definition

Algorithms that run on quantum computers, exploiting superposition, entanglement, and interference for speedups over classical algorithms.

Key Algorithms

Algorithm	Problem	Classical	Quantum	Speedup
Grover’s	Unstructured search	O(n)	O(√n)	Quadratic
Shor’s	Integer factoring	O(exp(n^{1/3}))	O(n³)	Exponential
Quantum Walk	Graph problems	Varies	Varies	Polynomial-Exponential
HHL	Linear systems Ax=b	O(n³)	O(poly(log n))	Exponential*

*HHL has significant caveats: requires specific matrix structure and quantum-accessible input.

Grover’s Algorithm Intuition

import numpy as np

def grover_simulation(n_qubits, target):
    """
    Simulate Grover's algorithm for searching an unsorted list.
    n_qubits: log2 of search space size
    target: index to search for
    """
    N = 2 ** n_qubits
    iterations = int(np.pi / 4 * np.sqrt(N))

    # Initialize uniform superposition
    state = np.ones(N) / np.sqrt(N)

    # Oracle: flip sign of target
    oracle = np.eye(N)
    oracle[target][target] = -1

    # Diffusion operator: 2|s><s| - I
    s = np.ones(N) / np.sqrt(N)
    diffusion = 2 * np.outer(s, s) - np.eye(N)

    for _ in range(iterations):
        state = oracle @ state     # Oracle step
        state = diffusion @ state  # Diffusion step

    # Measure: probability of target
    prob = abs(state[target]) ** 2
    return prob, iterations

# Search in 1024 elements: need only ~25 iterations
prob, iters = grover_simulation(10, 42)
print(f"Found target with probability {prob:.4f} in {iters} iterations")

165.5 Differential Privacy

Definition

A mathematical framework for quantifying and limiting the privacy loss when analyzing data. An algorithm satisfies ε-differential privacy if changing any single individual’s data changes the output probability by at most e^ε.

Motivation

Organizations collect sensitive data (health records, location). Even “anonymized” data can be de-anonymized. Differential privacy provides formal guarantees.

Formal Definition

A randomized mechanism M satisfies ε-differential privacy if for all neighboring datasets D, D’ (differing in one record) and all output sets S:

Pr[M(D) ∈ S] ≤ e^ε · Pr[M(D') ∈ S]

Laplace Mechanism

import numpy as np

def laplace_mechanism(true_answer, sensitivity, epsilon):
    """
    Add Laplace noise to achieve ε-differential privacy.
    sensitivity: max change in answer when one record changes
    epsilon: privacy parameter (smaller = more private)
    """
    scale = sensitivity / epsilon
    noise = np.random.laplace(0, scale)
    return true_answer + noise

# Example: Average salary (sensitivity = max_salary / n)
salaries = [50000, 60000, 70000, 80000, 90000]
true_avg = np.mean(salaries)
n = len(salaries)
sensitivity = (max(salaries) - min(salaries)) / n

# Private answers with different epsilon values
for eps in [0.1, 1.0, 10.0]:
    private_avg = laplace_mechanism(true_avg, sensitivity, eps)
    print(f"ε={eps}: true={true_avg:.0f}, private={private_avg:.0f}")

Exponential Mechanism

def exponential_mechanism(scores, epsilon, sensitivity=1.0):
    """
    Select output with probability proportional to exp(ε·score / 2Δ).
    Used for non-numeric queries (e.g., "most popular item").
    """
    max_score = max(scores)
    weights = [np.exp(epsilon * (s - max_score) / (2 * sensitivity)) for s in scores]
    total = sum(weights)
    probs = [w / total for w in weights]
    return np.random.choice(len(scores), p=probs)

# Select "best" category while preserving privacy
categories = ["A", "B", "C", "D"]
scores = [10, 8, 15, 12]  # True popularity scores
selected = exponential_mechanism(scores, epsilon=1.0)
print(f"Selected: {categories[selected]} (highest score was C=15)")

Protocol	Communication	Error
Send all bits	n bits	0
Send hash	O(log n) bits	Low
Randomized	O(1) bits	1/2^k

#include <iostream>
#include <vector>
#include <random>
#include <functional>

// Randomized equality protocol with O(1) communication
bool randomizedEquality(const std::vector<int>& x, const std::vector<int>& y,
                        int num_hashes = 20) {
    std::mt19937 rng(42);
    std::uniform_int_distribution<int> dist(1, 1000000007);

    int a = dist(rng), b = dist(rng), p = 1000000007;

    auto hash = [&](const std::vector<int>& v) {
        long long h = 0;
        for (int x : v) h = (h * a + x + b) % p;
        return h;
    };

    // Alice sends hash(x), Bob computes hash(y) and compares
    // Repeat to reduce error probability
    for (int i = 0; i < num_hashes; i++) {
        a = dist(rng); b = dist(rng);
        if (hash(x) != hash(y)) return false;
    }
    return true;  // Equal with probability ≥ 1 - 1/2^num_hashes
}

int main() {
    std::vector<int> x = {1, 2, 3, 4, 5};
    std::vector<int> y = {1, 2, 3, 4, 5};
    std::vector<int> z = {1, 2, 3, 4, 6};

    std::cout << "x == y: " << randomizedEquality(x, y) << "\n";
    std::cout << "x == z: " << randomizedEquality(x, z) << "\n";

    return 0;
}

#include <iostream>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <vector>

// LRU Cache: O(1) per operation, competitive ratio = k (cache size)
class LRUCache {
    int capacity;
    std::list<int> order;  // Most recent at front
    std::unordered_map<int, std::list<int>::iterator> cache;

public:
    LRUCache(int cap) : capacity(cap) {}

    bool access(int page) {
        if (cache.count(page)) {
            order.erase(cache[page]);
            order.push_front(page);
            cache[page] = order.begin();
            return true;  // Hit
        }

        if ((int)order.size() >= capacity) {
            int lru = order.back();
            order.pop_back();
            cache.erase(lru);
        }

        order.push_front(page);
        cache[page] = order.begin();
        return false;  // Miss
    }
};

int main() {
    LRUCache cache(3);
    std::vector<int> requests = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5};

    int hits = 0;
    for (int page : requests) {
        if (cache.access(page)) hits++;
        std::cout << "Page " << page << (cache.access(page) ? " hit" : " miss") << "\n";
    }
    std::cout << "Hit rate: " << hits << "/" << requests.size() << "\n";

    return 0;
}

165.8 Exercises

SETH exercise: Assuming SETH, prove that computing the diameter of a sparse graph requires Ω(n²) time.
Property tester: Design a property tester for “array has all distinct elements” with O(1/ε) queries.
Count-Min Sketch: Implement a Count-Min Sketch and estimate the frequency of items in a stream of 1M elements.
Differential privacy: Implement the Gaussian mechanism (adds Gaussian noise instead of Laplace) for ε,δ-differential privacy.
Communication complexity: Prove that the equality function requires Ω(n) bits of communication in the deterministic case.
Grover’s simulation: Extend the Grover’s simulation to handle multiple targets.
Competitive ratio: Prove that LRU has competitive ratio k for the paging problem.

165.9 Interview Questions

What is SETH and why does it matter? Answer: SETH states that CNF-SAT requires essentially 2^n time. It’s used to prove conditional lower bounds—showing that a faster algorithm for problem X would break SETH, implying X is likely optimal.
Explain property testing in simple terms. Answer: Instead of checking an entire dataset, we randomly sample a few elements to determine if a property holds (probably true) or if the data is far from satisfying it (probably false). The number of samples depends only on the desired accuracy, not the dataset size.
How does differential privacy protect individuals? Answer: By adding calibrated random noise to query results. The noise is enough to mask any single individual’s contribution, so their presence or absence in the dataset doesn’t meaningfully change the output.
What is the difference between streaming and sublinear algorithms? Answer: Streaming algorithms process data in one pass with limited memory. Sublinear algorithms more broadly use o(n) time or space. Streaming is a subset—some sublinear algorithms make multiple passes or random accesses.
Explain the power of two choices in load balancing. Answer: When placing n balls into n bins, choosing the less loaded of 2 random bins reduces the maximum load from Θ(log n / log log n) to Θ(log log n). This dramatic improvement comes at the cost of one extra random choice.

165.10 Cross-References

Chapter 3: Asymptotic analysis and complexity classes
Chapter 12: Hashing (for Count-Min Sketch, HyperLogLog)
Chapter 27: Graph algorithms (for quantum walk applications)
Chapter 75: Randomized algorithms basics
Chapter 150: Advanced randomized techniques
Chapter 164: Approximation algorithms (for competitive analysis)

Summary

Area	Key Idea	Impact
Fine-Grained Complexity	Conditional lower bounds via SETH	Proves optimality of known algorithms
Property Testing	Sublinear queries, probabilistic	Massive dataset analysis
Sublinear Algorithms	o(n) time and space	Streaming, big data
Quantum Algorithms	Quantum speedup (Grover, Shor)	Future of computing
Differential Privacy	Calibrated noise for privacy	Data protection guarantees
Communication Complexity	Bits to compute jointly	Distributed computing limits
Online Algorithms	No future knowledge	Competitive analysis

Keyboard shortcuts

Placement Preparation Knowledge Base