Varieties generated by modular lattices of width four

A variety (equational class) of lattices is said to be finitely based if there exists a finite set of identities defining the variety. Let M^∞_n denote the lattice variety generated by all modular lattices of width not exceeding n. M^∞₁ and M^∞₂ are both the class of all distributive lattices and consequently finitely based. B. Jónsson has shown that M^∞₃ is also finitely based. On the other hand, K. Baker has shown that M^∞_n is not finitely based for 5 ≤ n ˂ ω. This thesis settles the finite basis problem for M^∞₄. M^∞₄ is shown to be finitely based by proving the stronger result that there exist ten varieties which properly contain M^∞₄ and such that any variety which properly contains M^∞₄ contains one of these ten varieties.

The methods developed also yield a characterization of sub-directly irreducible width four modular lattices. From this characterization further results are derived. It is shown that the free M^∞₄ lattice with n generators is finite. A variety with exactly k covers is exhibited for all k ≥ 15. It is further shown that there are 2^Ӄo sub- varieties of M^∞₄.

Improving the biological activity of pyrrole-imidazole polyamides

DNA is nature’s blueprint, holding within it the genetic code that defines the structure and function of an organism. A complex network of DNA-binding proteins called transcription factors can largely control the flow of information from DNA, so modulating the function of transcription factors is a promising approach for treating many diseases. Pyrrole-imidazole (Py-Im) polyamides are a class of DNA-binding oligomers, which can be synthetically programmed to bind a target sequence of DNA. Due to their unique shape complementarity and a series of favorable hydrogen bonding interactions that occur upon DNA-binding, Py-Im polyamides can bind to the minor groove of DNA with affinities comparable to transcription factors. Previous studies have demonstrated that these cell-permeable small molecules can enter cell nuclei and disrupt the transcription factor-DNA interface, thereby repressing transcription. As the use of Py-Im polyamides has significant potential as a type of modular therapeutic platform, the need for polyamides with extremely favorable biological properties and high potency will be essential. Described herein, a variety of studies have been performed aimed at improving the biological activity of Py-Im polyamides. To improve the biological potency and cellular uptake of these compounds, we have developed a next-generation class of polyamides bearing aryl-turn moieties, a simple structural modification that allows significant improvements in cellular uptake. This strategy was also applied to a panel of high-affinity cyclic Py-Im polyamides, again demonstrating the remarkable effect minor structural changes can have on biological activity. The solubility properties of Py-Im polyamides and use of formulating reagents with their treatment have also been examined. Finally, we describe the study of Py-Im polyamides as a potential artificial transcription factor.

Dense, efficient chip-to-chip communication at the extremes of computing

The scalability of CMOS technology has driven computation into a diverse range of applications across the power consumption, performance and size spectra. Communication is a necessary adjunct to computation, and whether this is to push data from node-to-node in a high-performance computing cluster or from the receiver of wireless link to a neural stimulator in a biomedical implant, interconnect can take up a significant portion of the overall system power budget. Although a single interconnect methodology cannot address such a broad range of systems efficiently, there are a number of key design concepts that enable good interconnect design in the age of highly-scaled CMOS: an emphasis on highly-digital approaches to solving ‘analog’ problems, hardware sharing between links as well as between different functions (such as equalization and synchronization) in the same link, and adaptive hardware that changes its operating parameters to mitigate not only variation in the fabrication of the link, but also link conditions that change over time. These concepts are demonstrated through the use of two design examples, at the extremes of the power and performance spectra.

A novel all-digital clock and data recovery technique for high-performance, high density interconnect has been developed. Two independently adjustable clock phases are generated from a delay line calibrated to 2 UI. One clock phase is placed in the middle of the eye to recover the data, while the other is swept across the delay line. The samples produced by the two clocks are compared to generate eye information, which is used to determine the best phase for data recovery. The functions of the two clocks are swapped after the data phase is updated; this ping-pong action allows an infinite delay range without the use of a PLL or DLL. The scheme's generalized sampling and retiming architecture is used in a sharing technique that saves power and area in high-density interconnect. The eye information generated is also useful for tuning an adaptive equalizer, circumventing the need for dedicated adaptation hardware.

