Papers, Presentations, Theses, and Patents
Here is a curated set of our publications, each with an playful, sometimes whimsical, description of its content and impact. Where different versions of a paper have been published in different venues, say first in conference proceedings and then in a journal, these are grouped together in one entry.
Storing with Molecules
|
Automated Routing of Droplets for DNA Storage on a Digital Microfluidics Platform
DNA offers a library in a speck of dust; the trouble is printing the books. Its four-letter alphabet can, in principle, store two bits in every nucleotide, while sequencing and synthesis have advanced on a Moore’s-law-like trajectory. Yet a wide gap remains between DNA’s theoretical capacity as an archive and the rate at which data can actually be written. This paper turns synthesis into an automated molecular print shop on a vast digital-microfluidic chip. “Symbol” droplets carry short blocks of data; “linker” droplets lock them into the intended order during Gibson assembly. A compiler decomposes the requested strand into an assembly tree, and prioritized 3-D A* routes thousands of droplets across the electrode grid, treating time as a third dimension and reserving space to prevent collisions. The simulations reveal both the unprecedented parallelism of the approach and the formidable traffic required to command it. If DNA is to store so much data so efficiently, its alphabet needs a printing press. |
Computing with Molecules
|
Each well in this computer holds a tiny election. Acid and base droplets cast opposing votes; neutralization counts them, and whichever side has the majority determines the result. Majority alone is not enough for universal logic, so every value travels on two rails, an acid–base pair and its mirror image. Negation then requires no exotic reaction: the robotic liquid handler simply crosses the rails. From that modest trick come AND, OR, decoders, and neural-network inference, with the liquid handler serving as the wiring and a pH indicator announcing the winner in color. Experiments classified handwritten digits in close agreement with the electronic model. Successive stages do drift toward neutrality, so larger circuits will need a way to restore their chemical conviction. Still, the paper extracts universal computation from chemistry familiar to any first-year student. The computer is a ballot box with a color readout. |
|
Computing Mathematical Functions with Chemical Reactions via Stochastic Logic
Truth tables are usually blueprints for silicon; here each row becomes a line in a chemical recipe. A number between zero and one is stored as the relative concentration of two molecular species, one playing 0 and the other 1. When the ingredients collide, their subscripts select a row of the truth table and produce the corresponding output species. Stochastic logic supplies the sleight of hand: a Boolean circuit acting on probabilities computes an analog polynomial, so the same recipe can approximate arctangent, exponential, Bessel, sinc, and other functions that rarely appear on a chemistry lab bench. The paper proves that the fractional output is correct throughout the reaction, provided the rates are matched, and finds reasonable tolerance to imperfect matching. DNA concatemers offer a possible physical chassis. The larger purpose is to replace bespoke molecular dynamics with a systematic design method. Chemistry learns to read a circuit diagram. |
|
Neural Network Execution Using Nicked DNA and Microfluidics
DNA becomes a manuscript with information written twice. Its nucleotide sequence holds the archival text; small cuts in its backbone provide a rewritable layer of punctuation above it. A real-valued input is encoded by the fraction of molecules nicked at one site, and a neural-network weight by the fraction independently nicked at a second. Molecules bearing both cuts occur with the product of those fractions, turning multiplication into the simple question, “How many pages carry both marks?” Gentle heating exposes a toehold only between paired nicks, allowing strand displacement to release the answer. The paper builds this idea into a proposed microfluidic neural engine whose chambers mix inputs and weights, merge products, and apply DNA seesaw gates as activation functions. It would be slow by electronic standards, but density, parallelism, and biocompatibility are the prize. The wager is that molecular data should learn where it lives, without first being translated back into electricity. |
|
Parallel Pairwise Operations on Data Stored in DNA: Sorting, XOR, Shifting, and Searching
This paper teaches DNA to compute by neighborhood gossip. Each bit occupies a seven-domain cell on a strand, with the position of a nick distinguishing 0 from 1. Carefully chosen instruction strands let adjacent cells recognize one another, expose selected toeholds, and rewrite their values. A single instruction added to the test tube acts everywhere it matches: pairs reading 10 become 01 until the bits are sorted; neighboring values propagate to perform a shift; pairs of 1s cancel to reveal XOR parity; progressively larger blocks assemble themselves into a substring search. Some operations take linearly many chemical rounds, and the practical search loses part of its ideal logarithmic speed, but each round acts across enormous numbers of cells and strands at once. Silicon wins by moving quickly; this scheme proposes winning by making the same slow move almost everywhere. Sorting, parity, motion, and search emerge from molecules peeking next door. |
|
Cascadable Stochastic Logic for DNA Storage
Most molecular logic is a box of bricks with smooth tops: one layer works, then there is nowhere to attach the next. This paper restores the studs. A number is the fraction of double-stranded DNA molecules carrying an exposed toehold. For inputs a and b, the molecules bearing both marks occur at fraction ab. Strand displacement releases a matching strand from that population and uses it to cover toeholds on fresh DNA, leaving fraction 1-ab exposed. The result is a NAND gate whose output has exactly the same molecular shape as its inputs, so gates can snap together. Since NAND is universal, cascades can approximate functions such as e^{-x}. Domain-level simulations keep the concentration error below 0.03 percent, although wet-lab validation remains ahead. The deeper contribution is composability: a clever reaction becomes a material from which larger molecular programs can actually be built. |
|
Stochastic Computation on DNA Strands through Hydroxyl Nicking
Hydroxyl radicals usually vandalize DNA; this work hires them as the punch operator for a molecular player-piano roll. Random, rate-controlled cuts are made along one backbone, and gentle denaturing removes the short pieces caught between nearby cuts, leaving a pattern of exposed gaps. The fraction of exposed bases stores a number between zero and one. Combine two independently punched patterns and only coincident gaps remain exposed, giving multiplication; use complementary covers and gaps exchange roles, giving 1-x. AND and NOT can then be composed into richer functions, including a short polynomial approximation to e^{-x}. This brief proposal remains principally a computational design, with experiments left for future work, but its governing idea is wonderfully physical: damage becomes representation. A ragged DNA backbone carries arithmetic in the statistics of its scars. |
|
Concentration-Based Polynomial Calculations on Nicked DNA
Imagine a deck of molecular punch cards. A value is the fraction of DNA molecules punched, or nicked, at one designated site. Put a second site beside the first and nick it independently; the cards bearing both punches appear with frequency ab, so multiplication is obtained by releasing and counting the strip between the two cuts. Arrange many neighboring pairs and all products of a dot product can be cut loose in parallel, translated into a common strand, and pooled. Competitive strand-displacement reactions scale the terms, while positive and negative pools consume one another until the survivor gives a polynomial’s sign and magnitude. The paper demonstrates this machinery in simulation with an approximation to e^{-x}. Its output cannot yet be written back into the original punch-card format, so the calculator does not chain. Even so, it shows how arithmetic can occur directly on a topological layer of stored DNA. |
|
Computing Mathematical Functions Using DNA via Fractional Coding
A transcendental function is a large score; this paper rearranges it for an orchestra that can play only duets. Each value travels as the ratio of two molecular species, with a bipolar version allowing negative notes. A Maclaurin approximation supplies the melody, Horner’s rule folds it into a cascade, and small multiplication, complemented-multiplication, and mixing units perform the score using only bimolecular reactions. The resulting DNA strand-displacement networks approximate exponential, sine, cosine, logarithm, tanh, and sigmoid functions with low simulated error. The same vocabulary builds a 32-input molecular perceptron whose sigmoid decision agrees with its mathematical counterpart on the simulated test set, although the weighted sum is scaled and no wet-lab classifier is demonstrated. The achievement is one of arrangement: complicated mathematics becomes a sequence of reactions simple enough for DNA to plausibly play. |
|
Chemical Reaction Networks for Computing Polynomials
Earlier chemical calculators hid a polynomial’s coefficients in reaction rates, like storing a recipe in how fast the cook stirs. This paper bottles the coefficients. A number is encoded as the ratio of type-1 molecules to a complementary type-0/type-1 pair. The target polynomial is rewritten in the Bernstein basis, whose coefficients can all be placed between zero and one when the polynomial maps the unit interval to itself. Those coefficients become molecular concentrations; one group of reactions generates the Bernstein terms, and another routes them into the two output species. The paper proves the construction for any such polynomial, supplies encoders and decoders, and maps a cubic example to DNA strand displacement. The price is a chemically awkward reaction involving as many reactants as the polynomial’s degree, a problem later work would dismantle into pairwise steps. Here the foundational move is representational: mathematics is stored in quantities of molecules instead of exquisitely tuned kinetic clocks. |
|
Molecular Computation of Complex Markov Chains with Self-Loop State Transitions
Markov chains are usually maps used to describe molecular motion. This paper folds the map into molecules and lets it walk. Each state becomes a distinct data species, while the concentration of a catalytic control species sets the traffic along one outgoing edge. A data molecule changes identity as it crosses an edge; after the reactions settle, the crowd gathered under each identity gives the chain’s long-term probability distribution. The important refinement is the apparently idle self-loop. Like a traveler choosing the door that leads back into the same room, it changes no location, yet it must compete with the other doors if the probabilities are to remain correct. The construction handles transient states and recurrent classes, and maps a seven-state example to DNA strand-displacement reactions whose simulated steady-state probabilities are within 2 percent of theory. Here chemistry stops being the phenomenon under study and becomes the machine that studies it. |
|
Molecular Sensing and Computing Systems
The world inside a cell speaks in concentrations, while digital logic speaks in bits. This paper builds an interpreter for the border. An analog molecular input between zero and eight nanomolar passes through a hierarchy of comparisons and emerges as a three-bit word. Molecular AND, OR, and XOR gates then add two such words, after which a four-bit digital-to-analog converter weighs the output bits and reconstructs the chemical sum. The entire sense-compute-respond path is mapped to DNA strand displacement and validated through kinetic simulation. Around this central example, the paper develops a larger vocabulary for analog, sampled, and digital molecular signal processing, including several ways to coordinate chemical delay elements. The intended interpreter would live in a biochemical controller, reading protein levels, making a discrete decision, and answering in the language of chemistry. The work is constructive rather than experimental, but it closes a conceptual circuit: molecules can sense their world, reason about it, and return an actionable molecular signal. |
|
Markov Chain Computations Using Molecular Reactions
Instead of asking a computer to replay one gambler’s luck again and again, this paper releases a crowd of molecular gamblers into the same casino. Each data molecule carries the gambler’s current fortune as its molecular identity. Catalytic control molecules encode the odds, steering gamblers one step toward WIN or RUIN without themselves being consumed. When no further play is possible, the relative sizes of the two final crowds reveal the probability of ruin. Stochastic simulation treats each molecule as an individual gambler; mass-action kinetics follows the population as a continuous flow. Both views reproduce the theoretical result, and a DNA strand-displacement implementation computes the ruin probability with less than 1 percent error in simulation. Larger molecular crowds give sharper estimates, just as more trials improve a Monte Carlo calculation. The method generalizes to first-order Markov chains, turning repeated random trials into a population whose chemistry plays every game at once. |
|
Asynchronous Discrete-Time Signal Processing with Molecular Reactions
A conventional signal processor is a railway run by a master timetable. Molecules cannot keep appointments, so this paper replaces the timetable with block signals. Each computation proceeds through four phases, and an “absence indicator” opens the next block only after the molecular species occupying the previous one have disappeared. Values therefore move through delay elements without a global clock and without colliding with the next sample. A systematic synthesis procedure assigns the phases to an arbitrary signal-flow graph, using two molecular species for each delay or output variable. The method is demonstrated on FIR and IIR filters and an eight-point real-valued fast Fourier transform, then mapped to DNA strand-displacement reactions. Simulations show the price of haste: the FFT schedule is faster than the compared synchronous design, but its error rises to roughly 24 percent as leakage accumulates across its 202 reactions. The enduring idea is coordination by completion rather than time: molecular computation advances when the track is clear. |
|
Digital Logic with Molecular Reactions
Every bit in this paper is a molecular tug-of-war. Instead of trusting the fragile presence or absence of one species, a bit is represented by two complementary populations, X_0 and X_1. A bistable reaction network rewards whichever side has the lead until the minority is cleared away, continually restoring a crisp zero or one despite leakage and small perturbations. From this self-correcting bit, the paper constructs AND, OR, NOR, and XOR gates, then adds memory through latches and flip-flops. Larger simulated designs include a four-bit adder, a digit-serial square-root unit, and a linear-feedback shift register that traverses all seven of its nonzero states without accumulating errors from one cycle to the next. The reactions require only coarse agreement among their rates and can be translated into DNA strand-displacement systems, although the validation here remains computational. The deeper achievement is regeneration: chemistry gains the digital habit of making a clean decision at every stage instead of passing yesterday’s uncertainty downstream. |
|
Discrete-Time Signal Processing with DNA
Most chemistry has no memory: it reacts to what is present now. A digital filter needs an echo, a disciplined copy of what arrived one sample ago. This paper gives DNA that echo. Molecular concentrations carry signals; reactions add and scale them, while delay units shuttle each value through paired or color-coded species so that it can meet the next input at the proper moment. One architecture follows two nonoverlapping phases of a chemical oscillator. The other watches for a color’s disappearance and advances itself. With these mechanisms, the paper constructs moving-average and biquad filters and a four-parallel, eight-point real FFT. The networks are mapped to DNA strand displacement and evaluated through kinetic simulations. Synchronous designs are slower but more accurate; for the FFT, synchronization cuts the error from 22 to 7.8 percent while more than doubling the calculation time. The work is conceptual, but its deeper purpose is clear: chemistry acquires a past, allowing it to filter and interpret a changing biochemical world. |
|
Robust Tunable In Vitro Transcriptional Oscillator Networks
A synthetic molecular oscillator can resemble a clock with a fading mainspring: each swing consumes fuel, accumulates waste, and drifts until the motion dies. This paper proposes winding the clock while it runs. It begins with Kim and Winfree’s two-switch transcriptional oscillator, in which RNA activation and inhibition form a negative-feedback loop, and places it in an assumed open microchemostat. Fluorescence measurements reveal the state of each switch; a dynamic-inversion controller compares that state with a desired waveform and injects activator strands to correct the error. The resulting law reduces to familiar proportional-integral feedback, while the reference waveform specifies the oscillation’s amplitude, frequency, and phase. Simulations show two switches tracking perturbed sinusoidal signals with a prescribed phase offset, even when parts of the biochemical model are uncertain. The controller was not experimentally implemented in this study, but the proposal changes the meaning of a molecular clock: its tempo becomes something an engineer can command rather than merely observe. |
|
Rate-Independent Constructs for Chemical Computation
A molecular recipe that encodes its answer in exact reaction speeds is a recipe written for one stove. Change the temperature, volume, or chemistry, and the meal changes with it. This paper rewrites the recipe using only two settings, fast and slow. “Absence indicator” molecules act as readiness tests, allowing each operation to begin only after the species from the preceding step has been consumed. From that device, the paper builds inverters, copiers, incrementers, decrementers, and comparators, then assembles them into loops that perform multiplication, exponentiation, integer powers, and base-two logarithms. Gillespie simulations show errors shrinking as the separation between the two rate classes grows, with a 10,000-to-one separation producing nearly exact results across most examples. The reactions remain abstract rather than experimentally realized, and some constructions are sprawling, but they establish the vocabulary for a chemical compiler. Reaction rates determine how long dinner takes; they no longer determine what arrives on the plate. |
|
Synchronous Sequential Computation with Molecular Reactions
A sequential machine needs a heartbeat, separate beats on which to compute and remember. This paper builds that heartbeat from chemistry. A four-color reaction network cycles through red, green, blue, and yellow concentrations, with positive feedback sharpening the transitions. Two nonadjacent colors, red and blue, become the alternating phases of a molecular clock. Each memory element is represented by a pair of species: on the blue beat, a stored concentration is released, transformed, and placed in the first stage of the next memory element; on the red beat, that result is committed for the following cycle. The scheme drives a three-bit binary counter and a two-parallel, four-point FFT in mass-action simulations. Slight overlap between clock phases causes leakage that accumulates in the counter, although increasing the separation between fast and slow reactions sharply reduces the error. DNA strand displacement is proposed as the eventual chassis. The paper’s contribution is a temporal spine: reactions cease to be an undifferentiated flurry and begin to compute in measured beats. |
|
Asynchronous Computation with Molecular Reactions
A clockless molecular program is a relay race with no starting gun. Each handoff begins when an absence indicator reports that the previous runner has left the exchange zone. This paper turns a signal-processing data-flow graph into such a relay by assigning every edge a transfer step. Once all source species for one step have disappeared, the corresponding absence molecule accumulates and releases the next set of transfers. Cycles introduce a subtle hazard: a species asked to send a value in one step and receive a new value immediately afterward can suppress its own completion signal, freezing the race. The method detects this conflict and inserts an intermediate molecular node, giving the handoff an extra exchange zone. A four-tap FIR filter is scheduled in six steps as a worked example. This early construction is a blueprint, without kinetic simulation or a completed DNA mapping, but it isolates the central problem of asynchronous chemistry: deciding safely when one event is over. The absence of a molecule becomes the message that moves computation forward. |
|
Binary Counting with Chemical Reactions
A binary counter is an odometer: each event turns the smallest wheel, and a completed revolution nudges the wheel to its left. This paper rebuilds that mechanism from molecules. The presence or absence of three molecular types records a three-bit number, while each injection of a trigger species asks the counter to advance once. “Prereactant” molecules carry the increment toward more significant bits; absence indicators decide whether a bit should be filled or the carry passed onward. Because all the reactions would otherwise fire at once, a red-green-blue chemical oscillator serves as the escapement, opening the sequence one phase at a time. Twenty-four abstract reactions produce the full cycle from 000 through 111 and back to zero, remaining stable through repeated counts in mass-action simulations. The deeper possibility is an event counter that lives where the events occur, allowing cell divisions or biochemical episodes to leave a molecular history. |
|
Writing and Compiling Code into Biochemistry
Molecular circuits are ordinarily written one reaction at a time, as if every program had to be composed directly in machine code. This paper introduces a translator. Its prototype compiler, VERB, accepts a Verilog-like description in which protein quantities behave as registers, then turns assignments, arithmetic, and loops into an abstract chemical reaction network. Stoichiometry supplies addition and scaling; repeated transfers implement multiplication, exponentiation, logarithms, and powers; a biochemical clock keeps the stages in order. A second translation step can map those generic reactions onto a physical library such as DNA strand displacement. The paper compiles a moving-average filter whose stochastic simulation cleans up a noisy sinusoid, along with a deserializer, vector-matrix multiplier, integrator, and differentiator. The chemistry remains a design rather than an experiment, but the abstraction is the contribution: a biochemical engineer can state what a system should do before deciding which molecules must do it. |
|
A truth table is a passport photograph: it shows a biochemical gate holding still, not whether it can keep its footing when the world moves. This paper supplies the movie camera. Gillespie’s stochastic simulation normally seals a reaction network after its initial state; stochastic transient analysis admits external pulses, piecewise-linear ramps, and sinusoidal signals, either forcing a molecular population or injecting molecules into it, with threshold events able to switch those inputs on and off. A time-binned data structure averages many stochastic trials without memory growing with the number of runs. The method probes a Lotka reaction network and then drives biochemical inverter, AND, NAND, OR, and XOR models through changing inputs. The XOR gate is the revealing test: it produces the right logical response at a leisurely tempo but cannot rise fully when the inputs switch too quickly. A circuit that knows the correct answer may still be too slow to say it. |
|
Module Locking in Biochemical Synthesis
A reaction network without synchronization is a workshop in which every machine starts as soon as material touches it. This paper puts locks on the machines. Each computational module receives a molecular key; a slowly appearing “keysmith” can forge that key only when indicator species show that earlier work has finished. The key opens the module’s first reaction, then disappears so the operation can be locked again. The mechanism coordinates phases within iterative modules and handoffs between modules, replacing a staircase of exquisitely separated reaction speeds with the coarser distinction between fast and slow. The price is machinery: a four-reaction multiplier grows to twenty-six reactions. At a comparable overall range of rates, however, locking improves its accuracy by more than eightyfold and sharply reduces errors in probabilistic modules. The deeper result is biochemical concurrency control: correctness comes from permission to proceed rather than from hoping one reaction outruns another. |
|
Synthesizing Stochasticity in Biochemical Systems
Cells already roll dice; this paper shows how to load them. Competing initiation reactions enter a molecular race whose odds are set by their rates and the starting quantities of input species. The first catalyst across the line reinforces itself, consumes its rivals’ fuel, and purges competing catalysts, turning a fleeting random event into a stable outcome. A deterministic front end computes how the odds should vary with the inputs, using modules for linear, exponential, logarithmic, and power-law dependence. In stochastic simulations, a compact network of nineteen reactions and seventeen molecular types reproduces the input-dependent lysis-versus-lysogeny choice of a lambda-phage model containing 117 reactions and 61 types. The construction is abstract, but it makes a lasting conceptual move: biochemical noise becomes an instruction, the chemistry’s way of making a programmable choice. |
Computing about Molecules
|
Evaluating NetMHCpan Performance on Non-European HLA Alleles Not Present in Training Data
A biased guest list does not always produce a blind doorman. NetMHCpan’s training data heavily favors HLA alleles common in European populations, leaving many Asian and Pacific Islander alleles outside the velvet rope. Poor peptide-binding predictions for unseen alleles seemed the likely consequence. Tests on seven novel class I alleles and one class II allele found surprisingly little practical loss. A map of HLA sequence space helps explain why: the named alleles are missing, yet their biochemical neighborhoods are often represented. When the authors mutate HLA residues one by one, the model reacts most strongly at positions that physically touch the peptide, evidence that it has learned some of the binding pocket’s grammar instead of merely memorizing allele names. The sample is small, and the inequity in experimental data remains. The sharper lesson is methodological: audit who is absent, then test what the absence actually breaks. |
|
A dog that did not bark is evidence only once you know the dog can bark. Omicron’s spike carries enough mutations to slip past most neutralizing antibodies, yet T cell responses to it hold up—reassuring, but hard to interpret, since “no loss detected” may only mean the instrument was not looking. This paper runs the natural variants and the vaccine spikes through NetMHCpan-4.1 and NetMHCiipan-4.0 and finds their Class I and Class II antigen repertoires essentially unchanged: the mutations swap which peptides are presented without reducing how many. Then comes the control. The authors engineer two hundred “evader” spikes, each allotted exactly BA.1’s budget of thirty-six mutations but spent deliberately, on anchor residues, substituting amino acids that the relevant binding pocket refuses. The evaders collapse antigenicity across nearly every HLA tested and separate cleanly from the natural variants, while Omicron sits comfortably among them. Evasion of the T cell pathway was thus within reach of the virus’s mutation budget; Omicron simply did not spend it that way. The paper’s durable move is the control itself: to give a negative result teeth, build the positive result that should have happened. |
|
Hydrophobicity Identifies False Positives and False Negatives in Peptide-MHC Binding
A peptide-binding predictor can ace the exam and still fail the chemistry lab. NetMHC-4.0 and NetMHCpan-4.1 both earn impressive aggregate scores, so this paper dips their answers in a biochemical litmus test: hydrophobicity. HLA-A2 favors hydrophobic anchors, HLA-B27 a hydrophilic arginine, and HLA-B8 a more balanced motif. Across training peptides and a sample of the human proteome, NetMHC-4.0 predicts immunopeptidomes for A2 and B27 that are too hydrophobic; the usual performance metrics conceal a mixture of hydrophobic false positives and overlooked hydrophilic binders. NetMHCpan-4.1 fares better, plausibly because its larger collection of eluted-ligand data captures more of the antigen-presentation pathway than binding-affinity measurements alone. The paper’s deeper contribution is a method of interrogation: when an artificial intelligence makes biological predictions, ask whether its mistakes obey the physics and chemistry of the world in which those predictions must live. |
|
Gene Regulatory Network Modeling Using Literature-Curated and High-Throughput Data
The scientific literature and a microarray are two imperfect witnesses. The literature remembers who activates or inhibits whom, but seldom knows the strength of the interaction; expression data records what every gene is doing, but not who made it do so. This paper brings the witnesses together. Literature-curated signs and absent edges constrain a locally linear ordinary differential equation, steady-state expression measurements determine its weights, sparsity prevents the reconstruction from inventing a biological conspiracy in which everything regulates everything else, and linear-matrix inequalities insist that the resulting network is dynamically stable. The framework also relaxes the impractical assumption that an experiment perturbs exactly one gene at a time, allowing the unknown effects of realistic treatments to be inferred alongside the network. After tests on synthetic data, it reconstructs a 42-protein network from patients with Plasmodium falciparum and P. vivax malaria. A pathway diagram is ordinarily a map of reported roads; this work adds traffic, direction, and a guarantee that the modeled city will not fly apart. |
|
Characterizing the Memory of the GAL Regulatory Network in Saccharomyces cerevisiae
A cellular memory is a marble resting in a landscape. A pulse of galactose can push yeast from an “off” valley into an “on” valley; whether the cell remembers the sugar depends on which ridge it crossed and where it comes to rest after the sugar disappears. This paper gives that landscape a 25-state dynamical model, following Gal4p, Gal80p, Gal3p, galactose transport, gene binding, growth, and substrate consumption. Two added paths—a weak direct interaction between Gal3p and Gal80p and non-facilitated galactose diffusion—allow the model to reproduce behaviors that simpler models miss, including activation caused by Gal3p overproduction even without galactose and the observed behavior of transport mutants. Lyapunov functions and linear-matrix inequalities then carve out a guaranteed portion of each equilibrium’s basin of attraction and show how feedback through galactose input could shepherd the system toward a chosen state. Memory emerges not as a molecule stored on a shelf, but as the shape that feedback gives to the ground beneath the cell. |
Computing with Random Bit Streams
|
Maximizing Memory-Level Parallelism via Integrated Stochastic Logic-in-Memory Architectures
Conventional stochastic computing watches a film one frame at a time: an N-bit stream ordinarily takes N cycles to pass through a gate. This architecture unrolls the whole film across an MTJ memory array and examines every frame at once. Binary operands are converted in place into deterministic, low-discrepancy bit bundles; logic-in-memory units then apply the same operation across all bundle positions simultaneously. Multiplication and minimum take one cycle, addition and subtraction two, and combinational approximations of transcendental functions only a few. Results may remain stochastic for the next stage or be counted back into binary form without leaving the memory fabric. The bargain is explicit: spatial width and higher instantaneous power are exchanged for the disappearance of serial latency. That bargain yields 22- to 64-fold speedups over serial stochastic execution, and a parallel tone-mapping pipeline processes images about 54 times faster. The memory array’s width, usually passive real estate, becomes the computation’s main engine. |
|
MITRA teaches memory to draw curves by walking through a maze. Incoming stochastic bits guide a finite-state machine through a one- or two-dimensional grid, and the long-run occupancy of its states traces sine, cosine, logarithm, exponential, sigmoid, and other nonlinear functions. Magnetic tunnel junctions serve as both the maze’s rooms and its memory: they retain the current state while nearby FinFET logic evaluates the next move, keeping the entire walk inside the array. Rearranging state boundaries and stored coefficients reconfigures the same fabric for different functions. Because each step touches only the room being left and the room being entered, fine-grained power gating can darken the rest of the maze, cutting power by as much as 60.9 percent. The paper also lets a neural network train with the maze’s imperfections in view, recovering optical-digit accuracy from 88.7 to roughly 97 percent. Approximation error becomes terrain the learner can navigate. |
|
Breaking New Ground: Division Directly in Memory
Division is arithmetic’s habitual troublemaker: multiplication fits neatly into hardware, while division usually demands an extended ritual of guesses, shifts, subtractions, and corrections. This work sneaks past that machinery by representing numbers as stochastic streams. A feedback-based multiplexer updates or recirculates each quotient bit according to the denominator stream, reducing the divider to two AND operations and an OR. Those gates are then mapped into magnetic-tunnel-junction and FinFET logic-in-memory cells. The alternating preparation and evaluation phases of the memory provide the needed history, allowing a clocking trick to dispense with the usual flip-flop. Longer streams progressively sharpen the answer, reaching a mean error of 1.61 percent at 1,024 bits; an extended evaluation also finds stable outputs under device variation and demonstrates low-light image enhancement with Retinex division. Long division becomes a tiny echo inside memory: each bit listens to the previous one, and the quotient gradually emerges. |
|
A Scalable, Deterministic Approach to Stochastic Computing
Exact deterministic stochastic multiplication throws a banquet at which every bit in one stream must meet every bit in the other. The result is impeccable, but the guest list squares at every layer, making a large circuit impossible to host. This work replaces the banquet with carefully arranged speed dating. It shortens each operand to the square root of the desired stream length, records the discarded low-order bits as small debts, and uses two auxiliary multiplications to decide where compensating zeros should be flipped to ones. The output therefore remains the same length from one stage to the next, while its error is bounded by two bits per logic level regardless of stream length. In experiments, the method approaches the accuracy of Sobol-sequence computing with substantially less hardware. The important achievement is composability: deterministic bit-stream arithmetic can finally be chained into deep computations without the streams breeding uncontrollably at every gate. |
|
Performing Stochastic Computation Deterministically
After decades spent devising better sources of randomness, this paper fires the croupier. Its central observation is that stochastic logic does not fundamentally need chance; it needs a uniform representation and a schedule that lets every bit of one operand meet every bit of another. Three deterministic schedules—relatively prime stream lengths, rotation, and clock division—make those meetings exact, preserving the tiny arithmetic gates and soft-error tolerance while eliminating statistical fluctuations. The reduction in latency is exponential: a random stream may require more than 2^{20} samples to resolve a ten-bit value, whereas its deterministic uniform counterpart needs only 2^{10}. Exact unary results do grow unwieldy through many levels of logic, so the paper also develops Sobol-sequence variants that can be stopped early and still give unusually good approximations; in experiments, their truncated multiplication error is orders of magnitude below conventional stochastic sampling. What had looked like computing with probability is revealed as computing by convolution. Randomness was stage machinery, not the plot. |
|
Synthesis of Polynomial Functions
What language can a circuit made from ordinary Boolean gates speak when its inputs are probabilities? This chapter supplies both the grammar and the dictionary. It shows that every combinational circuit operating on independent stochastic streams computes a polynomial in the input probabilities, then proves the remarkable converse: essentially every polynomial that behaves like a probability can be translated back into such a circuit. Bernstein polynomials provide the phrasebook. By raising the degree, the coefficients can be coaxed into the unit interval, where stochastic streams can represent them; a generalized multiplexer then assembles the desired function by counting how many input bits are one. Continuous nonpolynomial functions can be approximated through the same construction. Earlier work offered recipes for particular functions. Here the scattered recipes become a theory, drawing the boundary of everything combinational stochastic logic can say and showing how to say any sentence inside it. |
|
Deterministic Approaches to Bitstream Computing
This chapter takes stochastic computing apart to see whether chance is really holding it together. It is not. Random streams merely arrange repeated encounters among bits; relatively prime lengths, rotation, and clock division can schedule every necessary encounter exactly, replacing statistical sampling with an orderly convolution. The familiar tiny gates remain, along with their tolerance of bit flips, while random-number generators disappear and latency falls exponentially. The chapter then turns the representation ninety degrees. A number need not occupy a pattern of bits in space; it can occupy a fraction of a pulse in time. Signals with carefully chosen periods flow through the same simple gates to perform arithmetic, potentially beginning directly with an analog quantity and avoiding much of the conversion machinery surrounding conventional digital computation. The chapter is therefore less a summary than a change of viewpoint: stochastic logic’s real gift was never randomness, but the freedom to encode magnitude as extent—and extent may be measured in bits, motion, or time. |
|
A Survey of Computation-Driven Data Encoding
This survey treats a number representation as the gearbox of a computation: the right gearing can make a hard operation almost effortless. Binary radix notation packs numbers into very few bits, then pays for that thrift with elaborate arithmetic and an especially precious most-significant bit. Stochastic encoding unspools each number into a long, disorderly ribbon, allowing multiplication and other functions to collapse into tiny, fault-tolerant circuits. Between these poles lie deterministic unary streams, low-discrepancy sequences, sign-magnitude schemes, unbounded ratio encodings, and integral stochastic streams, each moving cost among space, time, precision, and hardware. The deeper proposal is to stop treating binary as the box in which every computation must arrive. An encoding should be cut to fit the operation, the device, and the amount of error the application can tolerate. Sometimes the shortest description of a number produces the longest route to its answer. |
|
Energy-Efficient Pulse-Based Convolution Engine for Near-Sensor Processing
A sensor already speaks the language of time, yet conventional hardware makes it translate every observation into binary before anyone will listen. This work lets the first convolutional layer meet the sensor in its native tongue. Pixel values and weights become pulse widths at two inharmonic frequencies; an AND gate multiplies their duty cycles, while an active integrator pours all the resulting currents into a capacitor and thereby performs accumulation. Positive and negative weights travel through separate engines and meet again at a differential amplifier. The design avoids the costly analog-to-digital and analog-to-stochastic converters that burden earlier near-sensor engines, and HSPICE simulation with 45-nanometer synthesis shows substantial savings in area and energy over binary and stochastic alternatives. Its mixed-signal nature introduces small errors and a limited linear range, but neural networks can tolerate—and sometimes already impose—the resulting clipping. Instead of hauling raw sensor data into the digital world, the computation walks out to the sensor and listens at the source. |
|
Low-Cost Sorting Network Circuits Using Unary Processing
When numbers are represented as bars of light, comparison becomes geometry: the overlap of two bars is the shorter one, and their union is the longer. In unary logic, an AND gate therefore computes the minimum and an OR gate the maximum, collapsing a conventional compare-and-swap unit—with its multibit comparator and two multiplexers—into two gates whose size does not grow with numerical precision. Thread those tiny units through a bitonic sorting network and the savings compound: complete networks use as much as 92 percent less area and power than binary implementations, while remaining strikingly tolerant of bit flips. Serial unary streams impose a long wait, so the paper also lets the bars exist literally as pulse widths. Near a sensor, one time-encoded pulse can pass through the entire network without first taking the expensive detour through binary conversion. Median-filter case studies show that this version can beat binary designs in latency and energy with only a small loss of accuracy. Sorting, usually a contest among numbers, has been recast as the simple act of measuring shadows. |
|
Time-Encoded Values for Highly Efficient Stochastic Circuits
Instead of repeatedly shuffling a deck of random bits, this paper builds a set of gears. A value becomes the duty cycle of a periodic pulse, and signals are assigned periods with relatively prime lengths; as the gears turn, every relevant alignment appears by the time they reach their least-common-multiple rendezvous. Simple gates can then perform the usual stochastic operations without pseudorandom generators or long, noisy streams. Correlation becomes useful too: aligned pulses of the same period let a single XOR gate compute an absolute difference. Cheap mixed-signal circuitry—an oscillator, ramp, and comparator—creates the pulses directly from analog values, removing the conversion hardware that often consumes most of a stochastic circuit. In edge detection and gamma correction, this clockwork representation cuts latency by as much as 99 percent and energy by 98 percent relative to conventional stochastic designs, while retaining their small computational core and graceful response to faults. Randomness has been replaced by choreography: not every arrangement is sampled by chance; every necessary arrangement is scheduled. |
|
Unary computation is an excellent tally keeper with an unfortunate habit of using one impossibly long wall. This paper moves the tally marks into a building. Within each room, bits remain equally weighted and easy to process; successive rooms are weighted by increasing powers of the base, as digits are in an ordinary positional number. With k streams of length n, the representation holds n^k distinct values using only nk bits, rather than the n^k-bit wall required by plain unary encoding. Addition still works largely by gathering marks, multiplication still relies on simple AND operations and convolution, and carry units move each completed group upstairs. The result cuts multiplication time from n^{2k} to kn^2, exchanging a modest amount of hardware for an exponential reduction in latency. Some of unary’s fault tolerance is surrendered because damage on an upper floor matters more, though far less than a flipped binary most-significant bit. The scheme occupies a useful middle floor between binary’s cramped efficiency and unary’s sprawling simplicity. |
|
Computing Polynomials with Positive Coefficients Using Stochastic Logic by Double-NAND Expansion
A polynomial usually arrives as a row of terms demanding multipliers and adders. This paper folds that row into a set of algebraic nesting dolls: each layer has the form “one minus a product,” exactly the operation performed by a NAND gate on stochastic streams. Two NANDs add each new term, so a degree-n polynomial with nonnegative coefficients summing to at most one requires no more than 2n of them. The construction is a stochastic cousin of Horner’s rule, with complementary probabilities doing the work that explicit addition would ordinarily perform. Truncated Maclaurin series then bring functions such as e^{x-1}, \sec x-1, and \cosh x-1 into the same cascade. Against multiplexer trees, Bernstein constructions, finite-state machines, and earlier factorizations, the double-NAND circuits generally offer a shorter path, fewer resources, and equal or better accuracy. Its real contribution is algebraic carpentry: instead of inventing more elaborate hardware for a formula, refold the formula until the cheapest available gate fits every joint. |
|
Polysynchronous Clocking: Exploiting the Skew Tolerance of Stochastic Circuits
Ordinary digital circuits march to a single drum, and distributing that beat consumes an astonishing amount of machinery. Stochastic circuits care less about the downbeat than about how long each note is held: because a value is a fraction of time, small disagreements about when bits begin and end wash out in the average. This paper turns that tolerance into “polysynchronous” clocking. One design replaces the global clock tree with tiny local ring oscillators; another keeps a global clock but relaxes its timing so aggressively that it can be made smaller and run faster. Neither needs the handshakes and synchronizers normally used between clock domains. Across edge detection, median filtering, and image segmentation, the untidy clocks preserve both accuracy and fault tolerance; in a large edge-detection array, they permit up to twelve times the clock rate while reducing area by 39 percent and energy by 23 percent. The circuit ceases to be a regiment and becomes an ensemble: every player keeps time locally, yet the piece still comes out right. |
|
A Reconfigurable Architecture with Sequential Logic-Based Stochastic Computing
Here a finite-state machine becomes a loom. Incoming random bits tug its state back and forth; the fraction of time spent in each state forms a set of threads, and programmable output weights weave those threads into a desired mathematical function. Markov-chain analysis supplies the equilibrium distribution of the states, after which quadratic optimization chooses the weights that best approximate the target. Changing those weights reprograms the same hardware to compute exponentials, hyperbolic tangents, Gaussian curves, high-order polynomials, or functions with several inputs; changing the machine’s topology supplies still more shapes. This sequential architecture replaces the crowd of random-number generators and arithmetic units required by the earlier Bernstein-polynomial design with one small wandering automaton. For comparable accuracy, it reduces area by as much as 30 percent and energy by 40 percent while running faster, and it retains stochastic logic’s composure when inputs or internal states are corrupted. The paper turns an FSM from a device that follows a fixed script into a compact repertory company: alter a few cues, and the same actors perform a different play. |
|
Synthesis of Correlated Bit Streams for Stochastic Computing
A circuit tested only with independent streams is like an airplane tested only in still air. Real sensors often rise and fall together, and those crosswinds of correlation can push stochastic arithmetic far from its intended answer. This paper builds a weather machine for such circuits: specify the value of each stream and the desired correlations among them, and a hierarchy of conditional probabilities generates the corresponding bits. The construction begins with independent pseudorandom sources, produces one stream at a time, and extends from pairs to triples, where pairwise correlations alone no longer suffice and a genuinely three-way interaction must also be prescribed. The same analysis predicts how these relationships alter the means and variances of stochastic gates in both unipolar and bipolar representations. Simulations reproduce the requested statistics, while the added circuitry remains modest—about 9 percent area overhead for two correlated streams and 21 percent for three. Correlation becomes reproducible laboratory weather: difficult to avoid in the world, but now possible to summon, measure, and design against. |
|
Effect of Bit-Level Correlation in Stochastic Computing
Two streams may contain exactly the same proportions of ones and still tell a gate different stories, depending on whether their bits arrive separately or arm in arm. This paper makes that hidden choreography explicit. Using a correlation coefficient, it derives the mean and variance produced by the basic stochastic gates—AND, OR, XOR, XNOR, and the multiplexer—and shows precisely how correlation bends their arithmetic. It also identifies which degrees of correlation are actually possible for given input values and constructs streams with a prescribed relationship by generating one bit conditionally on the other. The larger lesson is that a stochastic number has more structure than its population of ones: the alignment between streams acts like a second, usually invisible operand. By extending the analysis to reconvergent signals in two-level circuits, the work turns correlation from an unruly source of error into something a designer can measure, propagate, and eventually exploit. |
|
Computation on Stochastic Bit Streams: Digital Image Processing Case Studies
A stochastic image is pointillist: damage a few dots and the picture scarcely changes. A binary image is more like stained glass, where one broken, high-order pane can alter an entire region. This paper puts that contrast to work in five substantial image-processing tasks—edge detection, median filtering, contrast stretching, frame differencing, and kernel-density segmentation—showing that the little gates developed for stochastic arithmetic can be assembled into a surprisingly capable darkroom. The resulting circuits generally preserve image quality while using far less logic; the kernel-density estimator, the most complex case, falls from roughly 400,000 to 1,500 equivalent NAND gates at its computational core. Their resilience is just as striking: when faults corrupt 30 percent of the bits, the stochastic version’s error rises only slightly, while its binary counterpart deteriorates dramatically. The cost is time, since an image must emerge from a stream rather than a word. Yet as the algorithm grows more intricate, that slow exposure increasingly pays for itself in compactness and durability. |
|
Logical Computation on Stochastic Bit Streams with Linear Finite-State Machines
A combinational gate is an amnesiac: every coin flip arrives without a past, restricting stochastic circuits largely to polynomial arithmetic. Give the circuit a little memory, however, and a far richer mathematics appears. In these linear finite-state machines, the input stream nudges a state back and forth along a rail; its bias determines where the state spends its time, and the labels painted on different portions of the rail turn that stationary distribution into functions such as tanh and exponentiation. Earlier work had discovered these remarkable machines empirically. This paper explains why they work, derives the governing symmetries, and adds constructions for absolute value and exponentiation of an absolute value, useful in image processing and density estimation. The resulting circuits compare favorably with conventional arithmetic at modest precision and remain remarkably calm under bit flips. The central insight is almost mechanical: memory supplies nonlinearity, and a complicated function can emerge from nothing more elaborate than a bead wandering on a wire. |
|
IIR Filters Using Stochastic Arithmetic
A sigma–delta converter speaks in a rapid Morse code of single bits. Conventional signal-processing hardware pauses to translate that stream into multibit words, filters the words, and eventually translates them back. This paper listens in Morse. Its stochastic integrator uses an up/down counter to accumulate the difference between two bit streams, then compares the counter state with a random value to emit a new stream; a z-transform analysis shows that this humble mechanism really does behave as a discrete-time integrator. With parameters controlling its gain and resolution, these integrators form first- and second-order low-pass IIR filters that operate directly on oversampled sigma–delta data, eliminating the surrounding decimation and interpolation machinery. The resulting designs occupy a fraction of the area of comparable conventional filters, including a treble-cut audio example, though their pole locations become entangled with precision and their noise demands further study. The broader contribution is architectural: sometimes the cheapest representation conversion is the one never performed. |
|
Stochastic Functions Using Sequential Logic
Once finite-state machines had been shown to compute a few striking functions, the next question was whether they could be designed rather than divined. This paper provides a recipe. It first sketches the desired function with a Taylor series, folds that polynomial into a compact rational approximation, and then realizes the numerator and denominator as the equilibrium behavior of a reversible Markov chain. Groups of states supply the denominator’s coefficients; selected, weighted states supply the numerator’s. Synthesizing a function thus becomes a peculiar kind of town planning: build just enough neighborhoods, connect them with simple streets, and let the long-run distribution of traffic draw the desired curve. The method produces small machines for a broad collection of algebraic and transcendental functions, including sine, cosine, tanh, and exponentiation, with fewer states than earlier fixed-form constructions. More important than any one function is the bridge it builds from approximation theory to hardware: Taylor writes the sketch, Padé compresses it, and a Markov chain brings it to life. |
|
Stochastic computing’s usual bargain is tiny hardware paid for with very long bit streams. Numerical integration quietly renegotiates the deal. A Riemann sum already gathers many function evaluations, so each evaluation need not speak with great precision: one noisy bit may be a terrible estimate of a single value, yet thousands of such bits poured into the same bucket give an accurate integral. The analysis shows that error depends chiefly on the total number of samples, LM—stream length times integration points—allowing many points to substitute for long streams and turning the sum itself into a noise filter. An architecture sweeps stochastically across the integration interval, evaluates a Bernstein-polynomial approximation to the integrand, and counts the resulting ones. Experiments confirm the mathematics and produce the unusual double victory of smaller area and shorter delay. Here the integral’s breadth, normally its computational burden, becomes its shelter from randomness: a broad basin can measure rainfall one drop at a time. |
|
Transforming Probabilities with Combinational Logic
A probabilistic circuit needs many shades of randomness, while physical sources usually come in only a few fixed colors. This paper turns combinational logic into a mixing palette. If independent sources with biases 0.4 and 0.5 may be copied, AND gates and inverters can generate any terminating decimal probability; factorization and circuit balancing keep the resulting constructions shallow. More broadly, for every base n, a single carefully chosen source probability can generate any fraction whose denominator is a power of n. When the available sources are fixed and cannot be duplicated, the problem becomes one of selecting rows from a probability-weighted truth table: a binary optimization gives the closest possible target, while a fast greedy construction provides a bounded approximation. When the sources may be chosen but used only once, the paper derives the optimal biases, spacing all reachable output probabilities evenly. This revives the old idea of a “probability transformer” as a modern logic-synthesis problem. A few raw biases become a complete palette of odds for the computations downstream. |
|
An Architecture for Fault-Tolerant Computation with Stochastic Logic
Most fault-tolerant systems build armor around a conventional computation. The ReSC architecture puts a shock absorber inside the number representation itself. A Randomizer turns inputs and stored coefficients into independent stochastic streams; a reconfigurable Bernstein-polynomial unit processes them; a counter converts the output stream back into an ordinary value. Loading new coefficients changes the function, allowing the same datapath to approximate gamma correction, color-space transformations, geometric operations, and other continuous computations. The paper separates its uncertainty into three intelligible pieces—functional approximation, quantization, and random fluctuation—each with its own accuracy knob. Across ten image-processing benchmarks, the complete FPGA architecture uses about forty percent fewer lookup tables on average than conventional implementations. With ten percent of the bits deliberately flipped, conventional color-processing circuits produce errors exceeding twenty percent in roughly thirty-seven percent of pixels; ReSC produces none that large. Its streams are long and its answers imprecise, but the architecture’s wager is compelling: many tiny errors are safer than one important bit. |
|
The Synthesis of Stochastic Circuits for Nanoscale Computation
Self-assembled nanowires arrive like a loom whose threads have crossed themselves, and this paper makes the crossings part of the pattern. A real value is carried by a wide bundle as the fraction of wires holding one. Random crossbar connections shuffle pairs so that banks of AND gates perform multiplication, while “bundleplexers” form weighted mixtures. The synthesis procedure translates an ordinary Boolean netlist into multiplicative binary moment diagrams, separates its positive and negative polynomial contributions, implements each with these shuffled components, and reunites them at a counter. Trials on fifteen benchmark circuits make bundle width an accuracy knob: wider bundles consume more area but drive the error toward zero. The construction is conceptual and assumes a particular nearly one-to-one random crossbar fabric, yet its deeper inversion matters. Manufacturing disorder becomes the routing resource that the computation expects. |
|
Two-Level Logic Synthesis for Probabilistic Computation
Classical logic synthesis treats a truth table as sacred: the circuit must preserve exactly which input combinations produce a one. A probabilistic circuit driven by independent fair bits cares only how many do. To generate m/2^n, any m minterms will serve, turning the Karnaugh map from a portrait into a seating chart: move the guests around until they fit at the fewest tables. The binary expansion of m supplies a quick arrangement of disjoint cubes, while overlapping cubes can sometimes do even better through inclusion–exclusion. To judge how close this construction comes to optimal, the paper recasts the unavoidable overlaps as an “optimal subtraction” problem and solves it by dynamic programming. The deeper lesson is one of semantic thrift: when the promised result is a measure rather than a membership list, the identities of the minterms are disposable—and that freedom can buy a much smaller circuit. |
|
Estimation and Optimization of Reliability of Noisy Digital Circuits
A faulty gate merely drops a rumor into a circuit; reliability depends on whether that rumor reaches the exits. This paper attaches a probabilistic XOR “coin” to every gate, builds a faulty twin of the original circuit, and asks how often the twins disagree. The hard part is reconvergence: two paths carrying related errors may reinforce or cancel one another, defeating naïve probability propagation. The proposed hybrid method examines these knots exactly with algebraic decision diagrams while treating the simpler stretches between them with faster correlation estimates. It comes within 3.5 percent of Monte Carlo fault injection while running about 56 times faster, making reliability estimation cheap enough to sit inside a synthesis loop. That loop then rewires the circuit without changing its Boolean function, replacing vulnerable routes with more reliable ones and sometimes deleting gates in the process. Benchmarks gain roughly 10 percent in reliability while shrinking by 6.9 percent. Reliability is revealed as a property of the roads, not merely the sturdiness of the bricks. |
|
The Synthesis of Stochastic Logic to Perform Multivariate Polynomial Arithmetic
The earlier Bernstein construction traced a single curve; this paper stretches the same mathematical net across surfaces and higher-dimensional volumes. Each variable receives its own collection of independent stochastic copies, and a decoder counts how many ones appear in each collection. Those counts jointly address a multidimensional multiplexer whose data inputs encode the Bernstein coefficients. Degree elevation eventually brings the coefficients of any polynomial lying strictly inside the unit interval into the range that probabilities can represent; simple transformations extend the method to other finite input and output ranges. The paper demonstrates the machinery on the real and imaginary parts of Butterworth polynomials, where two variables describe complex frequency. At equal nominal resolution, the resulting circuits have area-delay products comparable to binary-radix implementations, but respond much more gently to bit flips. The contribution is a route from one-dimensional stochastic arithmetic to the coupled computations required by filters, models, and other systems whose answer depends on several quantities at once. |
|
The Synthesis of Robust Polynomial Arithmetic with Stochastic Logic
A conventional binary number is a tower whose upper stones carry enormous weight: flip the most significant bit and the value lurches. A stochastic number is a jar of black and white beads; its value is the fraction that are black, so one mistaken bead barely moves the average. This paper builds a general method for polynomial arithmetic from that idea. It first shows that any combinational circuit driven by independent random bits computes a particular multivariate polynomial in their probabilities. It then runs the argument backward, converting a target univariate polynomial into Bernstein form and raising its degree until every coefficient can itself be represented as a probability. A population counter and multiplexer perform the resulting computation. Experiments on elementary-function approximations show area-delay costs comparable to conventional arithmetic, while errors from corrupted inputs grow far more gently. Stochastic sampling introduces a modest blur even in a quiet circuit, but no individual bit holds royal power. What had been a collection of clever stochastic gate tricks becomes a synthesis methodology. |
Computing with Emerging Technology
|
There are two principal ways to tip the tiny magnetic compass needle inside SC-CRAM: push current through the tunnel barrier with spin-transfer torque, or sweep it along a channel beneath the magnet with spin-orbit torque. This study asks which route wins after the physics is made to pay the full architectural bill. Using laboratory devices, commercial technology, and projected devices, it compares energy and tolerance to variation across six arithmetic functions and four neuromorphic applications. Present-day STT cells consume less energy because today’s SOT magnetic pillars are too resistive, forcing the logic step to shoulder nearly the whole cost. Yet the projected race reverses when the pillar’s resistance-area product is lowered, its resistance is matched to the SOT channel, and a high tunneling-magnetoresistance ratio widens the safe logic window. Under those conditions, SOT becomes especially attractive for NAND-heavy workloads. The paper is less a horse race than a road map: it identifies the material improvements that turn SOT’s wider lane into actual speed. |
|
Random-bit generation is ordinarily the mint of a stochastic computer: a large, expensive establishment that stamps probabilistic coins before shipping them elsewhere to be spent. SC-CRAM lets each magnetic memory cell mint and spend its own coin. During a repeating reset–perturb–logic–read cycle, the thermal uncertainty of a magnetic tunnel junction generates a bit with a tunable probability, and the same cells immediately process it using in-memory logic. Multiplication, division, square root, and other functions can therefore be performed without separate random-number hardware or continual traffic between memory and computation. Applied to image thresholding, object location, heart-risk inference, and kernel-density estimation, the scheme uses roughly twenty to 180 times fewer memory cells than conventional CRAM and often gains both speed and a safer electrical noise margin. The work turns physical uncertainty from a nuisance into a resident computational resource: the memory does not merely store the dice; it rolls them and plays the game. |
|
Interconnects for DNA, Quantum, In-Memory, and Optical Computing: Insights From a Panel Discussion
Emerging computers form a wonderfully unruly menagerie: DNA carries information in liquids, qubits work inside refrigerators, photons race through waveguides, and memory arrays calculate where data already live. Their internal tricks are impressive; getting them to speak to one another may be harder. This article treats interconnects as the plumbing, roads, and translators of a future heterogeneous machine. It compares needs that span nanoseconds to hours and electrical signals to biochemical concentrations, then imagines specialized chiplets joined by a multilayer interposer carrying conventional wires, photonic links, wireless broadcasts, and microfluidic channels. Keeping communication within its native domain avoids costly conversions, while crossings between domains require carefully placed interfaces and workload-shaped network topologies. The deeper warning is that an exotic accelerator without suitable data movement is an island, however brilliant its local computation. The proposed interposer is less a motherboard than a miniature world whose roads change material at every border. |
|
Logic Synthesis for Switching Lattices
Self-assembled nanodevices prefer graph paper to blueprints: regular grids of identical switches rather than carefully routed transistor networks. This paper teaches the grid to compute by weaving a Boolean tapestry. Products of the target function run as columns, products of its Boolean dual as rows, and every crossing receives a literal common to both. The warp creates the intended top-to-bottom routes; the weft ensures that any meandering shortcut through the lattice is logically redundant. That matters because the possible paths multiply exponentially, yet the synthesis remains polynomial-time and never enumerates them. On benchmark functions, the resulting lattices sometimes reach the physical lower bound on path length. Instead of fighting the regularity imposed by self-assembly, the construction makes the fabric itself supply the logic. |
|
Robust Computation through Percolation: Synthesizing Logic with Percolation in Nanoscale Lattices
Percolation asks whether water poured onto a porous rock will find a path to the bottom. This paper builds a computer out of that question. Each Boolean literal controls a region of nanoscale switches; random stuck-on and stuck-off defects make the individual connections uncertain, but a large lattice has a cliff-like threshold at which global connectivity changes abruptly from nearly impossible to nearly certain. The synthesis makes the desired top-to-bottom function and the left-to-right function Boolean duals, eliminating diagonal near-paths that would allow a few stray switches to turn a zero into a one. Region dimensions are then chosen to meet prescribed error margins. No defect map or post-fabrication repair is needed: provided defects are independent, redundancy acts less like a pile of spare parts than a phase transition that snaps a noisy physical medium into a reliable logical answer. |
|
Application of LUT Cascades to Numerical Function Generators
Numerical function generators traditionally choose between arithmetic that walks and a lookup table that eats a warehouse. This paper offers a folding map. A curve is divided into straight segments by a modified Douglas–Peucker procedure, with short intervals around sharp bends and long ones where the terrain is gentle. A compact cascade of lookup tables determines which segment contains the input; a small coefficient table supplies that segment’s slope and intercept, and a multiplier and adder reconstruct the answer. Because segment numbers increase monotonically, the cascade needs only a few wires between stages. The method accommodates functions ranging from sine and logarithm to entropy, sigmoids, and Gaussian curves, without requiring a convergent series or even smoothness everywhere. In the cosine example, it shrinks the stored information from 524,288 bits to 1,460. The machine remembers the shape of the curve rather than memorizing every point on it. |
Computing with Feedback
|
Digital design has long treated feedback as memory: once a wire points backward, the circuit must remember its past. This paper draws an ouroboros that forgets. In a valid cyclic Boolean circuit, every input assignment supplies controlling values that cut the feedback before it can sustain ambiguity; the topology contains cycles, but the computation’s sensitized paths never bite their own tails. A rigorous three-valued semantics, beginning with every internal wire undefined, separates these circuits from latches and timing-dependent contraptions. The reward is shared computation: output functions can lean on one another instead of forcing some function at the top of an acyclic hierarchy to be built from scratch. Explicit families use as little as half the number of gates required by their acyclic counterparts under the same fan-in constraints, while any cyclic circuit with m gates can be unfolded into an acyclic one with at most m^2. The directed acyclic graph, it turns out, was a habit masquerading as a definition. |
|
The Synthesis of Cyclic Dependencies with Boolean Satisfiability
Once cycles are permitted, synthesis faces a circular-debt problem: which functions may borrow from one another without leaving the answer dependent on itself? This work hires a SAT solver as auditor. For a proposed dependency graph, two copies of every function search for the same primary input sustaining different internal answers; a satisfying assignment exposes an ambiguous fixed point, while unsatisfiability proves that the network remains combinational. Craig interpolation performs the delightful reversal at the heart of the method, turning the proof that no counterexample exists into the logic that implements the chosen dependencies. A branch-and-bound search begins with the tightest, most densely cyclic support sets and loosens only the functions implicated in ambiguity until it finds a low-cost valid graph. The approach scales far beyond its sum-of-products and decision-diagram predecessors. Feedback becomes a shared vocabulary: each function can say less because its neighbors are allowed to finish the sentence. |
|
The Analysis and Mapping of Cyclic Circuits with Boolean Satisfiability
A cyclic network can be perfectly sound as Boolean algebra and fail when that algebra is chopped into library gates. The identity b+\bar b=1, for example, assumes that b already has a Boolean value—exactly what is at stake inside a feedback loop. This paper treats technology mapping as a building inspection. It cuts enough wires to open every cycle, encodes each signal with two rails representing zero, one, or undefined, and asks a SAT solver whether the cut ends can agree at a fixed point while some signal remains floating. UNSAT certifies the circuit; SAT produces the precise input assignment that exposes the flaw. That counterexample then becomes a repair plan: logically redundant products or sums are added to exert controlling values only where the mapped circuit needs bracing. The method is orders of magnitude faster than its decision-diagram predecessor and lets feedback survive contact with physical gates. |
|
Timing Analysis of Cyclic Combinational Circuits
On a schematic, a cyclic circuit contains paths of infinite length. Measuring its speed by the longest drawn path would be like timing a commute by following a roundabout forever. This paper follows the traffic instead. Beginning with every internal wire undefined, symbolic event propagation tracks the sets of input assignments for which each gate settles to zero or one at each time step. A controlling value can end a journey early; only when no such value arrives must a gate wait for all its other inputs. Under an up-bounded inertial-delay model, the first time by which every input assignment gives the outputs definite values is the circuit’s delay bound. The method turns cyclic timing into the familiar problem of false-path-aware timing, without first unraveling the circuit into a potentially enormous acyclic copy. Incorporated into CYCLIFY, it enabled simultaneous improvements approaching 10% in area and 25% in delay. The clock follows logic’s traffic, not topology’s ink. |
|
Cyclic Combinational Circuits: Analysis for Synthesis
How can one prove that a knot will always untie without simulating every possible tug? This paper searches for the strand that must go slack first. For any input assignment that makes a cyclic network combinational, at least one node becomes independent of the feedback variables in its support. A symbolic operation called the marginal identifies exactly those assignments. The analysis cuts that node, substitutes its target function into the remaining network, and recurses on the smaller knot; the original network is valid precisely when these first-cut cases eventually cover the entire input space. Unlike earlier ternary-simulation methods, the formulation stays in Boolean algebra and naturally supports decision diagrams. Because restrictions commute, results for recurring subnetworks can also be cached as synthesis explores many related candidates. Analysis thus becomes a pruning oracle rather than a final inspection. Every input arrives carrying its own pair of scissors, although different inputs may cut the loop in different places. |
|
The Synthesis of Cyclic Combinational Circuits
Traditional logic synthesis arranges functions in a one-way organizational chart: each may reuse work performed below it, while the unfortunate function at the top must build everything from scratch. This paper abolishes the hierarchy. During resubstitution, any function may borrow another, even when the borrowing becomes mutual, provided the resulting circuit remains combinational. The CYCLIFY system searches this circular marketplace in two directions. Its “break-down” strategy starts with the cheapest, densely connected web and removes dependencies until the loops become safe; its “build-up” strategy starts with a safe acyclic design and adds opportunities for shared work until further feedback becomes invalid. Combinationality analysis guards every step, while branch-and-bound discards candidates that cannot beat the best solution. Benchmark networks shrank by as much as 30%, and cyclic improvements appeared in nearly every random trial. Feedback, formerly an accidental by-product to be eliminated, becomes a first-class optimization variable. |
Algorithms and Data Structures
|
Using Cubes of Non-state Variables With Property Directed Reachability
Property-directed reachability proves safety by remembering forbidden “cubes,” partial descriptions of states that must never occur. Ordinarily it speaks only in latch bits, rather like describing a crowd one face at a time even though everyone is already wearing informative uniforms. This paper lets the verifier use intermediate gate signals as well. Because such a signal is a function of several state bits, one gate literal can name a scattered family of states that would otherwise require several separate cubes. The transition relation is rearranged into a half-unrolled form so these gate-level descriptions can pass between frames, while logic-level-ordered ternary simulation removes literals whose values are already implied by others. On hardware-model-checking benchmarks, the richer vocabulary yields speedups as large as 3.2 times when counterexamples exist and 3.84 times when properties hold, though the gains vary by circuit. The deeper lesson is that internal wires are not verification clutter; they are ready-made abstractions, a shorthand the hardware has already computed. |
|
Resolution Proofs as a Data Structure for Logic Synthesis
A SAT solver’s resolution proof is usually treated like a receipt: it certifies the answer, then gets crumpled and thrown away. This paper keeps the receipt and starts designing on it. Proofs for several target functions are merged; clauses peculiar to one output are colored black, clauses available to all outputs white, and SAT is asked whether a black clause can be rebuilt entirely from the common white stock. Each successful rewrite moves useful reasoning into the shared trunk, so Craig interpolation produces circuits with common branches rather than separate thickets. An AIG displays only the gates already present; a resolution proof records alternate reasons those gates could work. The paper’s larger proposal is therefore a change of medium: the artifact that explains why a circuit exists becomes a malleable data structure for constructing a better one. |
|
Reduction of Interpolants for Logic Synthesis
Craig interpolation translates a proof of impossibility into a circuit—but, like an overly faithful translator, it preserves every detour. Two proofs of the same contradiction can consequently yield circuits of very different sizes. This paper edits the argument before translation. When an intermediate clause involving both sides of the problem is already implied by one side alone, incremental SAT promotes that clause to a new premise and prunes away the ancestry beneath it. Working backward from the contradiction tends to find the most consequential cuts, making the two halves of the proof more disjoint and the resulting interpolant markedly smaller, even after conventional logic optimization. The deeper lesson is that circuit bloat can begin as explanatory bloat: sometimes the shortest hardware comes from finding a shorter reason that it must work. |
|
Tolerating Faults in Counting Networks
Imagine a crowd taking numbered tickets without lining up at a single booth. A counting network spreads the crowd through many tiny turnstiles called balancers, avoiding the contention of a shared counter—but a failed turnstile can spoil the choreography. This paper offers two ways to keep the dance intact. The first replaces each balancer with a small troupe of pseudo-balancers that pass a leader’s baton whenever one member crashes, preserving exact counting despite a bounded number of failures. The second permits a failed balancer to return in an arbitrary state, proves that each such mishap wrinkles the output distribution by at most one token, and then sends the counts through butterfly-shaped correction stages that repeatedly bring the fullest and emptiest outputs together. Faults may rumple the fabric, but each pass irons out one crease; the network continues to balance the crowd without rebuilding the bottleneck it was invented to escape. |
Information Theory & Mathematics
|
Characterizing Polynomial Arithmetic with Stochastic Circuits
Earlier synthesis methods read a polynomial by its coefficients. This work looks instead at its constellation of roots. The fundamental theorem of algebra breaks a target function into linear factors for real roots and quadratic factors for complex-conjugate pairs; small branches of AND and NOT gates realize each accessible factor, and an AND tree stitches them together. The complex plane, however, contains a precisely charted forbidden shoal: roots within this region cannot be reached by the restricted, tree-shaped stochastic circuits considered here. Thus the paper supplies both a construction and an impossibility result, showing where the ship can sail and where the mathematics itself runs aground. For functions whose roots lie in navigable waters, the method produces remarkably lean circuits, reducing gate count and delay by about 68 percent on average relative to the earlier Bernstein-polynomial construction. A polynomial’s zeros become its hardware blueprint. |
|
A Study on Monotone Self-Dual Boolean Functions
A self-dual monotone function is a Boolean hall of mirrors: interchange AND with OR and the function looks back unchanged. This paper finds a surprisingly rigid skeleton inside that symmetry. Treating variables and prime implicants as the two shores of a bipartite graph, it proves that every variable must be married to a different term. A self-dual irredundant DNF therefore cannot have more variables than disjuncts, sharpening the previous quadratic bound to a linear one. At the knife-edge where the two numbers are equal, Hall’s matching theorem squeezes the possibilities further: most functions expose two-literal handles by which they can be reduced recursively, while the only densely interlocked exception is the seven-point Fano plane. The resulting recognition algorithm runs in polynomial time for this balanced case. What begins as a stubborn problem in Boolean dualization ends as incidence geometry with almost no room to wriggle. |
|
Synthesizing Cubes to Satisfy a Given Intersection Pattern
Ordinary two-level synthesis is handed points on a Boolean map and asked to cover them with cubes. This paper reverses the telescope: it is given only the census of every overlap—how many minterms belong to each cube, each pair, each triple, and so on—and must decide whether any cubes could have cast those shadows. Writing cubes as rows of 0, 1, and * turns variables into reusable column species; when all cubes intersect, a Möbius-like inversion on the Boolean lattice determines exactly how many columns of each species are needed. Empty intersections introduce opposing literals, but a “root” construction removes their signs, a disjointness graph restricts the admissible columns, and the remaining feasibility question becomes a system of linear equations and inequalities over nonnegative integers. This inverse Venn-diagram problem is a missing hinge in arithmetic logic minimization for probabilistic hardware, where the output probability cares how many minterms are covered, not which ones: given the shadows, the method rebuilds the boxes. |
|
Networks of Passive Oscillators
A biological clock is easy to sketch as a feedback loop; the harder task is persuading a network of mismatched clocks to find a rhythm that will not fade. This paper describes each oscillator by its energy manners rather than its internal anatomy: passive elements store and exchange energy, while nonlinear feedback returns energy when the motion is too small and drains it when the motion grows too large. KS multipliers make this description tractable for an interconnected MIMO Lur’e system, locating the gain values at which a quiet equilibrium tips through a Hopf or pitchfork bifurcation and gives way to a globally attracting limit cycle. Crucially, the test does not require every oscillator to be identical; heterogeneous components and nonlinear couplings can join the ensemble as long as they obey the same passivity contract. The result is a conductor’s score for synthetic gene oscillators: tune the flow of energy, and a collection of different instruments can still settle into a dependable beat. |
|
Uniform Approximation and Bernstein Polynomials with Coefficients in the Unit Interval
Bernstein’s classical theorem watches polynomials approach a curve; this paper looks behind the curve at the coefficients doing the approaching. It proves that when a fixed polynomial is repeatedly expressed in higher-degree Bernstein form, the coefficients crowd uniformly toward the polynomial’s values at the corresponding grid points. Degree elevation adds more control pegs without changing the curve, and eventually those pegs trace it as closely as desired. This yields an exact characterization with an appealingly visual boundary: apart from the constant zero and one, a polynomial can be written with every Bernstein coefficient in [0,1] precisely when its graph stays strictly inside the probability box over 0<x<1, touching the floor or ceiling only at the endpoints. Because Bernstein basis functions are nonnegative and sum to one, the reverse direction follows from their convex-combination geometry. For stochastic logic, whose coefficients must themselves be probabilities, the theorem turns implementability into a glance at the graph: if the curve remains in the room, enough control pegs can be brought inside with it. |
|
Computing in the RAIN: A Reliable Array of Independent Nodes
Rather than build one computer too sturdy to fail, RAIN gives a crowd of ordinary computers an umbrella. Compute nodes attach to widely separated switches so that a few broken links cannot tear the cluster in half; paired endpoints pass tokens to maintain the same history of an unreliable channel; a membership token tours the surviving nodes, while a “911” mechanism regenerates it or welcomes an excluded node home. Data receive the same communal treatment: MDS array codes scatter redundant fragments across machines, using inexpensive XOR operations so that any sufficient subset can reconstruct what vanished. Video serving, web serving, distributed checkpointing, and the commercial Rainwall system demonstrate that these are working foundations rather than isolated proofs. The governing idea is architectural: confine the difficult reasoning about failure to a few trustworthy building blocks, then let applications inherit their guarantees. Reliability ceases to mean a machine that never breaks; it means a community that agrees on what broke, routes around the hole, and remembers what was lost. |
Theses
 |
