Computer science

Computer science studies how information can be represented and transformed by algorithms, and what those transformations can achieve. Its central questions connect mathematics to practical design: what answer should a procedure produce, why is it correct, and how much work does it require as its input grows? Computability theory asks which tasks can be solved at all; computational complexity theory asks what resources a solution needs.

The beauty is that choosing a representation can change what is feasible. Finding a name among a million entries sounds like a million checks. Store the entries in a sorted array, and binary search needs at most twenty middle-entry comparisons. The order makes each unsuccessful comparison eliminate a whole region of possibilities. A data structure supplies useful organization; an algorithm exploits it; time complexity explains the resulting savings.

Algorithm correctness covers every permitted input, including absent names and empty collections. Time complexity predicts scaling; statistical program profiling investigates a particular implementation.

Victor Eijkhout is a computing researcher and author of TeX by Topic by Victor Eijkhout, a technical reference explaining how TeX processes input, expands macros and builds typeset material. Its subject-based organization makes the distinction between TeX tokens, TeX expansion and later layout operations explicit.^[ref]

A small example illustrates the kind of mechanism such a reference explains. Define a TeX macro with \def\double#1{#1#1}. The call \double{ab} substitutes the argument's two letter tokens twice, producing the expanded letter-token sequence abab. In contrast, \double ab takes only the next unbraced letter token as its argument; the remaining b follows the replacement, giving aab. These are own illustrative calls under ordinary tokenization, not quotations from the book.^[ref]

The example shows why reading source as raw character substitution can be misleading. Argument boundaries and tokenization are part of the computation; the eventual visual layout is a later concern. That separation connects a practical typesetting problem with more general ideas about programming language processing.

His institutional profile also identifies work in numerical linear algebra, scientific computing and parallel computing, and links his computing textbooks. These are professional contributions beyond the TeX reference, rather than evidence inferred from a similarly named person.^[ref]

Christian Szegedy is a researcher whose coauthored work includes Inception and methods for training convolutional neural networks. Rethinking the Inception Architecture for Computer Vision by Christian Szegedy and others examines computationally efficient convolutional design and regularization, including label smoothing. The original paper's byline identifies him as a coauthor; these are collaborative contributions.^[ref]

One idea is to change training targets rather than demand probability one for a single class. For $K$ classes and smoothing amount $\epsilon$, the paper mixes the original target with a uniform distribution. In an illustrative three-class problem with target $(1,0,0)$ and $\epsilon =0.1$, this givesThe target still favors the labeled class, but allocates some mass to the others. This changes the cross-entropy training objective; it is not the same operation as fitting temperature scaling after training.^[ref]

The architectural work also motivates checking computation counts. In a simplified same-channel comparison, a five-by-five convolution uses $25C^2$ weights, while two successive three-by-three convolutions use $18C^2$, ignoring biases and boundary effects. The reduction is $7/25=28\%$. This own arithmetic illustrates the paper's factorization motivation; the two networks need not represent identical functions, particularly when a nonlinearity intervenes.^[ref]

The scientific value is the combination of testable architecture and training choices: compare classification behavior, parameter counts and computation under stated conditions rather than inferring that one named architecture is always best.

Chuan Guo is a computer scientist and coauthor of On Calibration of Modern Neural Networks by Chuan Guo and others (2017), which studies whether neural-network confidence agrees with observed correctness. Its experiments and post-processing comparisons helped make probability calibration a concrete evaluation question alongside classification accuracy. The paper marks its first three authors as equal contributors; the work should not be attributed solely to the first-listed author.^[ref]

The distinction can be illustrated without reproducing an experiment. Suppose a synthetic classifier makes $100$ predictions, of which $60$ are correct, and reports confidence $0.99$ for every selected class. Its accuracy is $60\%$, while its mean confidence is $99\%$. Changing only the reported confidence to $0.60$ leaves the predictions and accuracy unchanged but removes this group's mean confidence gap. Aggregate agreement still does not prove calibration within every subgroup.

Temperature scaling, examined in the paper, makes a related distinction operational by fitting one positive scalar to adjust probabilities while preserving the selected class within each example. The mathematical transformation and its measured limitations belong to temperature scaling; they do not imply that every classifier can be made perfectly calibrated with one number.^[ref]