On the other side of the performance/power spectra, a capacitive proximity interconnect has been developed to support 3D integration of biomedical implants. In order to integrate more functionality while staying within size limits, implant electronics can be embedded onto a foldable parylene (‘origami’) substrate. Many of the ICs in an origami implant will be placed face-to-face with each other, so wireless proximity interconnect can be used to increase communication density while decreasing implant size, as well as facilitate a modular approach to implant design, where pre-fabricated parylene-and-IC modules are assembled together on-demand to make custom implants. Such an interconnect needs to be able to sense and adapt to changes in alignment. The proposed array uses a TDC-like structure to realize both communication and alignment sensing within the same set of plates, increasing communication density and eliminating the need to infer link quality from a separate alignment block. In order to distinguish the communication plates from the nearby ground plane, a stimulus is applied to the transmitter plate, which is rectified at the receiver to bias a delay generation block. This delay is in turn converted into a digital word using a TDC, providing alignment information.

Convex analysis for minimizing and learning submodular set functions

The connections between convexity and submodularity are explored, for purposes of minimizing and learning submodular set functions.

First, we develop a novel method for minimizing a particular class of submodular functions, which can be expressed as a sum of concave functions composed with modular functions. The basic algorithm uses an accelerated first order method applied to a smoothed version of its convex extension. The smoothing algorithm is particularly novel as it allows us to treat general concave potentials without needing to construct a piecewise linear approximation as with graph-based techniques.

Second, we derive the general conditions under which it is possible to find a minimizer of a submodular function via a convex problem. This provides a framework for developing submodular minimization algorithms. The framework is then used to develop several algorithms that can be run in a distributed fashion. This is particularly useful for applications where the submodular objective function consists of a sum of many terms, each term dependent on a small part of a large data set.

Lastly, we approach the problem of learning set functions from an unorthodox perspective---sparse reconstruction. We demonstrate an explicit connection between the problem of learning set functions from random evaluations and that of sparse signals. Based on the observation that the Fourier transform for set functions satisfies exactly the conditions needed for sparse reconstruction algorithms to work, we examine some different function classes under which uniform reconstruction is possible.

Developing peptide based capture agents for diagnostics and therapeutics

Iterative in situ click chemistry (IISCC) is a robust general technology for development of high throughput, inexpensive protein detection agents. In IISCC, the target protein acts as a template and catalyst, and assembles its own ligand from modular blocks of peptides. This process of ligand discovery is iterated to add peptide arms to develop a multivalent ligand with increased affinity and selectivity. The peptide based protein capture agents (PCC) should ideally have the same degree of selectivity and specificity as a monoclonal antibody, along with improved chemical stability. We had previously reported developing a PCC agent against bovine carbonic anhydrase II (bCAII) that could replace a polyclonal antibody. To further enhance the affinity or specificity of the PCC agent, I explore branching the peptide arms to develop branched PCC agents against bCAII. The developed branched capture agents have two to three fold higher affinities for the target protein. In the second part of my thesis, I describe the epitope targeting strategy, a strategy for directing the development of a peptide ligand against specific region or fragment of the protein. The strategy is successfully demonstrated by developing PCC agents with low nanomolar binding affinities that target the C-terminal hydrophobic motif of Akt2 kinase. One of the developed triligands inhibits the kinase activity of Akt. This suggests that, if targeted against the right epitope, the PCC agents can also influence the functional properties of the protein. The exquisite control of the epitope targeting strategy is further demonstrated by developing a cyclic ligand against Akt2. The cyclic ligand acts as an inhibitor by itself, without any iteration of the ligand discovery process. The epitope targeting strategy is a cornerstone of the IISCC technology and opens up new opportunities, leading to the development of protein detection agents and of modulators of protein functions.