Most DNA archives write their answers into nucleotide sequences, then summon a sequencer whenever a bit must be read or changed. This thesis gives each bit a luggage tag and a handle. Every register strand carries its address and value in separate domains, with internal toeholds allowing instruction strands to retrieve one register, rewrite it, return it, or test it alongside a neighbor. Toehold exchange makes many molecular mistakes into reversible wrong turns: an incorrectly bound strand has a route home instead of becoming permanent debris. Thermodynamic and kinetic simulations identify the domain lengths, concentrations, and temperatures under which retrieval and pairwise computation remain reliable. The larger vision is modular memory whose pieces can move between systems and compute in parallel. The DNA archive learns to lend out a single book without emptying the library. |
 |
Carving a Niche in the Intersection of Computer Engineering and Molecular Biology This is a bilingual dissertation, translating in both directions across the narrow border between computer engineering and molecular biology. On one lane, computer instructions become chemistry: neighboring cells on nicked DNA sort, shift, compute parity, and search in parallel, while truth tables become chemical reaction networks that evaluate analog mathematical functions through stochastic logic. On the other lane, biological questions become computational ones: peptide–MHC prediction tools are audited against a physical property they can too easily learn imperfectly, hydrophobicity. The chapters range widely because the bridge itself is the subject. Algorithms gain a substrate with extraordinary density and parallelism; biology gains the discipline of representation, synthesis, testing, and computational controls. The thesis argues that neither field should merely borrow the other’s tools. The interesting science begins when each learns the other’s grammar. |
 |