Homepage: sites.google.com/view/chuanguo . The page lists the calibration paper, distinguishing this author from other researchers with the same name.

Michael F. Plass is a computer scientist whose work connects typography with mathematical optimization. With Donald E. Knuth, he coauthored the 1981 paper that describes the Knuth-Plass line-breaking algorithm: choosing breaks for an entire paragraph with dynamic programming, allowing later text to influence earlier choices. The original byline places both authors in Stanford University's Computer Science Department.^[ref]

The authors' historical account credits Michael F. Plass with introducing feasible breakpoints into the developing algorithm in summer 1977, reducing the active possibilities considered. They report its implementation in the first complete version of TeX in March 1978. These dates describe the development of the method, rather than the later publication date.^[ref]

An illustrative spacing calculation shows one ingredient of the model. Suppose fixed boxes total 24 width units and two spaces each have normal width 3 and stretchability 2. Their natural total width is 30. For a target width of 32, the adjustment ratio is $(32-30)/(2+2)=1/2$; each space becomes $3+(1/2)2=4$, giving $24+4+4=32$. This original numerical example shows proportional stretching, before the paragraph-wide choice of breaks.

The full method also represents break preferences with penalties and accounts for relevant relationships between successive lines. Line breaking with squared slack cost is a useful simpler model for understanding global choices, while the published Knuth-Plass line-breaking algorithm handles adjustable spacing and additional preferences.^[ref]

Klaus Greff is a machine learning researcher whose work includes controlled comparisons of long short-term memory architectures. His author homepage identifies the researcher and links his publications; the original byline of LSTM: A Search Space Odyssey by Klaus Greff and others confirms his participation in that study.^[ref]

The study compared eight architectural variants across three task families, optimizing hyperparameters separately for each variant. This matters because a poorly tuned variant is not a fair test of its architecture. None significantly improved on the standard architecture in the reported comparisons, while removing particular components exposed the importance of the LSTM forget gate and output activation.^[ref]

For an illustrative ablation study, compare a complete recurrent neural network with a version lacking one gate, while keeping the training task and evaluation procedure comparable. A worse result after removal is evidence about that component under the tested conditions; it does not establish that no alternative architecture could ever replace it. This is the scientific value of a controlled comparison beyond displaying one successful network.

Fred Cummins is a researcher in cognitive science and speech whose work includes the timing of people speaking together. A2019speaker profile describes his empirical investigation of joint speech. His own publication list also confirms coauthorship of the2000long short-term memory forget-gate paper with Felix A. Gers and Jürgen Schmidhuber.^[ref]

His2003study of synchronous speech asked pairs of readers to speak a prepared text together and measured their timing. Across the reported conditions, corresponding points were typically separated by about40milliseconds, with larger differences at phrase beginnings. Comparison conditions examined practice and visual access to the partner; both speakers adjusted their timing relative to individual control readings.^[ref]

This supplies a concrete scientific question: is coordinated timing produced by one speaker simply trailing the other, or by mutual adjustment? Recording both voices and comparing them with individual readings can distinguish these accounts. The result concerns a structured reading task, rather than proving that every spontaneous crowd utterance follows the same timing rule.

Felix A. Gers is a researcher in machine learning and recurrent neural networks. His institutional profile connects his research with long short-term memory; the full-name byline of his2000paper verifies the name used here.^{[ref] [ref]}

With Jürgen Schmidhuber and Fred Cummins, he introduced the adaptive LSTM forget gate to address continual input streams lacking externally marked reset points. The gate lets a LSTM memory cell learn when to reduce retained state, rather than requiring every sequence boundary to be supplied from outside.^[ref]

A scalar toy update makes selective retention tangible:Here $f_t$ is a retention multiplier and $u_t$ a new contribution. With $c_{t-1}=8$ and $u_t=0$, choices $f_t=1$, $0.25$ and $0$ retain $8$, $2$ and $0$ respectively. This arithmetic illustrates one role of a LSTM forget gate; it omits the other gates and training equations of a complete long short-term memory network. Forgetting stored state is also distinct from discarding all learned network parameters.

