These are my recent Pinboard.in links:

• [1105.4335] Physical approaches to the dynamics of genetic circuits: A tutorial

  "Cellular behavior is governed by gene regulatory processes that are intrinsically dynamic and nonlinear, and are subject to non-negligible amounts of random fluctuations. Such conditions are ubiquitous in physical systems, where they have been studied for decades using the tools of statistical and nonlinear physics. The goal of this review is to show how approaches traditionally used in physics can help in reaching a systems-level understanding of living cells. To that end, we present an overview of the dynamical phenomena exhibited by genetic circuits and their functional significance. We also describe the theoretical and experimental approaches that are being used to unravel the relationship between circuit structure and function in dynamical cellular processes under the influence of noise, both at the single-cell level and in cellular populations, where intercellular coupling plays an important role."

  systems-biology biological-engineering genetic-regulatory-networks emergent-design biochemistry overview

• [1106.0371] A Novel Image Segmentation Enhancement Technique based on Active Contour and Topological Alignments

  "Topological alignments and snakes are used in image processing, particularly in locating object boundaries. Both of them have their own advantages and limitations. To improve the overall image boundary detection system, we focused on developing a novel algorithm for image processing. The algorithm we propose to develop will based on the active contour method in conjunction with topological alignments method to enhance the image detection approach. The algorithm presents novel technique to incorporate the advantages of both Topological Alignments and snakes. Where the initial segmentation by Topological Alignments is firstly transformed into the input of the snake model and begins its evolvement to the interested object boundary. The results show that the algorithm can deal with low contrast images and shape cells, demonstrate the segmentation accuracy under weak image boundaries, which responsible for lacking accuracy in image detecting techniques. We have achieved better segmentation and boundary detecting for the image, also the ability of the system to improve the low contrast and deal with over and under segmentation."

  image-segmentation algorithms nudge-targets

• [1106.2508] A Practical Implementation of the Bernoulli Factory

  "…While several practical uses of the method have been proposed in Monte Carlo applications, these require an implementation framework that is flexible, general and efficient. We present such a framework for functions that are either strictly linear, concave, or convex on the unit interval using a series of envelope functions defined through a cascade, and show that this method not only greatly reduces the number of input bits needed in practice compared to other currently proposed solutions for more specific problems, but can easily be coupled to more asymptotically efficient methods to allow for theoretically strong results."

  algorithms numerical-methods Monte-Carlo-simulation probability-theory nudge-targets

• [1105.1729] Evolutionary search for novel superhard materials

  "We have developed a method for prediction of the hardest crystal structures in a given chemical system. It is based on the evolutionary algorithm USPEX and electronegativity-based hardness model that we have augmented with bond-valence model and graph theory. These extensions enable correct description of the hardness of layered, molecular and low-symmetry crystal structures. Applying this method to C and TiO2, we have (i) obtained a number of low-energy carbon structures with hardness slightly lower than diamond and (ii) proved that TiO2 in any of its possible polymorphs cannot be the hardest oxide, its hardness being below 17 GPa."

  materials-science genetic-algorithm condensed-matter simulation nudge-targets

• [1109.0573] Phase Retrieval via Matrix Completion

  "This paper considers the fundamental problem of recovering a general signal, an image for example, from the magnitude of its Fourier transform. This problem, also known as phase retrieval, arises in many applications and has challenged engineers, physicists, and mathematicians for decades. Its origin comes from the fact that detectors can often times only record the squared modulus of the Fresnel or Fraunhofer diffraction pattern of the radiation that is scattered from an object. In such settings, one cannot measure the phase of the optical wave reaching the detector and, therefore, much information about the scattered object or the optical field is lost since, as is well known, the phase encodes a lot of the structural content of the image we wish to form."

  image-processing inverse-problems signal-processing system-identification frequency-space algorithms nudge-targets numerical-methods

• [1109.0807] Harmonic Analysis of Boolean Networks: Determinative Power and Perturbations

  "Consider a large Boolean network with a feed forward structure. Given a probability distribution for the inputs, can one find-possibly small-collections of input nodes that determine the states of most other nodes in the network?…"

  Boolean-networks Kauffmania complexology discrete-mathematics mathematical-recreations nudge-targets