DNA serves here as notebook, calculator, and memory palace. Small cuts in native double-stranded DNA encode bits without replacing its underlying sequence; heating turns selected cuts into toeholds, and strand displacement reads, rewrites, and moves the information. The report tours three rooms in this prospective molecular computer. An addressed AND gate reads chosen bits and writes its result elsewhere on the same DNA “deck.” An in-memory construction adapts the reversible Toffoli gate familiar from quantum logic, showing how one instruction can flip the proper bit across several stored inputs. A synthesis of DNA associative-memory schemes then moves from sequence matching to Hopfield networks built from seesaw gates, where a fragmentary cue retrieves a complete pattern. These are exploratory constructions rather than one finished machine. Together they ask the more consequential question: once DNA holds data, why should the data have to leave before it can think? |
 |
Digital Logic and Signal Processing Computations with Molecular Reactions Drop an electrical engineer into a cell and the voltmeter disappears. Concentrations become signals, chemical reaction networks become schematics, and DNA strand displacement becomes the fabrication process. This dissertation teaches that unfamiliar workshop a substantial engineering curriculum: asynchronous FIR and IIR filters, a fast Fourier transform, molecular analog-to-digital and digital-to-analog converters, and even Markov chains whose equilibrium populations reveal long-run probabilities. Its most fertile invention is fractional coding. A value travels as the ratio of two molecular populations, allowing Bernstein polynomials, multiplication, scaled addition, exponentials, sines, sigmoids, and a perceptron to emerge from simple reactions. These molecular machines would lose every race against silicon. Their purpose is to compete where silicon cannot comfortably enter—inside a biochemical environment, reading its native signals and answering in the same chemical language. The test tube becomes a signal-processing bench that can live beside the signal. |
 |
