An official website of the United States government
We presentcalf, acost-awarelogicalframework for studying quantitative aspects of functional programs. Taking inspiration from recent work that reconstructs traditional aspects of programming languages in terms of a modal account ofphase distinctions, we argue that the cost structure of programs motivates a phase distinction betweenintensionandextension. Armed with this technology, we contribute a synthetic account of cost structure as a computational effect in which cost-aware programs enjoy an internal noninterference property: input/output behavior cannot depend on cost. As a full-spectrum dependent type theory,calfpresents a unified language for programming and specification of both cost and behavior that can be integrated smoothly with existing mathematical libraries available in type theoretic proof assistants. We evaluatecalfas a general framework for cost analysis by implementing two fundamental techniques for algorithm analysis: themethod of recurrence relationsandphysicist’s method for amortized analysis. We deploy these techniques on a variety of case studies: we prove a tight, closed bound for Euclid’s algorithm, verify the amortized complexity of batched queues, and derive tight, closed bounds for the sequential andparallelcomplexity of merge sort, all fully mechanized in the Agda proof assistant. Lastly we substantiate the soundness of quantitative reasoning incalfby means of a model construction.
more »
« less
A faster direct sampling algorithm for equilateral closed polygons and the probability of knotting
Abstract We present a faster direct sampling algorithm for random equilateral closed polygons in three-dimensional space. This method improves on the moment polytope sampling algorithm of Cantarellaet al(2016J. Phys. A: Math. Theor.49275202) and has (expected) time per sample quadratic in the number of edges in the polygon. We use our new sampling method and a new code for computing invariants based on the Alexander polynomial to investigate the probability of finding unknots among equilateral closed polygons.
more »
« less
- Award ID(s):
- 2107700
- PAR ID:
- 10519718
- Publisher / Repository:
- IOP Publishing
- Date Published:
- Journal Name:
- Journal of Physics A: Mathematical and Theoretical
- Volume:
- 57
- Issue:
- 28
- ISSN:
- 1751-8113
- Format(s):
- Medium: X Size: Article No. 285205
- Size(s):
- Article No. 285205
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)Random knot models are often used to measure the types of entanglements one would expect to observe in an unbiased system with some given physical property or set of properties. In nature, macromolecular chains often exist in extreme confinement. Current techniques for sampling random polygons in confinement are limited. In this paper, we gain insight into the knotting behavior of random polygons in extreme confinement by studying random polygons restricted to cylinders, where each edge connects the top and bottom disks of the cylinder. The knot spectrum generated by this model is compared to the knot spectrum of rooted equilateral random polygons in spherical confinement. Due to the rooting, such polygons require a radius of confinement R ⩾ 1. We present numerical evidence that the polygons generated by this simple cylindrical model generate knot probabilities that are equivalent to spherical confinement at a radius of R ≈ 0.62. We then show how knot complexity and the relative probability of different classes of knot types change as the length of the polygon increases in the cylindrical polygons.more » « less
-
Abstract New stimulus‐responsive scaffolds are of interest as constituents of hierarchical supramolecular ensembles. 1,3,5–2,4,6‐Functionalized, facially segregated benzene moieties have a time‐honored role as building blocks for host molecules. However, their user as switchable motifs in the construction of multi‐component supramolecular structures remains poorly explored. Here, we report a molecular cage 1, which consists of a bent anthracene dimer3paired with 1,3,5‐tris(aminomethyl)‐2,4,6‐triethylbenzene2. As the result of the pH‐inducedababab↔bababaisomerization of the constituent‐functionalized benzene units derived from2, this cage can reversibly convert between an open state and a closed form, both in solution and in the solid state. Cage 1was used to create stimuli‐responsive hierarchical superstructures, namely Russian doll‐like complexes with [K⊂18‐crown‐6⊂1]+and [K⊂cryptand‐222⊂1]+. The reversible assembly and disassembly of these superstructures could be induced by switching cage 1from its open to closed form. The present study thus provides an unusual example where pH‐triggered conformation motion within a cage‐like scaffold is used to control the formation and disassociation of hierarchical ensembles.more » « less
-
Abstract Biopolymers, like chromatin, are often confined in small volumes. Confinement has a great effect on polymer conformations, including polymer entanglement. Polymer chains and other filamentous structures can be represented by polygonal curves in three-space. In this manuscript, we examine the topological complexity of polygonal chains in three-space and in confinement as a function of their length. We model polygonal chains by equilateral random walks in three-space and by uniform random walks (URWs) in confinement. For the topological characterization, we use the second Vassiliev measure. This is an integer topological invariant for polygons and a continuous functions over the real numbers, as a function of the chain coordinates for open polygonal chains. For URWs in confined space, we prove that the average value of the Vassiliev measure in the space of configurations increases as O ( n 2 ) with the length of the walks or polygons. We verify this result numerically and our numerical results also show that the mean value of the second Vassiliev measure of equilateral random walks in three-space increases as O ( n ). These results reveal the rate at which knotting of open curves and not simply entanglement are affected by confinement.more » « less
-
Abstract This paper contains a method to prove the existence of smooth curves in positive characteristic whose Jacobians have unusual Newton polygons. Using this method, I give a new proof that there exist supersingular curves of genus$$4$$in every prime characteristic. More generally, the main result of the paper is that, for every$$g \geq 4$$and primep, every Newton polygon whosep-rank is at least$$g-4$$occurs for a smooth curve of genusgin characteristicp. In addition, this method resolves some cases of Oort’s conjecture about Newton polygons of curves.more » « less