Lightweight deformable mirrors for future space telescopes

This thesis presents a concept for ultra-lightweight deformable mirrors based on a thin substrate of optical surface quality coated with continuous active piezopolymer layers that provide modes of actuation and shape correction. This concept eliminates any kind of stiff backing structure for the mirror surface and exploits micro-fabrication technologies to provide a tight integration of the active materials into the mirror structure, to avoid actuator print-through effects. Proof-of-concept, 10-cm-diameter mirrors with a low areal density of about 0.5 kg/m² have been designed, built and tested to measure their shape-correction performance and verify the models used for design. The low cost manufacturing scheme uses replication techniques, and strives for minimizing residual stresses that deviate the optical figure from the master mandrel. It does not require precision tolerancing, is lightweight, and is therefore potentially scalable to larger diameters for use in large, modular space telescopes. Other potential applications for such a laminate could include ground-based mirrors for solar energy collection, adaptive optics for atmospheric turbulence, laser communications, and other shape control applications.

The immediate application for these mirrors is for the Autonomous Assembly and Reconfiguration of a Space Telescope (AAReST) mission, which is a university mission under development by Caltech, the University of Surrey, and JPL. The design concept, fabrication methodology, material behaviors and measurements, mirror modeling, mounting and control electronics design, shape control experiments, predictive performance analysis, and remaining challenges are presented herein. The experiments have validated numerical models of the mirror, and the mirror models have been used within a model of the telescope in order to predict the optical performance. A demonstration of this mirror concept, along with other new telescope technologies, is planned to take place during the AAReST mission.

Control of dynamical systems with temporal logic specifications

This thesis is motivated by safety-critical applications involving autonomous air, ground, and space vehicles carrying out complex tasks in uncertain and adversarial environments. We use temporal logic as a language to formally specify complex tasks and system properties. Temporal logic specifications generalize the classical notions of stability and reachability that are studied in the control and hybrid systems communities. Given a system model and a formal task specification, the goal is to automatically synthesize a control policy for the system that ensures that the system satisfies the specification. This thesis presents novel control policy synthesis algorithms for optimal and robust control of dynamical systems with temporal logic specifications. Furthermore, it introduces algorithms that are efficient and extend to high-dimensional dynamical systems.

The first contribution of this thesis is the generalization of a classical linear temporal logic (LTL) control synthesis approach to optimal and robust control. We show how we can extend automata-based synthesis techniques for discrete abstractions of dynamical systems to create optimal and robust controllers that are guaranteed to satisfy an LTL specification. Such optimal and robust controllers can be computed at little extra computational cost compared to computing a feasible controller.

The second contribution of this thesis addresses the scalability of control synthesis with LTL specifications. A major limitation of the standard automaton-based approach for control with LTL specifications is that the automaton might be doubly-exponential in the size of the LTL specification. We introduce a fragment of LTL for which one can compute feasible control policies in time polynomial in the size of the system and specification. Additionally, we show how to compute optimal control policies for a variety of cost functions, and identify interesting cases when this can be done in polynomial time. These techniques are particularly relevant for online control, as one can guarantee that a feasible solution can be found quickly, and then iteratively improve on the quality as time permits.

The final contribution of this thesis is a set of algorithms for computing feasible trajectories for high-dimensional, nonlinear systems with LTL specifications. These algorithms avoid a potentially computationally-expensive process of computing a discrete abstraction, and instead compute directly on the system's continuous state space. The first method uses an automaton representing the specification to directly encode a series of constrained-reachability subproblems, which can be solved in a modular fashion by using standard techniques. The second method encodes an LTL formula as mixed-integer linear programming constraints on the dynamical system. We demonstrate these approaches with numerical experiments on temporal logic motion planning problems with high-dimensional (10+ states) continuous systems.

Formal methods for control synthesis in partially observed environments : application to autonomous robotic manipulation