• [0801.0830] Evolution of central pattern generators for the control of a five-link bipedal walking mechanism

  "With the aim of producing a stable human-like bipedal gait, a five-link planar walking mechanism is coupled with a central pattern generator (CPG) neural network, consisting of units based on Matsuoka's half-center oscillator model with a firm basis in neurophysiology. As a minimalistic approach to bipedal walking, this type of walking mechanism contains only four actuators, and is lacking feet and ankles. The mechanism is simulated with accurate physics, allowing realistic fitness evaluations for the creation of CPG controllers through evolutionary computation. The oscillatory parameters, internal connectivity structure, and external feedback pathways of the networks are determined through genetic algorithms (GA) optimization. The evolved CPG networks are transferred to a hardware implementation of the mechanism, to test their performance under real-world dynamics. Results confirm that the biologically inspired CPG model is very well suited for controlling legged locomotion, since a diverse manifestation of CPG networks (with and without external feedback) have been observed to succeed during the course of GA evaluations. Observations also imply that while the CPG mechanism is inherently able to sustain a stable gait, the utilization of feedback pathways makes the gait more human-like and is needed to provide a means to adapt to irregularities in the environment."

  robotics engineering-design genetic-algorithm neural-networks cybernetics nudge-targets

• [1109.3351] Physical limits on cooperative protein-DNA binding and the kinetics of combinatorial transcription regulation

  "Much of the complexity observed in gene regulation originates from cooperative protein-DNA binding. While studies of the target search of proteins for their specific binding sites on the DNA have revealed design principles for the quantitative characteristics of protein-DNA interactions, no such principles are known for the cooperative interactions between DNA-binding proteins. We consider a simple theoretical model for two interacting transcription factor (TF) species, searching for and binding to two adjacent target sites hidden in the genomic background. We study the kinetic competition of a dimer search pathway and a monomer search pathway, as well as the steady-state regulation function mediated by the two TFs over a broad range of TF-TF interaction strengths. Using a transcriptional AND-logic as exemplary functional context, we identify the functionally desirable regime for the interaction. We find that both weak and very strong TF-TF interactions are favorable, albeit with different characteristics. However, there is also an unfavorable regime of intermediate interactions where the genetic response is prohibitively slow."

  biological-engineering genetic-regularory-networks systems-biology emergent-design nudge-targets

• [1109.6874] #h00t: Censorship Resistant Microblogging

  "Microblogging services such as Twitter are an increasingly important way to communicate, both for individuals and for groups through the use of hashtags that denote topics of conversation. However, groups can be easily blocked from communicating through blocking of posts with the given hashtags. We propose #h00t, a system for censorship resistant microblogging. #h00t presents an interface that is much like Twitter, except that hashtags are replaced with very short hashes (e.g., 24 bits) of the group identifier. Naturally, with such short hashes, hashtags from different groups may collide and #h00t users will actually seek to create collisions. By encrypting all posts with keys derived from the group identifiers, #h00t client software can filter out other groups' posts while making such filtering difficult for the adversary. In essence, by leveraging collisions, groups can tunnel their posts in other groups' posts. A censor could not block a given group without also blocking the other groups with colliding hashtags. We evaluate the feasibility of #h00t through traces collected from Twitter, showing that a single modern computer has enough computational throughput to encrypt every tweet sent through Twitter in real time. We also use these traces to analyze the bandwidth and anonymity tradeoffs that would come with different variations on how group identifiers are encoded and hashtags are selected to purposefully collide with one another."

  social-media steganography robustness activism cute

• [1107.0414] A random walk on image patches

  "In this paper we address the problem of understanding the success of algorithms that organize patches according to graph-based metrics. Algorithms that analyze patches extracted from images or time series have led to state-of-the art techniques for classification, denoising, and the study of nonlinear dynamics. The main contribution of this work is to provide a theoretical explanation for the above experimental observations. Our approach relies on a detailed analysis of the commute time metric on prototypical graph models that epitomize the geometry observed in general patch graphs.…"

  image-segmentation image-analysis algorithms combinatorics nudge-targets