Data Cycling in Networks: Thoughts and Experiments Where is a packet while it travels? Hiding in plain sight: inside a fiber, waiting in a router, or crawling through propagation delay. This thesis treats that journey as storage. Garden hoses carrying paper messages and light folded between parallel mirrors establish the physical intuition; loops of network nodes then keep packets circulating until someone needs them. Wired experiments show that the idea works and also expose its tax in traffic, loss, and congestion. In wireless ad hoc networks, where there is little room for in-flight data, the circulating packet becomes more useful as a traveling scrap of context: each vehicle modifies and forwards it, allowing a changing population to count itself without a central authority. This is memory by juggling. It suits ephemeral, loss-tolerant information whose value fades quickly and whose users are already distributed. The bit survives by refusing to sit still. |
 |
Algorithms and Data Structures for Logic Synthesis and Verification Using Boolean Satisfiability A SAT solver begins as an interrogator: does some assignment make this formula true? This dissertation promotes it to auditor, editor, and architect. SAT first determines whether a circuit with feedback has one definite answer for every input, then helps synthesize and repair such cyclic circuits. When the answer is UNSAT, the solver leaves behind a resolution proof. Craig interpolation translates that proof of impossibility into working logic, and the thesis shows how to prune, recolor, and merge proofs so the resulting circuits become smaller and share more structure. The same habit of looking inside the machinery improves property-directed reachability: intermediate gate signals provide a compact vocabulary for describing whole families of forbidden states. The unifying reversal is delightful. A proof that something cannot happen ceases to be a dead certificate; it becomes raw material for constructing what should. In this workshop, “no” is a blueprint. |
 |
