Foundations

A proof in a black-box encryption or signature game typically exposes specified outputs and oracles, not secret-dependent timing, power, cache traces or fault responses.

PAC learning bounds population risk with probability at least 1−delta from iid samples.

For a finite hypothesis class H, iid observations and losses in [0,1], Hoeffding plus a union bound gives probability at most 2|H|exp(−2n epsilon²) that any empirical risk differs from its population risk by more than epsilon.

VC dimension is the largest size of a point set on which a binary hypothesis class realizes every labeling.

Bayesian inference combines likelihood and prior into a posterior conditional on observed data.

A qubit pure state is a normalized vector in C² modulo global phase; a mixed state is a positive trace-one density operator.

A physical channel on a subsystem is modeled by a completely positive trace-preserving map.

A quantum circuit composes unitary gates, ancillas, channels and measurements from a specified gate set.

For an unstructured search over N alternatives with a coherent marking oracle and one marked item, amplitude amplification uses O(sqrt(N)) oracle queries for bounded success probability.

Shor's factoring algorithm reduces factoring to order finding and uses modular exponentiation, quantum phase/Fourier processing and classical continued fractions.

Von Neumann entropy is −tr rho log2 rho and equals Shannon entropy of the density operator's eigenvalues.

A relation is a set of tuples over a schema.

A candidate key is a minimal attribute set uniquely identifying a tuple; a superkey need not be minimal.

A transaction groups operations with atomic commit or abort.

PostgreSQL 18 repeatable read uses snapshot isolation: each transaction reads a stable snapshot, but concurrent writes to different rows can produce write skew and a nonserializable joint outcome.

An operational semantics defines a transition relation between program configurations, including state when needed.

For the declared simply typed language, progress says a closed well-typed term is a value or can take a step; preservation says evaluation retains its type.

Sequential consistency presents operations in one order preserving each thread's program order.

CompCert's principal semantic-preservation theorem relates accepted C abstract syntax to generated assembly abstract syntax: generated behavior refines permitted source behavior under the theorem's hypotheses.

The official CompCert 3.18 release in August 2026 revises formal handling of alignment/free and adds Rocq 9.2 support.

For predictors h, population risk is expected loss under a declared data distribution; empirical risk averages loss over a sample.

Regularized empirical minimization adds lambda times a complexity penalty to sample loss.

Stochastic gradient updates parameters using a sampled gradient or subgradient.

PCA finds an orthogonal low-rank subspace minimizing squared reconstruction error for centered observations.

Training fits parameters, validation selects models/tuning, and a final held-out test estimates performance of the selected procedure on its sampling population.

A Bayesian network uses a directed acyclic graph and local conditional distributions to factor a joint law.

Variational inference approximates a posterior by choosing q from a specified family to minimize KL(q||posterior).

MCMC constructs a Markov chain with a desired stationary posterior and estimates integrals from correlated draws; convergence, mixing and effective sample size require checks.

Observational conditioning p(Y|X=x) and intervention p(Y|do(X=x)) describe different operations.

Crash faults stop a process; Byzantine faults permit arbitrary behavior, including inconsistent messages.