• [1107.0385] An algorithm for autonomously plotting solution sets in the presence of turning points

  "Plotting solution sets for particular equations may be complicated by the existence of turning points. Here we describe an algorithm which not only overcomes such problematic points, but does so in the most general of settings. Applications of the algorithm are highlighted through two examples: the first provides verification, while the second demonstrates a non-trivial application. The latter is followed by a thorough run-time analysis. While both examples deal with bivariate equations, it is discussed how the algorithm may be generalized for space curves in $R^{3}$."

  visualization mathematics graphics approximation algorithms nudge-targets

• [1105.1033] Adaptively Learning the Crowd Kernel

  "We introduce an algorithm that, given n objects, learns a similarity matrix over all n^2 pairs, from crowdsourced data alone. The algorithm samples responses to adaptively chosen triplet-based relative-similarity queries. Each query has the form "is object 'a' more similar to 'b' or to 'c'?" and is chosen to be maximally informative given the preceding responses. The output is an embedding of the objects into Euclidean space (like MDS); we refer to this as the "crowd kernel." SVMs reveal that the crowd kernel captures prominent and subtle features across a number of domains, such as "is striped" among neckties and "vowel vs. consonant" among letters."

  classification ontology-discovery crowdsourcing feature-extraction algorithms nudge-targets performance-space-analysis

• [1109.1030] An Algorithm for Detecting Intrinsically Knotted Graphs

  "We describe an algorithm that recognizes some (perhaps all) intrinsically knotted (IK) graphs, and can help find knotless embeddings for graphs that are not IK. The algorithm, implemented as a Mathematica program, has already been used by Goldberg, Mattman, and Naimi [6] to greatly expand the list of known minor minimal IK graphs, and to find knotless embeddings for some graphs that had previously resisted attempts to classify them as IK or non-IK."

  combinatorics topology algorithms nudge-targets

• [1109.5635] Approximating Edit Distance in Near-Linear Time

  "We show how to compute the edit distance between two strings of length n up to a factor of 2^{~O(sqrt(log n))} in n^(1+o(1)) time. This is the first sub-polynomial approximation algorithm for this problem that runs in near-linear time, improving on the state-of-the-art n^(1/3+o(1)) approximation. Previously, approximation of 2^{~O(sqrt(log n))} was known only for embedding edit distance into l_1, and it is not known if that embedding can be computed in less than quadratic time."

  algorithms string-editing Levenshtein-distance rewriting-systems bioinformatics nudge-targets

• [1107.1866] Priority-based task reassignments in hierarchical 2D mesh-connected systems using tableaux

  "Task reassignments in 2D mesh-connected systems (2D-MSs) have been researched and simulated for several decades. We propose a hierarchical 2D mesh-connected system (2D-HMS) in order to exploit the regular nature of a 2D-MS. In our approach priority-based task assignments and reassignments in a 2D-HMS are represented by tableaux and their algorithms. We provide examples of priority-based task reassignments in a 2D-HMS in which task relocations are simply reduced to a jeu de taquin slide."

  scheduling operations-research algorithms grid-computing optimization nudge-targets

• [1101.4744] Clustering functional data using wavelets

  "We present two methods for detecting patterns and clusters in high dimensional time-dependent functional data. Our methods are based on wavelet-based similarity measures, since wavelets are well suited for identifying highly discriminant local time and scale features. The multiresolution aspect of the wavelet transform provides a time-scale decomposition of the signals allowing to visualize and to cluster the functional data into homogeneous groups. For each input function, through its empirical orthogonal wavelet transform the first method uses the distribution of energy across scales generate a handy number of features that can be sufficient to still make the signals well distinguishable. Our new similarity measure combined with an efficient feature selection technique in the wavelet domain is then used within more or less classical clustering algorithms to effectively differentiate among high dimensional populations. The second method uses dissimilarity measures between the whole time-scale representations and are based on wavelet-coherence tools. The clustering is then performed using a k-centroid algorithm starting from these dissimilarities. Practical performance of these methods that jointly designs both the feature selection in the wavelet domain and the classification distance is demonstrated through simulations as well as daily profiles of the French electricity power demand."

  classification time-series feature-extraction machine-learning multiobjective-optimization ontology-discovery wavelets nudge-targets