Jürgen Schmidhuber is a computer scientist whose research includes learning architectures for recurrent neural networks. He coauthored the1997long short-term memory paper with Sepp Hochreiter and the2000adaptive-forgetting paper with Felix A. Gers and Fred Cummins. These are team contributions documented by the original bylines.^{[ref] [ref] [ref]}

The1997architecture separates a persistent internal state from learned control of access to that state. A LSTM input gate controls new input, while a LSTM output gate controls how stored information influences output. This arrangement was designed to reduce the vanishing gradient problem that makes distant events difficult to associate during learning.^[ref]

An illustrative task presents a marked value early in a long stream, then asks for it after many irrelevant inputs. A network needs both a way to retain the relevant information and a way to protect it from later interference. The paper tested artificial long-delay tasks; success on those experiments is evidence about the architecture and learning procedure under specified conditions, not a guarantee of unlimited or error-free memory.

Sepp Hochreiter is a computer scientist working on machine learning and neural networks. His institutional profile identifies long short-term memory among his research topics. The1997paper with Jürgen Schmidhuber connects his earlier analysis of decaying learning signals to a recurrent architecture designed to preserve useful error flow.^{[ref] [ref]}

A toy chain rule calculation explains the motivation. If a learning signal is multiplied by $1/2$ at each of twenty successive steps, its contribution is scaled byThat small contribution can make an early input difficult to associate with a much later training signal. The example illustrates the vanishing gradient problem; it is not a measurement of every recurrent neural network.

The long short-term memory design introduced a controlled internal path with constant error flow, while multiplicative gates regulate access. Its artificial-data experiments included successful learning across delays exceeding1000discrete steps. The reported capability belongs to those experiments and their architecture-specific learning rules, rather than implying that any trained instance will remember every input indefinitely.^[ref]

Ray Smith is a researcher and developer associated with optical character recognition and the Tesseract engine. His official author profile records development of Tesseract at HP Labs Bristol and later work on it at Google. These are documented contributions, rather than an identification with other people sharing the name.^[ref]

His 2007 paper An Overview of the Tesseract OCR Engine by Ray Smith explains an architecture that first organizes a page into text lines and words, then performs recognition in two passes. Confident first-pass results train an adaptive classifier; a later pass revisits difficult words using what the system has learned about that document. The paper also discusses character segmentation and recognition features.^[ref]

A useful example is a page printed in one unusual font. Recognizing several clear characters can provide evidence about that page's letter shapes, helping interpret an ambiguous character elsewhere. Adaptation improves specificity but also makes the reliability of its training examples important. This explains a documented design idea; the 2007 architecture should not be assumed to describe every later Tesseract release.

Hinrich Schütze is a researcher in natural language processing and computational linguistics whose work includes learning representations of language from text. His LMU profile identifies his research and teaching at its Center for Information and Language Processing.^[ref]

In his 1998 paper Automatic Word Sense Discrimination by Hinrich Schütze, occurrences of an ambiguous word are represented by their surrounding context and grouped using clustering. The groups can distinguish uses without requiring a human to supply a sense label for every training example. The paper investigates alternative representations and evaluates how well the resulting groups separate uses.^[ref]

For an illustrative example, occurrences of “bank” near “loan” and “account” differ from occurrences near “river” and “flood”. A context vector can record such differences, and clustering can group similar vectors. This is a problem of discovering useful structure from data; the algorithm's groups need not coincide perfectly with the entries of a human dictionary. The example connects his work to unsupervised learning and to the broader use of word embeddings.

Christopher D. Manning is a researcher in natural language processing whose work connects linguistic structure with statistical and neural methods. Stanford's institutional biography identifies contributions to learned word representations, language understanding and computational analysis of sentence structure.^[ref]

He is a coauthor of Introduction to Information Retrieval by Christopher D. Manning and others. The book gives precise mathematical formulations of problems that arise when a system retrieves documents in response to a query. This connects an algorithm's output to a measurable task instead of evaluating it only by a few convincing examples.^[ref]

For instance, suppose a query has twelve relevant documents, and a system returns ten documents of which six are relevant. Its precision is $6/10=0.6$, while its recall is $6/12=0.5$. Returning more documents can change the two measures differently. This example illustrates the distinction between making useful predictions and choosing a reproducible way to evaluate them, a recurring issue in natural language processing.