Digital Logic and Signal Processing Computations with Molecular Reactions Chemistry is an orchestra without a reliable metronome: every reaction starts when its molecules meet, and every tempo drifts with temperature and concentration. This dissertation writes a score whose players need only distinguish allegro from adagio. An RGB protocol passes signals among molecular colors when the next stage is empty; a sustained chemical oscillator supplies clock phases when synchrony helps; a fully asynchronous scheme uses absence indicators as handshakes. These mechanisms give chemistry the memory needed for moving-average and biquad filters, fast Fourier transforms, counters, latches, and flip-flops. Dual molecular populations turn each digital bit into a self-correcting tug-of-war, clearing small leaks before uncertainty spreads. The networks are compiled into DNA strand-displacement reactions and tested through kinetic simulation. The deeper contribution is temporal discipline: unruly molecular collisions acquire beats, handoffs, and remembered values, yet the answer does not depend on every musician playing at exactly the promised speed. |
 |
Logic Synthesis for Networks of Four-Terminal Switches Imagine a computer as a city drawn on graph paper. Each four-terminal switch is an intersection controlled by a Boolean literal, and the answer is one precisely when an open route crosses the city from north to south. The challenge is that a grid contains exponentially many winding routes, including shortcuts the designer never intended. This dissertation uses Boolean duality as urban planning: products of the target function shape one direction, products of its dual shape the other, producing compact lattices without enumerating every possible path. At the nanoscale, broken intersections become statistics. Large regions of redundant switches undergo a percolation transition, changing global connectivity sharply even when individual devices fail; duality prevents stray diagonal paths from turning a zero into a one. The geometry also yields new results about self-dual Boolean functions. Regularity and defects, often treated as the indignities of self-assembly, become the fabric from which reliable logic is woven. |
 |