• [1105.3726] Controlling Complex Networks with Compensatory Perturbations

  "The response of complex networks to perturbations is of utmost importance in areas as diverse as ecosystem management, emergency response, and cell reprogramming. A fundamental property of networks is that the perturbation of one node can affect other nodes, in a process that may cause the entire or substantial part of the system to change behavior and possibly collapse. Recent research in metabolic and food-web networks has demonstrated the concept that network damage caused by external perturbations can often be mitigated or reversed by the application of compensatory perturbations. Compensatory perturbations are constrained to be physically admissible and amenable to implementation on the network. However, the systematic identification of compensatory perturbations that conform to these constraints remains an open problem. Here, we present a method to construct compensatory perturbations that can control the fate of general networks under such constraints. Our approach accounts for the full nonlinear behavior of real complex networks and can bring the system to a desirable target state even when this state is not directly accessible. Applications to genetic networks show that compensatory perturbations are effective even when limited to a small fraction of all nodes in the network and that they are far more effective when limited to the highest-degree nodes. The approach is conceptually simple and computationally efficient, making it suitable for the rescue, control, and reprogramming of large complex networks in various domains."

  emergent-design complexology control biological-engineering nudge-targets

• [1109.1275] A Formal Verification Approach to the Design of Synthetic Gene Networks

  "The design of genetic networks with specific functions is one of the major goals of synthetic biology. However, constructing biological devices that work "as required" remains challenging, while the cost of uncovering flawed designs experimentally is large. To address this issue, we propose a fully automated framework that allows the correctness of synthetic gene networks to be formally verified in silico from rich, high level functional specifications.
  Given a device, we automatically construct a mathematical model from experimental data characterizing the parts it is composed of. The specific model structure guarantees that all experimental observations are captured and allows us to construct finite abstractions through polyhedral operations. The correctness of the model with respect to temporal logic specifications can then be verified automatically using methods inspired by model checking.
  Overall, our procedure is conservative but it can filter through a large number of potential device designs and select few that satisfy the specification to be implemented and tested further experimentally. Illustrative examples of the application of our methods to the design of simple synthetic gene networks are included."

  genetic-regulatory-networks bioinformatics biological-engineering design-automation emergent-design acceptance-testing performance-measure nudge

• [1108.1150] Epistasis can lead to fragmented neutral spaces and contingency in evolution

  "Under neutral reciprocal sign epistasis, two genetic changes are jointly neutral, even though their individual effects are deleterious. By using the widely studied mapping from an RNA sequence to secondary structure, we investigate the effect of this kind of epistasis on neutral spaces corresponding to networks of genotypes that fold to the same secondary structure. Neutral networks for RNA structures with n bonds are typically fragmented into at least 2^n different neutral components that cannot be connected by single point mutations. By exhaustive enumeration of all RNA secondary structures of sequences of length 15 we show that most networks are not dominated by one neutral component, but are rather broken up into multiple large components. Although they generate the same phenotype, components of a single neutral network are heterogeneous, showing wide variations in their robustness and their evolvability. Both properties are correlated with component size, rather than with the size of their underlying neutral network. In particular, sets of accessible phenotypes can vary quite strongly between components. Thus, the potential for future innovation is contingent on which neutral component a population occupies. We further argue that neutral reciprocal sign epistasis may have similar consequences for neutral evolution of other biological systems as well."

  combinatorics RNA neutral-networks complexology bioinformatics polymer-models mathematical-recreations nudge-targets

• OldFonts.com | About Us

  "Willson founded 3IP in 1989 to self-publish a book of pretentious nature essays. Soon after, he found himself tinkering with type design, and 3IP has since become known for its library of authentic-looking handwriting fonts—many of them modeled after historical penmanship—and antique text simulations."

  typography fonts handwriting