D. McGrew authored RFC 5116, which specifies an interface for authenticated encryption with associated data. The RFC's author-address section identifies him as David A. McGrew. Its technical contribution is to make the inputs and outputs of encryption and authenticated decryption explicit, including the key, nonce, readable authenticated data, ciphertext and failure result.^[ref]

For example, a packet header can remain readable while being authenticated together with an encrypted payload. Changing that header must invalidate the result rather than silently attach the old payload to a different context. The RFC also separates an algorithm's nonce requirements from management of nonces by the surrounding cryptographic protocol. Reusing a key/nonce pair can violate a construction's assumptions even though the interface accepts values of the correct length.^[ref]

Brian Jeff wrote Arm's 2013 overview of its Cortex-A mobile processor roadmap. The article distinguishes architectural generations and implementation choices, explaining the Cortex-A8 as a dual-issue processor that preserves instruction issue order.^[ref]

The distinction is concrete: issuing two independent instructions in a cycle is compatible with maintaining program order. It does not by itself imply out-of-order execution, which permits ready instructions to proceed around stalled ones subject to correctness constraints. This example separates issue width from scheduling policy, two different dimensions of microarchitecture. The attribution here concerns Jeff's identified technical explanation; a product overview is not evidence that its author individually designed every processor it describes.

Google is the organizational author of the recommendation-system course cited here. Its candidate-generation explanation connects learned item and query vectors with similarity search. The choice between dot product, cosine similarity and Euclidean distance can change the selected items; normalizing vectors makes these particular rankings equivalent. This gives a concrete computational contribution of the cited documentation rather than treating the organization name as a technical method.^[ref]

The Lustre project develops and documents Lustre file system, a distributed parallel file system. Its architecture separates namespace and metadata operations from bulk file-content operations, allowing different servers to handle those workloads. A client can therefore resolve a file through the metadata service and transfer its content through object-storage services. The project documentation identifies these roles explicitly, which matters when reasoning about where a request travels and which service limits its performance.^[ref]

The CRYSTALS project developed the lattice-based designs CRYSTALS-Kyber and CRYSTALS-Dilithium. They solve different tasks: Kyber is a key encapsulation mechanism, while Dilithium provides digital signatures. Their compact representations use structured polynomial arithmetic and explicit computational hardness assumptions. Kyber's construction uses module learning with errors; Dilithium combines a Fiat-Shamir transform with response rejection. ML-KEM and ML-DSA are the corresponding standardized descendants, so a project submission and a final standard should be distinguished when choosing precise encodings or parameters.^[ref][ref]

The Khronos Group publishes interoperability specifications for graphics and related computational interfaces. Its OpenGL specification defines a rendering pipeline, including rasterization, fragment shaders and per-fragment operations. A specification makes observable behavior portable across implementations: for example, a configured depth buffer comparison determines whether a candidate surface contributes to the framebuffer. This is a definition of an interface contract, rather than a requirement that all implementations use identical internal hardware.^[ref][ref]

The World Wide Web Consortium develops Web standards through technical groups and a public review process. Its specifications can define computational behavior precisely: WebXR describes tracked poses and views, while the CSS color specification defines color values and their interpretation. Such documents distinguish an interface's semantics from the particular browser or device implementing it. A document's stated publication status also matters; a draft records work in progress rather than silently implying a completed recommendation.^[ref][ref]

Cecilia R. Aragon coauthored the randomized search-tree construction with Raimund Seidel. Their treap combines binary search tree order on keys with heap order on random priorities. A key set and distinct priorities determine the tree; independent random priorities give expected logarithmic search and update costs. The analysis separates expected cost from the possibly linear height of a particular realization.^[ref]

The construction makes balancing probabilistic without storing the explicit balance conditions used by AVL trees. Operations that split or join a tree preserve the two orderings, making the idea useful for both ordered dictionaries and sequence data structures.

Raimund Seidel coauthored Randomized Search Trees by Raimund Seidel and Cecilia R. Aragon with Cecilia R. Aragon. The paper analyzes search trees whose shape is governed by random priorities. Combining binary search tree order and heap order gives the treap, supporting searches, updates and split/join operations with expected bounds.^[ref]

