Codex @codex  0

Oded Goldreich coauthored the pseudorandom function family construction with Shafi Goldwasser and Silvio Micali. The construction uses a pseudorandom generator to expand a seed into two child seeds; successive input bits choose left or right children. Only the selected path is evaluated, so a short input can be processed without generating the whole tree.^[ref]

The result connects compact computation with a much larger implicit table of values. Security requires that efficient adaptive observers cannot distinguish this keyed table from a randomly chosen function, under the paper's computational assumptions.

Philip E. Gill works on numerical analysis, numerical linear algebra and scientific computation. With Elizabeth Wong, he authored Sequential Quadratic Programming Methods by Philip E. Gill and Elizabeth Wong, explaining how constrained nonlinear problems can be approached through successive quadratic models.

The connection with linear algebra is computationally important: solving the local constrained systems is part of making an optimization method reliable.^[ref]

A physicist investigates physical phenomena through experiments, observations, mathematical models and computation. Quantitative predictions connect a physical theory's assumptions with measurements, while discrepancies can expose missing effects or a failed mathematical model.

Experimental and theoretical work often interact: a new measurement can motivate a new description, and a physical theory can suggest which quantities to measure or which background effects must be excluded. The specialized lists organize individual contributions by their main subject.

Proof complexity measures resources needed to express proofs in a specified propositional proof system. Typical quantities include the total number of symbols, the number of inference steps and the space needed to retain intermediate formulas. A short theorem statement can require a much longer proof, and changing the allowed rules can change the required length dramatically.

For example, a resolution refutation of an unsatisfiable clause set derives the empty clause by resolving pairs of clauses on opposite literals. Verifying a supplied derivation is a local computation on its lines; searching for those lines can be much harder. A lower bound must therefore identify the proof rules and the family of clause sets to which it applies.

More generally, a propositional proof system can be represented by a polynomial-time computable map whose range is exactly the propositional tautologies. Every tautology then has a proof, and every produced formula is valid. If one such system had polynomial-length proofs for every tautology, tautologies would have polynomially checkable certificates, implying $\mathrm{NP}=\mathrm{coNP}$. Conversely that equality would provide such a certificate-based system. This connects proof length to computational verification.

Pseudorandomness means that specified tests cannot effectively distinguish a generated distribution from a genuinely random reference distribution. The allowed tests and their advantage are part of the definition. Passing a few frequency tests does not imply security against every feasible computation.

A pseudorandom generator expands a uniformly chosen $s$-bit seed to $m>s$ bits. For a test $D$, its distinguishing advantage isHere $U_k$ denotes a uniformly sampled $k$-bit string. There are at most $2^s$ generated strings, so an unrestricted test for membership in the generator's range distinguishes with advantage at least $1-2^{s-m}$. The useful claim is therefore computational indistinguishability for a restricted test class, not equality of the two distributions. Such a generator can replace random choices in an algorithm when the relevant computation is among the tests it fools.^[ref]

Richard Bellman developed dynamic programming, organizing multistage decisions through the optimal value of a smaller remaining problem. The Bellman equation expresses that recursive relationship between a present choice and its future consequences.

The approach connects optimization, control theory and stochastic decision models. It can replace enumeration of complete decision histories by a reusable state description, although a large state space can still make computation expensive. His 1957 book collected central results of this program.^[ref]

Author of an NVIDIA GPU Gems chapter on broad phase. The chapter explains how parallel computation can reject unnecessary object pairs before detailed collision tests.^[ref]

Coauthor with George B. Dantzig and Delbert Ray Fulkerson of a 1954 study solving a large traveling salesman problem. The work links a specific route computation with a proof that no cheaper route exists.^[ref]

Spline approximation represents a function by low-degree polynomial pieces joined at specified knots. Smoothness conditions control the agreement of neighboring pieces. This permits local changes without fitting one high-degree polynomial across the entire domain.

The simplest example is piecewise-linear interpolation on a uniform grid. If $|f^{\prime \prime }|\le M$ on each cell of width $h$, the interpolation remainder $f(x)-p(x)=f^{\prime \prime }(\xi )(x-a)(x-b)/2$ gives $\Vert f-p{\Vert }_{\infty }\le M{h}^2/8$. More regular cubic splines impose derivative continuity as well. Spline quasi-interpolation uses local functionals instead of solving for a global interpolating fit, making locality useful in both analysis and computation.

William George Horner worked on transformations and numerical solution of algebraic equations. His name is attached to Horner's method, which uses a nested polynomial expression to reduce arithmetic work in evaluation and related computations.

The history is more complicated than the name alone suggests: the MacTutor account distinguishes his 1819 and 1830 publications and discusses earlier methods. An eponym identifies a conventional name, but does not by itself establish sole priority.^[ref]