Digital Yet Deliberately Random: Synthesizing Logical Computation on Stochastic Bit Streams Binary numbers are monarchies: the most significant bit rules, and one coup can overturn the value. A stochastic number is a democracy, represented by the fraction of equally weighted bits that vote one. That extravagantly long ballot makes arithmetic startlingly cheap—an AND gate multiplies, a multiplexer forms a weighted sum—and lets isolated bit flips disturb the result only slightly. This dissertation supplies the missing compiler. Bernstein polynomials translate arbitrary polynomial and approximated non-polynomial functions into stochastic circuits; additional synthesis methods manufacture the required probability streams from a small collection of biased sources and minimize the logic used to produce a target probability. Longer streams buy precision without rebuilding the hardware, while errors degrade gracefully. The price is time and representation length. The reward is a computational style fitted to dense, noisy technologies whose devices already behave probabilistically. Randomness becomes the number system rather than a defect layered on top of it. |
 |
Synthesizing Stochasticity in Biochemical Systems A cell is already a casino; this thesis asks chemistry to set the house odds. Deterministic reaction modules first calculate how an environment should influence a decision, composing addition, subtraction, multiplication, logarithms, exponentials, and powers. A stochastic module then reduces the choice to one molecular horse race. Competing initiation reactions start with prescribed odds; the first catalyst to appear amplifies itself, consumes its rivals’ fuel, and suppresses competing outcomes until a fleeting fluctuation becomes a stable decision. Molecular locks coordinate modules and prevent later stages from starting early, exchanging a vast hierarchy of exquisitely separated reaction speeds for extra chemical machinery and greater accuracy. Linear and integer programming automate parts of the design. The constructions remain abstract, with DNA proposed as the eventual physical vocabulary, yet the conceptual change is durable: biochemical noise becomes control flow, a programmable branch in the cell’s response to its world. |
 |