Modern robots are increasingly expected to function in uncertain and dynamically challenging environments, often in proximity with humans. In addition, wide scale adoption of robots requires on-the-fly adaptability of software for diverse application. These requirements strongly suggest the need to adopt formal representations of high level goals and safety specifications, especially as temporal logic formulas. This approach allows for the use of formal verification techniques for controller synthesis that can give guarantees for safety and performance. Robots operating in unstructured environments also face limited sensing capability. Correctly inferring a robot's progress toward high level goal can be challenging.

This thesis develops new algorithms for synthesizing discrete controllers in partially known environments under specifications represented as linear temporal logic (LTL) formulas. It is inspired by recent developments in finite abstraction techniques for hybrid systems and motion planning problems. The robot and its environment is assumed to have a finite abstraction as a Partially Observable Markov Decision Process (POMDP), which is a powerful model class capable of representing a wide variety of problems. However, synthesizing controllers that satisfy LTL goals over POMDPs is a challenging problem which has received only limited attention.

This thesis proposes tractable, approximate algorithms for the control synthesis problem using Finite State Controllers (FSCs). The use of FSCs to control finite POMDPs allows for the closed system to be analyzed as finite global Markov chain. The thesis explicitly shows how transient and steady state behavior of the global Markov chains can be related to two different criteria with respect to satisfaction of LTL formulas. First, the maximization of the probability of LTL satisfaction is related to an optimization problem over a parametrization of the FSC. Analytic computation of gradients are derived which allows the use of first order optimization techniques.

The second criterion encourages rapid and frequent visits to a restricted set of states over infinite executions. It is formulated as a constrained optimization problem with a discounted long term reward objective by the novel utilization of a fundamental equation for Markov chains - the Poisson equation. A new constrained policy iteration technique is proposed to solve the resulting dynamic program, which also provides a way to escape local maxima.

The algorithms proposed in the thesis are applied to the task planning and execution challenges faced during the DARPA Autonomous Robotic Manipulation - Software challenge.

Multi-model inference ranking and applications to physics at the Large Hadron Collider

In the measurement of the Higgs Boson decaying into two photons the parametrization of an appropriate background model is essential for fitting the Higgs signal mass peak over a continuous background. This diphoton background modeling is crucial in the statistical process of calculating exclusion limits and the significance of observations in comparison to a background-only hypothesis. It is therefore ideal to obtain knowledge of the physical shape for the background mass distribution as the use of an improper function can lead to biases in the observed limits. Using an Information-Theoretic (I-T) approach for valid inference we apply Akaike Information Criterion (AIC) as a measure of the separation for a fitting model from the data. We then implement a multi-model inference ranking method to build a fit-model that closest represents the Standard Model background in 2013 diphoton data recorded by the Compact Muon Solenoid (CMS) experiment at the Large Hadron Collider (LHC). Potential applications and extensions of this model-selection technique are discussed with reference to CMS detector performance measurements as well as in potential physics analyses at future detectors.

Special Frobenius Traces in Galois Representations

This thesis studies Frobenius traces in Galois representations from two different directions. In the first problem we explore how often they vanish in Artin-type representations. We give an upper bound for the density of the set of vanishing Frobenius traces in terms of the multiplicities of the irreducible components of the adjoint representation. Towards that, we construct an infinite family of representations of finite groups with an irreducible adjoint action.

In the second problem we partially extend for Hilbert modular forms a result of Coleman and Edixhoven that the Hecke eigenvalues a_p of classical elliptical modular newforms f of weight 2 are never extremal, i.e., a_p is strictly less than 2[square root]p. The generalization currently applies only to prime ideals p of degree one, though we expect it to hold for p of any odd degree. However, an even degree prime can be extremal for f. We prove our result in each of the following instances: when one can move to a Shimura curve defined by a quaternion algebra, when f is a CM form, when the crystalline Frobenius is semi-simple, and when the strong Tate conjecture holds for a product of two Hilbert modular surfaces (or quaternionic Shimura surfaces) over a finite field.