The key idea is to analyze the distribution of the whole tree instead of enforcing a fixed local balance ratio after every update. For example, the item with highest priority becomes the root, and the same construction applies recursively to the smaller and larger keys. This turns priority independence into an analyzable balancing mechanism.

Jeffrey Scott Vitter coauthored the 2003 work on entropy-compressed text indexes with Roberto Grossi and Ankur Gupta. It develops compressed suffix-array representations and introduces a wavelet tree representation for symbol sequences. Bitvectors route a position through alphabet partitions, with rank queries translating that position into the selected subsequence. This connects compressed storage to efficient indexing rather than requiring full decompression for every query.^[ref]

Ankur Gupta is the coauthor named with Roberto Grossi and Jeffrey Scott Vitter on their 2003 entropy-compressed text-index paper. Its wavelet tree represents a sequence through alphabet partitions and bitvectors. Navigating a symbol uses rank queries to map positions between successive partitions, supporting operations on a compressed index. This contribution concerns searchable sequence representations; it does not identify this author with unrelated people sharing the same name.^[ref]

Roberto Grossi coauthored the 2003 entropy-compressed text-index paper with Ankur Gupta and Jeffrey Scott Vitter. The paper combines compressed suffix-array techniques with a wavelet tree, routing sequence positions through bitvectors that partition the alphabet. Its indexing bounds relate stored space to empirical entropy while retaining pattern-search functionality. The mathematical aim is both compression and access, rather than simply making a file small.^[ref]

The PostgreSQL Global Development Group is the collective project attribution used for the development and documentation of PostgreSQL, an open-source database management system. Its documentation specifies concrete behavior for database transactions, database integrity constraints, database query operations and storage mechanisms; these specifications are more precise than inferring behavior from SQL syntax alone.^[ref]

For example, PostgreSQL documents transaction isolation levels in terms of visible snapshots and permitted anomalies. The project name here identifies the responsible development community, rather than one individual author or a separate database product.

Peter Pin-Shan Chen proposed the entity-relationship model in his 1976 paper. It represents the application world through entities, relationships and attributes, together with a diagrammatic method for database design. The model aims to preserve semantic distinctions before translating them into a particular database representation.^[ref]

For example, a relationship between an employee and a project can carry an hours-worked attribute. That quantity belongs to the participation relationship, not to the employee or project alone. Making its placement explicit helps avoid duplicating or misinterpreting facts when designing a relational schema.

E. F. Codd introduced the relational model in his 1970 paper on large shared data banks. Data is represented by relations rather than application-visible pointers and access paths, supporting data independence: changing physical organization need not change the meaning of a query.^[ref]

The distinction is operationally important. A query can request tuples satisfying a predicate while the system chooses an index or scan. Applications specify the information they need instead of navigating one fixed storage layout. Mathematical relations also expose dependencies among attributes, providing a foundation for database normalization.

Margaret J. Corasick coauthored the 1975 multi-keyword matching algorithm with Alfred V. Aho. Their Aho-Corasick algorithm builds a finite-state keyword-matching machine and scans the text once, reporting occurrences of all dictionary patterns.^[ref]

A trie shares pattern prefixes, while failure links retain the longest useful suffix after a mismatch. For patterns he and she, reaching the end of she must also report he; terminal suffix information is therefore part of matching, not merely following trie edges. The mechanism makes one text scan reusable across many search terms.

Alfred V. Aho coauthored Efficient String Matching: An Aid to Bibliographic Search by Alfred V. Aho and Margaret J. Corasick with Margaret J. Corasick in 1975. Their Aho-Corasick algorithm constructs a machine for a whole pattern dictionary and searches a text in a single pass.^[ref]

Its useful distinction is between text progress and pattern progress. On a failed extension, a failure link changes the candidate pattern prefix without moving backward in the text. Shared prefixes and suffix continuations avoid repeating a complete independent search for every keyword, while reporting cost still grows with the number of actual matches.

Ugo Montanari coauthored the 1982 unification algorithm with Alberto Martelli. Their paper treats first-order terms as equations and derives an efficient implementation from simpler transformation rules, integrating the acyclicity test needed for finite terms.^[ref]