Stochastic Transient Analysis of Biochemical Systems Gillespie’s stochastic simulation places chemistry in a sealed snow globe: choose the initial molecules, shake, and watch the reactions unfold. This work opens windows in the glass. Stochastic transient analysis admits pulses, ramps, and sinusoids from outside the reaction network; an input may force a population to follow a waveform, inject or remove molecules, or switch on when another species crosses a threshold. Time-binned accumulation averages many random trials without memory growing with the number of simulations. Applied to a Lotka system and biochemical inverter, AND, NAND, OR, and XOR gates, the method becomes a molecular oscilloscope. The XOR gate provides the essential lesson: it reaches the correct logical level when driven slowly, yet cannot rise fully when its inputs change too quickly. A truth table can certify the destination. Transient analysis asks whether chemistry can get there in time. |
 |
Textbooks teach that feedback means memory. This dissertation finds loops with amnesia. In a cyclic combinational circuit, every output still depends only on the current inputs: for each input assignment, controlling values break the apparent circularity before any signal can chase its own tail. Feedback then lets output functions borrow intermediate work from one another, escaping the one-way hierarchy imposed by a directed acyclic graph. The thesis builds ternary and symbolic methods to prove such circuits sound, develops synthesis strategies that introduce cycles safely, and exhibits families using half as many gates as their best acyclic counterparts under the same fan-in bounds. Benchmark circuits also shrink and sometimes accelerate. The idea reaches beyond hardware to cyclic decision diagrams and other computational graphs. A loop can carry shared reasoning without carrying state. A structural convention had been wearing the robes of a behavioral law. |
Patents
 |