Programming chemical kinetics: engineering dynamic reaction networks with DNA strand displacement

Over the last century, the silicon revolution has enabled us to build faster, smaller and more sophisticated computers. Today, these computers control phones, cars, satellites, assembly lines, and other electromechanical devices. Just as electrical wiring controls electromechanical devices, living organisms employ "chemical wiring" to make decisions about their environment and control physical processes. Currently, the big difference between these two substrates is that while we have the abstractions, design principles, verification and fabrication techniques in place for programming with silicon, we have no comparable understanding or expertise for programming chemistry.

In this thesis we take a small step towards the goal of learning how to systematically engineer prescribed non-equilibrium dynamical behaviors in chemical systems. We use the formalism of chemical reaction networks (CRNs), combined with mass-action kinetics, as our programming language for specifying dynamical behaviors. Leveraging the tools of nucleic acid nanotechnology (introduced in Chapter 1), we employ synthetic DNA molecules as our molecular architecture and toehold-mediated DNA strand displacement as our reaction primitive.

Abstraction, modular design and systematic fabrication can work only with well-understood and quantitatively characterized tools. Therefore, we embark on a detailed study of the "device physics" of DNA strand displacement (Chapter 2). We present a unified view of strand displacement biophysics and kinetics by studying the process at multiple levels of detail, using an intuitive model of a random walk on a 1-dimensional energy landscape, a secondary structure kinetics model with single base-pair steps, and a coarse-grained molecular model that incorporates three-dimensional geometric and steric effects. Further, we experimentally investigate the thermodynamics of three-way branch migration. Our findings are consistent with previously measured or inferred rates for hybridization, fraying, and branch migration, and provide a biophysical explanation of strand displacement kinetics. Our work paves the way for accurate modeling of strand displacement cascades, which would facilitate the simulation and construction of more complex molecular systems.

In Chapters 3 and 4, we identify and overcome the crucial experimental challenges involved in using our general DNA-based technology for engineering dynamical behaviors in the test tube. In this process, we identify important design rules that inform our choice of molecular motifs and our algorithms for designing and verifying DNA sequences for our molecular implementation. We also develop flexible molecular strategies for "tuning" our reaction rates and stoichiometries in order to compensate for unavoidable non-idealities in the molecular implementation, such as imperfectly synthesized molecules and spurious "leak" pathways that compete with desired pathways.

We successfully implement three distinct autocatalytic reactions, which we then combine into a de novo chemical oscillator. Unlike biological networks, which use sophisticated evolved molecules (like proteins) to realize such behavior, our test tube realization is the first to demonstrate that Watson-Crick base pairing interactions alone suffice for oscillatory dynamics. Since our design pipeline is general and applicable to any CRN, our experimental demonstration of a de novo chemical oscillator could enable the systematic construction of CRNs with other dynamic behaviors.

An in vitro biomolecular breadboard for prototyping synthetic biological circuits

Biomolecular circuit engineering is critical for implementing complex functions in vivo, and is a baseline method in the synthetic biology space. However, current methods for conducting biomolecular circuit engineering are time-consuming and tedious. A complete design-build-test cycle typically takes weeks' to months' time due to the lack of an intermediary between design ex vivo and testing in vivo. In this work, we explore the development and application of a "biomolecular breadboard" composed of an in-vitro transcription-translation (TX-TL) lysate to rapidly speed up the engineering design-build-test cycle. We first developed protocols for creating and using lysates for conducting biological circuit design. By doing so we simplified the existing technology to an affordable ($0.03/uL) and easy to use three-tube reagent system. We then developed tools to accelerate circuit design by allowing for linear DNA use in lieu of plasmid DNA, and by utilizing principles of modular assembly. This allowed the design-build-test cycle to be reduced to under a business day. We then characterized protein degradation dynamics in the breadboard to aid to implementing complex circuits. Finally, we demonstrated that the breadboard could be applied to engineer complex synthetic circuits in vitro and in vivo. Specifically, we utilized our understanding of linear DNA prototyping, modular assembly, and protein degradation dynamics to characterize the repressilator oscillator and to prototype novel three- and five-node negative feedback oscillators both in vitro and in vivo. We therefore believe the biomolecular breadboard has wide application for acting as an intermediary for biological circuit engineering.