For example, decomposing $f(x,a)=f(b,y)$ gives $x=b$ and $y=a$, whereas $x=f(x)$ has no finite-term solution and must be rejected. The point is to compute a most general unifier without expanding or repeatedly traversing shared term structure unnecessarily. Such unification supports automated deduction and logic programming.

Alberto Martelli coauthored An Efficient Unification Algorithm by Alberto Martelli and Ugo Montanari in 1982. With Ugo Montanari, he developed a term-equation algorithm whose acyclicity check is built into the implementation rather than treated as an expensive separate afterthought.^[ref]

Unification asks for a substitution making terms identical; the most general unifier captures every solution through further substitution. This is stronger than finding one arbitrary matching assignment. The paper's equation transformations preserve the solution set while detecting incompatible constructors and cyclic finite-term requirements, connecting a declarative specification to an efficient procedure.

J. A. Robinson introduced the resolution principle in his 1965 paper on machine-oriented logic. His clause-based resolution calculus, using unification, supports a complete refutation procedure for first-order logic: an unsatisfiable clause set has a derivation of the empty clause.^[ref]

For example, resolving $P(x)\vee Q(x)$ with $\neg P(a)$ uses the first-order substitution $x\mapsto a$ and produces $Q(a)$. The rule separates the logical justification of a step from the search for useful clauses. A complete search procedure can still run indefinitely on a satisfiable input; completeness does not supply a decision algorithm for all first-order logic.

Paul C. van Oorschot coauthored the Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone. Its treatment connects cryptographic constructions with explicit mathematical algorithms and stated assumptions, rather than describing encryption only as a black box. The number-theoretic chapter includes algorithms for modular square roots, while the public-key chapter gives RSA cryptosystem and Rabin cryptosystem constructions.^[ref]

For a concrete special case, if $p\equiv 3(\mathrm{mod}4)$ is prime and $a$ is a nonzero square modulo $p$, a square root is $a^{(p+1)/4}\mathrm{mod}p$. This illustrates how assumptions on an integer modulus determine which algorithm and correctness argument apply.

Ryuhei Mori coauthored the 2021 algorithm for distant terms of a linear recurrence with Alin Bostan. Their Bostan-Mori algorithm uses coefficient extraction on a rational generating function $P(x)/Q(x)$ by repeatedly halving the requested index.^[ref]

Multiplying numerator and denominator by $Q(-x)$ makes the denominator even. Selecting the numerator's polynomial coefficients at even or odd powers according to the index parity reduces the problem to index $\lfloor N/2\rfloor$. With recurrence order $d$, the method uses $O(M(d)\log N)$ arithmetic operations, where $M(d)$ is the cost of multiplying polynomials of polynomial degree $d$. This reaches a distant term without computing every preceding term.

Silvio Micali coauthored the construction of pseudorandom function families with Oded Goldreich and Shafi Goldwasser. Their 1986 paper extends pseudorandomness from a generated binary string to a function that can be evaluated repeatedly at chosen inputs.^[ref]

A short key specifies an efficiently evaluated function even though its full truth table can be exponentially large. The comparison experiment is a single randomly chosen function, so repeated queries must receive consistent answers. That consistency distinguishes function security from supplying fresh independent random bits on every call.

Shafi Goldwasser coauthored How to Construct Random Functions by Oded Goldreich, Shafi Goldwasser and Silvio Micali. The paper formalizes pseudorandom function families through an observer's ability to distinguish keyed evaluation from access to one uniformly random function.^[ref]

The observer may choose later inputs after seeing earlier answers. Security therefore concerns the whole interaction, not just whether each separate output appears balanced. This computational experiment makes an apparently random reusable function a precise cryptographic object, conditional on the underlying hardness assumptions.

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.

Steven Rudich coauthored the natural proof framework with Alexander A. Razborov. Their 1997 paper identifies a barrier to a broad form of circuit lower bound argument, conditional on a sufficiently strong pseudorandom function family security assumption.^[ref]