• Collective Wisdom — Crooked Timber

  "More broadly, a simple dictum such as ‘listen to the experts’ isn’t going to work, precisely because our most powerful methods of generating new knowledge (viz. the sciences) are not so much based on listening to individual experts, as on including these experts (and many others) in broader social systems which expose them continually to the ideas of others and vice-versa. Designing (or – perhaps better- nurturing) such systems is hard to think about and hard to do – but it has to be the way forward."

  via:arsyed wisdom-of-crowds complexology innovation cultural-assumptions credentialing problem-solving what-is-true-is-what-gets-said

• [1109.1146] A Distributed Mincut/Maxflow Algorithm Combining Path Augmentation and Push-Relabel

  "We develop a novel distributed algorithm for the minimum cut problem. We primarily aim at solving large sparse problems. Assuming vertices of the graph are partitioned into several regions, the algorithm performs path augmentations inside the regions and updates of the push-relabel style between the regions. The interaction between regions is considered expensive (regions are loaded into the memory one-by-one or located on separate machines in a network). The algorithm works in sweeps – passes over all regions. Let $B$ be the set of vertices incident to inter-region edges of the graph. We present a sequential and parallel versions of the algorithm which terminate in at most $2|B|^2+1$ sweeps. The competing algorithm by Delong and Boykov uses push-relabel updates inside regions. In the case of a fixed partition we prove that this algorithm has a tight $O(n^2)$ bound on the number of sweeps, where $n$ is the number of vertices. We tested sequential versions of the algorithms on instances of maxflow problems in computer vision. Experimentally, the number of sweeps required by the new algorithm is much lower than for the Delong and Boykov's variant. Large problems (up to $10^8$ vertices and $6cdot 10^8$ edges) are solved using under 1GB of memory in about 10 sweeps."

  algorithms operations-research nudge-targets

• [1105.4953] A fast nearest neighbor search algorithm based on vector quantization

  "In this article, we propose a new fast nearest neighbor search algorithm, based on vector quantization. Like many other branch and bound search algorithms [1,10], a preprocessing recursively partitions the data set into disjointed subsets until the number of points in each part is small enough. In doing so, a search-tree data structure is built. This preliminary recursive data-set partition is based on the vector quantization of the empirical distribution of the initial data-set. Unlike previously cited methods, this kind of partitions does not a priori allow to eliminate several brother nodes in the search tree with a single test. To overcome this difficulty, we propose an algorithm to reduce the number of tested brother nodes to a minimal list that we call "friend Voronoi cells". The complete description of the method requires a deeper insight into the properties of Delaunay triangulations and Voronoi diagrams"

  algorithms search-algorithms data-analysis nudge-targets

• [1108.0986] A proximal point algorithm for sequential feature extraction applications

  "We propose a proximal point algorithm to solve LAROS problem, that is the problem of finding a "large approximately rank-one submatrix". This LAROS problem is used to sequentially extract features in data. We also develop a new stopping criterion for the proximal point algorithm, which is based on the duality conditions of eps-optimal solutions of the LAROS problem, with a theoretical guarantee. We test our algorithm with two image databases and show that we can use the LAROS problem to extract appropriate common features from these images."

  algorithms image-segmentation feature-extraction nudge-targets

• [1011.2348] Ergodic Control and Polyhedral approaches to PageRank Optimization

  "We study a general class of PageRank optimization problems which consist in finding an optimal outlink strategy for a web site subject to design constraints. We consider both a continuous problem, in which one can choose the intensity of a link, and a discrete one, in which in each page, there are obligatory links, facultative links and forbidden links. We show that the continuous problem, as well as its discrete variant when there are no constraints coupling different pages, can both be modeled by constrained Markov decision processes with ergodic reward, in which the webmaster determines the transition probabilities of websurfers. Although the number of actions turns out to be exponential, we show that an associated polytope of transition measures has a concise representation, from which we deduce that the continuous problem is solvable in polynomial time, and that the same is true for the discrete problem when there are no coupling constraints. We also provide efficient algorithms, adapted to very large networks. Then, we investigate the qualitative features of optimal outlink strategies, and identify in particular assumptions under which there exists a "master" page to which all controlled pages should point. We report numerical results on fragments of the real web graph."

  optimization PageRank operations-research algorithms nudge-targets