Reggeization of some unequal mass processes involving higher spins : the reactions pion-nucleon going to (V,Nucleon), pion-nucleon going to (V,delta-hyperon), and photon-proton going to (positive pion,neutron)

Recent theoretical developments in the reggeization of inelastic processes involving particles with high spin are incorporated into a model of vector meson production. A number of features of experimental differential cross sections and density matrices are interpreted in terms of this model.

The method chosen for reggeization of helicity amplitudes first separates kinematic zeros and singularities from the parity-conserving amplitudes and then applies results of Freedman and Wang on daughter trajectories to the remaining factors. Kinematic constraints on helicity amplitudes at t = 0 and t = (M – M_Δ)² are also considered.

It is found that data for reactions of types πN→VN and πN→VΔ are consistent with a model of this type in which all kinematic constraints at t = 0 are satisfied by evasion (vanishing of residue functions). As a quantitative test of the parametrization, experimental differential cross sections of vector meson production reactions dominated by pion trajectory exchange are compared with the theory. It is found that reduced residue functions are approximately constant, once the kinematic behavior near t = (M – M_Δ)² has been removed.

The alternative possibility of conspiracy between amplitudes is also discussed; and it is shown that unless conspiracy is present, some amplitudes allowed by angular momentum conservation will not contribute with full strength in the forward direction. An example, γp→π⁺n in which the data for dσ/dt indicate conspiracy, is studied in detail.

Combinatorial properties of finite geometric lattices

Let L be a finite geometric lattice of dimension n, and let w(k) denote the number of elements in L of rank k. Two theorems about the numbers w(k) are proved: first, w(k) ≥ w(1) for k = 2, 3, ..., n-1. Second, w(k) = w(1) if and only if k = n-1 and L is modular. Several corollaries concerning the "matching" of points and dual points are derived from these theorems.

Both theorems can be regarded as a generalization of a theorem of de Bruijn and Erdös concerning ʎ= 1 designs. The second can also be considered as the converse to a special case of Dilworth's theorem on finite modular lattices.

These results are related to two conjectures due to G. -C. Rota. The "unimodality" conjecture states that the w(k)'s form a unimodal sequence. The "Sperner" conjecture states that a set of non-comparable elements in L has cardinality at most max/k {w(k)}. In this thesis, a counterexample to the Sperner conjecture is exhibited.

Elimination of parity doublets in Regge amplitudes

In Part I, the common belief that fermions lying on linear trajectories must have opposite-parity partners is shown to be false. Reggeization of a sequence of positive-parity fermion resonance is carried out in the Van Hove model. As a consequence of the absence of negative-parity states, the partial-wave amplitudes must have a fixed cut in the J plane. This fixed cut, in conjunction with the moving Regge pole, provides a new parametrization for fermion-exchange reactions, which is in qualitative agreement with the data.

In Part II, the spin structure of three particle vertices is determined from the quark model. Using these SU(6)_W vertices in the Van Hove model, we derive a Reggeized scattering amplitude. In addition to Regge poles there are necessarily fixed Regge cuts in both fermion and boson exchange amplitudes. These fixed cuts are similar to those found in Part I, and may be viewed as a consequence of the absence of parity doubled quarks. The magnitudes of the pole and cut terms in an entire class of SU(6) related reactions are determined by their magnitudes in a single reaction. As an example we explain the observed presence or absence of wrong-signature nonsense dips in a class of reactions involving vector meson exchange.