A property that is efficiently recognizable from a truth table, holds for many random Boolean functions and excludes the target small-circuit class could distinguish pseudorandom function families from random ones. The required security must cover the time spent reading the entire table, which is exponential in the function's input length. The barrier restricts these proof methods under its assumption; it does not prove that circuit lower bounds are impossible.

Alexander A. Razborov coauthored Natural Proofs by Alexander A. Razborov and Steven Rudich with Steven Rudich. They analyzed why many successful restricted-model circuit lower bounds do not straightforwardly establish strong lower bounds for general Boolean circuits.^[ref]

Their framework separates a constructive property of Boolean functions, a large property of Boolean functions and a useful property against a circuit class. Together these can provide a statistical test contradicting a quantitatively strong pseudorandom function family assumption. The test for a constructive property of Boolean functions is measured against truth table size, not merely the number of input bits; that distinction is essential when stating the cryptographic hypothesis precisely.

Somenath Biswas coauthored the 2003 paper on primality testing and polynomial identity testing with Manindra Agrawal. Their randomized algorithm reduces a candidate integer's primality to a univariate polynomial identity over the integers modulo that candidate.^[ref]

A polynomial can have very high polynomial degree while being represented by a small arithmetic circuit. Expanding every polynomial coefficient can then be impractical. The paper also gives randomized algorithms for multivariate polynomial identity testing with running time polynomial in the circuit representation size and an error parameter. The input representation and probability of error are consequently essential parts of the algorithmic statement.

Manindra Agrawal coauthored Primality and Identity Testing via Chinese Remaindering by Manindra Agrawal and Somenath Biswas with Somenath Biswas in 2003. The paper connects primality testing to polynomial identity testing, using randomized algorithms for circuit-represented polynomials over finite fields, the rationals and, for one procedure, integers modulo an arbitrary candidate.^[ref]

The computational problem is not simply evaluating an already expanded polynomial: a compact arithmetic circuit may encode exponentially many polynomial coefficients. A successful test must exploit that representation without materializing the expansion. This distinction connects an algebraic identity to an implementable randomized algorithm.

Michael O. Rabin analyzed a randomized algorithm for primality testing in his 1980 paper. The Miller-Rabin primality test checks whether a candidate integer satisfies conditions obeyed by primes under modular exponentiation. A failed check certifies compositeness; passing a check gives a probable prime, not a proof of primality.^[ref]

For each fixed odd composite candidate, at most one quarter of the admissible bases are strong liars. Independent uniformly chosen bases therefore reduce the probability of accepting that composite to at most $4^{-k}$ after $k$ rounds. This probability is over the test's choices for a fixed input; it is not a posterior probability that an arbitrary accepted integer is prime.

Leslie G. Valiant proved in 1979 that computing the permanent of a zero-one matrix is complete for the counting complexity class $\#\mathbf{P}$ under the paper's arithmetic reductions.^[ref]

For a bipartite graph's zero-one adjacency matrix, the permanent counts perfect matchings. Deciding whether one exists admits a polynomial-time algorithm, while counting all of them has the paper's much stronger completeness property. This makes the difference between existence and counting concrete. The permanent resembles the determinant but lacks its alternating signs, so an efficient determinant algorithm does not automatically compute it. Valiant's permanent reduction encodes logical constraints into weighted combinatorial choices.

Publisher of the MIPS32 Architecture For Programmers Volume II by MIPS Technologies.

Pat Morin wrote Open Data Structures: An Introduction by Pat Morin, an open textbook presenting implementations of data structures together with mathematical analyses of their operation costs. Its topics include hashing, search trees, heaps and graphs. The text makes the representation part of the performance argument, rather than treating an abstract operation name as a sufficient cost model.^[ref]

Remzi H. Arpaci-Dusseau coauthored Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and others. The book organizes operating systems around virtualization, concurrent computing and persistence: sharing hardware, coordinating overlapping execution and retaining data. Its worked models connect process scheduling, virtual memory and file systems to the mechanisms that implement those goals.^[ref]

Andrea C. Arpaci-Dusseau coauthored Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and others. The book organizes operating systems around virtualization, concurrent computing and persistence: sharing hardware, coordinating overlapping execution and retaining data. Its worked models connect process scheduling, virtual memory and file systems to the mechanisms that implement those goals.^[ref]