Parallel Computing using Stochastic Circuits and Deterministic Shuffling Networks This architecture divides a unary or stochastic bit stream into tuples, shuffles the combinations among parallel computation units, and recombines their outputs. The shuffling lets many units work at once without demanding a separate random source for every stream. |
 |
Low Discrepancy Deterministic Bit-Stream Processing Using Sobol Sequences This method encodes operands as deterministic bit streams drawn from different Sobol low-discrepancy sequences, then processes them with simple stochastic logic. It replaces noisy random sampling with repeatable streams that converge more quickly and accurately. |
 |
Sorting Networks using Unary Processing This sorting network accepts values encoded as unary or time-based signals and orders them directly in that representation. Avoiding conversion to conventional binary arithmetic reduces the cost of comparison and sorting hardware. |
 |
Polysynchronous Stochastic Circuits This design runs groups of stochastic processing elements from clocks that need not be tightly synchronized. It exploits the circuits’ natural tolerance of skew to relax clock distribution while preserving useful numerical behavior. |
 |
Stochastic Computation using Pulse-Width Modulated Signals This approach represents values in the duty cycle or frequency of pulse-width-modulated signals and computes directly on those periodic pulses. It seeks the compact, fault-tolerant arithmetic of stochastic computing without the delay of long random bit streams. |
 |
Stochastic Computing on Deterministic Bit Streams This system encodes numbers as deterministic bit streams, uses a convolver or shuffler to form the needed pairwise combinations, and applies ordinary stochastic logic. The result is repeatable computation without random-number generators. |
 |
Synthesis of Cyclic Combinational Circuits This synthesis method introduces safe feedback paths into multilevel combinational logic while preserving a definite output for every input. The added cycles let a circuit reuse intermediate logic and can reduce its size or delay. |
 |
A Reliable Array of Distributed Computing Nodes This distributed server architecture combines redundant storage with multiple communication paths so data service can continue after node, switch, or link failures. Reliability comes from the array’s organization rather than from assuming that any one component will remain available. |
