11552
[1401.6200] Three Series for the Generalized Golden Mean
As is well-known, the ratio of adjacent Fibonacci numbers tends to phi = (1 + sqrt(5))/2, and the ratio of adjacent Tribonacci numbers (where each term is the sum of the three preceding numbers) tends to the real root eta of X^3 - X^2 - X - 1 = 0. Letting alpha(n) denote the corresponding ratio for the generalized Fibonacci numbers, where each term is the sum of the n preceding, we obtain rapidly converging series for alpha(n), 1/alpha(n), and 1/(2-alpha(n)).
number-theory  approximation  rather-interesting  series  convergence  nudge-targets  consider:evolving-some  consider:performance-measures  consider:convergence  consider:complexity
8 hours ago
[1407.5841] Mechanical Proofs of Properties of the Tribonacci Word
We implement a decision procedure for answering questions about a class of infinite words that might be called (for lack of a better name) "Tribonacci-automatic". This class includes, for example, the famous Tribonacci word T = 0102010010202 ..., the fixed point of the morphism 0 -> 01, 1 -> 02, 2 -> 0. We use it to reprove some old results about the Tribonacci word from the literature, such as assertions about the occurrences in T of squares, cubes, palindromes, and so forth. We also obtain some new results.
formal-languages  strings  automata  representation  feature-construction  rather-interesting  nudge-targets  consider:looking-to-see  consider:rediscovery
yesterday
[1505.00667] An Unusual Continued Fraction
We consider the real number σ with continued fraction expansion [a0,a1,a2,…]=[1,2,1,4,1,2,1,8,1,2,1,4,1,2,1,16,…], where ai is the largest power of 2 dividing i+1. We compute the irrationality measure of σ2 and demonstrate that σ2 (and σ) are both transcendental numbers. We also show that certain partial quotients of σ2 grow doubly exponentially, thus confirming a conjecture of Hanna and Wilson.
continued-fractions  strings  number-theory  rather-interesting  to-understand  nudge-targets  consider:representation
yesterday
[1311.2318] Counting the Palstars
A palstar (after Knuth, Morris, and Pratt) is a concatenation of even-length palindromes. We show that, asymptotically, there are Θ(αnk) palstars of length 2n over a k-letter alphabet, where αk is a constant such that 2k−1<αk<2k−12. In particular, α2≐3.33513193.
strings  feature-construction  classification  nudge-targets  consider:looking-to-see
yesterday
[1612.05320] Minimum Critical Exponents for Palindromes
We determine the minimum possible critical exponent for all palindromes over finite alphabets.
strings  feature-construction  rather-interesting  nudge-targets  consider:rediscovery  to-write-about
yesterday
[1602.06915] Periodicity in Rectangular Arrays
We discuss several two-dimensional generalizations of the familiar Lyndon-Schutzenberger periodicity theorem for words. We consider the notion of primitive array (as one that cannot be expressed as the repetition of smaller arrays). We count the number of m x n arrays that are primitive. Finally, we show that one can test primitivity and compute the primitive root of an array in linear time.
matrices  probability-theory  to-understand  data-structures  rather-interesting  consider:nudge-operators
yesterday
[1509.05240] Periods and borders of random words
We investigate the behavior of the periods and border lengths of random words over a fixed alphabet. We show that the asymptotic probability that a random word has a given maximal border length k is a constant, depending only on k and the alphabet size ℓ. We give a recurrence that allows us to determine these constants with any required precision. This also allows us to evaluate the expected period of a random word. For the binary case, the expected period is asymptotically about n−1.641. We also give explicit formulas for the probability that a random word is unbordered or has maximum border length one.
probability-theory  strings  rather-interesting  consider:Benford's-law?  to-write-about  to-understand
yesterday
[1709.07308] Predicting Positive and Negative Links with Noisy Queries: Theory & Practice
Social networks and interactions in social media involve both positive and negative relationships. Signed graphs capture both types of relationships: positive edges correspond to pairs of "friends", and negative edges to pairs of "foes". The edge sign prediction problem, that aims to predict whether an interaction between a pair of nodes will be positive or negative, is an important graph mining task for which many heuristics have recently been proposed [Leskovec 2010].
We model the edge sign prediction problem as follows: we are allowed to query any pair of nodes whether they belong to the same cluster or not, but the answer to the query is corrupted with some probability 0<q<12. Let δ=1−2q be the bias. We provide an algorithm that recovers all signs correctly with high probability in the presence of noise for any constant gap δ with O(nlognδ4) queries. Our algorithm uses breadth first search as its main algorithmic primitive. A byproduct of our proposed learning algorithm is the use of s−t paths as an informative feature to predict the sign of the edge (s,t). As a heuristic, we use edge disjoint s−t paths of short length as a feature for predicting edge signs in real-world signed networks. Our findings suggest that the use of paths improves the classification accuracy, especially for pairs of nodes with no common neighbors.
network-theory  rather-interesting  inference  feature-construction  algorithms  statistics  nudge-targets  consider:looking-to-see
4 days ago
[1605.04550] Finite-size effects and percolation properties of Poisson geometries
Random tessellations of the space represent a class of prototype models of heterogeneous media, which are central in several applications in physics, engineering and life sciences. In this work, we investigate the statistical properties of d-dimensional isotropic Poisson geometries by resorting to Monte Carlo simulation, with special emphasis on the case d=3. We first analyse the behaviour of the key features of these stochastic geometries as a function of the dimension d and the linear size L of the domain. Then, we consider the case of Poisson binary mixtures, where the polyhedra are assigned two labels' with complementary probabilities. For this latter class of random geometries, we numerically characterize the percolation threshold, the strength of the percolating cluster and the average cluster size.
probability-theory  computational-geometry  statistical-mechanics  looking-to-see  simulation  rather-interesting  feature-extraction  to-write-about
4 days ago
[1709.08071] Autonomous Agents Modelling Other Agents: A Comprehensive Survey and Open Problems
Much research in artificial intelligence is concerned with the development of autonomous agents that can interact effectively with other agents. An important aspect of such agents is the ability to reason about the behaviours of other agents, by constructing models which make predictions about various properties of interest (such as actions, goals, beliefs) of the modelled agents. A variety of modelling approaches now exist which vary widely in their methodology and underlying assumptions, catering to the needs of the different sub-communities within which they were developed and reflecting the different practical uses for which they are intended. The purpose of the present article is to provide a comprehensive survey of the salient modelling methods which can be found in the literature. The article concludes with a discussion of open problems which may form the basis for fruitful future research.
agent-based  collective-behavior  machine-learning  artificial-intelligence  open-problems  nudge-targets  to-write-about
4 days ago
[1709.09876] Communication Complexity of Cake Cutting
We study classic cake-cutting problems, but in discrete models rather than using infinite-precision real values, specifically, focusing on their communication complexity. Using general discrete simulations of classical infinite-precision protocols (Robertson-Webb and moving-knife), we roughly partition the various fair-allocation problems into 3 classes: "easy" (constant number of rounds of logarithmic many bits), "medium" (poly-logarithmic total communication), and "hard". Our main technical result concerns two of the "medium" problems (perfect allocation for 2 players and equitable allocation for any number of players) which we prove are not in the "easy" class. Our main open problem is to separate the "hard" from the "medium" classes.
computational-complexity  game-theory  algorithms  rather-interesting  performance-measure  feature-construction  nudge-targets  consider:classification  consider:reds
4 days ago
[1610.06479] Competition in growth and urns
We study survival among two competing types in two settings: a planar growth model related to two-neighbour bootstrap percolation, and a system of urns with graph-based interactions. In the planar growth model, uncoloured sites are given a colour at rate 0, 1 or ∞, depending on whether they have zero, one, or at least two neighbours of that colour. In the urn scheme, each vertex of a graph G has an associated urn containing some number of either blue or red balls (but not both). At each time step, a ball is chosen uniformly at random from all those currently present in the system, a ball of the same colour is added to each neighbouring urn, and balls in the same urn but of different colours annihilate on a one-for-one basis. We show that, for every connected graph G and every initial configuration, only one colour survives almost surely. As a corollary, we deduce that in the two-type growth model on ℤ2, one of the colours only infects a finite number of sites with probability one. We also discuss generalisations to higher dimensions and multi-type processes, and list a number of open problems and conjectures.
nonlinear-dynamics  probability-theory  rather-interesting  open-questions  to-write-about  nudge-targets  consider:looking-to-see
4 days ago
[1707.06557] leave a trace - A People Tracking System Meets Anomaly Detection
Video surveillance always had a negative connotation, among others because of the loss of privacy and because it may not automatically increase public safety. If it was able to detect atypical (i.e. dangerous) situations in real time, autonomously and anonymously, this could change. A prerequisite for this is a reliable automatic detection of possibly dangerous situations from video data. This is done classically by object extraction and tracking. From the derived trajectories, we then want to determine dangerous situations by detecting atypical trajectories. However, due to ethical considerations it is better to develop such a system on data without people being threatened or even harmed, plus with having them know that there is such a tracking system installed. Another important point is that these situations do not occur very often in real, public CCTV areas and may be captured properly even less. In the artistic project leave a trace the tracked objects, people in an atrium of a institutional building, become actor and thus part of the installation. Visualisation in real-time allows interaction by these actors, which in turn creates many atypical interaction situations on which we can develop our situation detection. The data set has evolved over three years and hence, is huge. In this article we describe the tracking system and several approaches for the detection of atypical trajectories.
amusing  anomaly-detection  computer-vision  surveillance  machine-learning  the-mangle-in-practice  to-write-about
4 days ago
[1611.01164] Sensitive Dependence of Optimal Network Dynamics on Network Structure
The relation between network structure and dynamics is determinant for the behavior of complex systems in numerous domains. An important longstanding problem concerns the properties of the networks that optimize the dynamics with respect to a given performance measure. Here we show that such optimization can lead to sensitive dependence of the dynamics on the structure of the network. Specifically, using diffusively coupled systems as examples, we demonstrate that the stability of a dynamical state can exhibit sensitivity to unweighted structural perturbations (i.e., link removals and node additions) for undirected optimal networks and to weighted perturbations (i.e., small changes in link weights) for directed optimal networks. As mechanisms underlying this sensitivity, we identify discontinuous transitions occurring in the complement of undirected optimal networks and the prevalence of eigenvector degeneracy in directed optimal networks. These findings establish a unified characterization of networks optimized for dynamical stability, which we illustrate using Turing instability in activator-inhibitor systems, synchronization in power-grid networks, network diffusion, and several other network processes. Our results suggest that the network structure of a complex system operating near an optimum can potentially be fine-tuned for a significantly enhanced stability compared to what one might expect from simple extrapolation. On the other hand, they also suggest constraints on how close to the optimum the system can be in practice. Finally, the results have potential implications for biophysical networks, which have evolved under the competing pressures of optimizing fitness while remaining robust against perturbations.
network-theory  nonlinear-dynamics  emergent-design  complexology  rather-interesting  to-write-about  to-simulate  nudge-targets  consider:looking-to-see
4 days ago
[1704.00023] On the Reliable Detection of Concept Drift from Streaming Unlabeled Data
Classifiers deployed in the real world operate in a dynamic environment, where the data distribution can change over time. These changes, referred to as concept drift, can cause the predictive performance of the classifier to drop over time, thereby making it obsolete. To be of any real use, these classifiers need to detect drifts and be able to adapt to them, over time. Detecting drifts has traditionally been approached as a supervised task, with labeled data constantly being used for validating the learned model. Although effective in detecting drifts, these techniques are impractical, as labeling is a difficult, costly and time consuming activity. On the other hand, unsupervised change detection techniques are unreliable, as they produce a large number of false alarms. The inefficacy of the unsupervised techniques stems from the exclusion of the characteristics of the learned classifier, from the detection process. In this paper, we propose the Margin Density Drift Detection (MD3) algorithm, which tracks the number of samples in the uncertainty region of a classifier, as a metric to detect drift. The MD3 algorithm is a distribution independent, application independent, model independent, unsupervised and incremental algorithm for reliably detecting drifts from data streams. Experimental evaluation on 6 drift induced datasets and 4 additional datasets from the cybersecurity domain demonstrates that the MD3 approach can reliably detect drifts, with significantly fewer false alarms compared to unsupervised feature based drift detectors. The reduced false alarms enables the signaling of drifts only when they are most likely to affect classification performance. As such, the MD3 approach leads to a detection scheme which is credible, label efficient and general in its applicability.
online-learning  machine-learning  classification  algorithms  performance-measure  nudge-targets  to-write-about  rather-interesting
4 days ago
[1611.05746] Note on k-planar crossing numbers
The crossing number cr(G) of a graph G=(V,E) is the smallest number of edge crossings over all drawings of G in the plane. For any k≥1, the k-planar crossing number of G, crk(G), is defined as the minimum of cr(G0)+cr(G1)+…+cr(Gk−1) over all graphs G0,G1,…,Gk−1 with ∪k−1i=0Gi=G. It is shown that for every k≥1, we have crk(G)≤(2k2−1k3)cr(G). This bound does not remain true if we replace the constant 2k2−1k3 by any number smaller than 1k2. Some of the results extend to the rectilinear variants of the k-planar crossing number.
graph-theory  feature-construction  algorithms  rather-interesting  nudge-targets  to-write-about  graph-layout
4 days ago
[1709.08461] Mining a Sub-Matrix of Maximal Sum
Biclustering techniques have been widely used to identify homogeneous subgroups within large data matrices, such as subsets of genes similarly expressed across subsets of patients. Mining a max-sum sub-matrix is a related but distinct problem for which one looks for a (non-necessarily contiguous) rectangular sub-matrix with a maximal sum of its entries. Le Van et al. (Ranked Tiling, 2014) already illustrated its applicability to gene expression analysis and addressed it with a constraint programming (CP) approach combined with large neighborhood search (CP-LNS). In this work, we exhibit some key properties of this NP-hard problem and define a bounding function such that larger problems can be solved in reasonable time. Two different algorithms are proposed in order to exploit the highlighted characteristics of the problem: a CP approach with a global constraint (CPGC) and mixed integer linear programming (MILP). Practical experiments conducted both on synthetic and real gene expression data exhibit the characteristics of these approaches and their relative benefits over the original CP-LNS method. Overall, the CPGC approach tends to be the fastest to produce a good solution. Yet, the MILP formulation is arguably the easiest to formulate and can also be competitive.
machine-learning  matrices  mathematical-programming  benchmarking  to-write-about  nudge-targets
4 days ago
The Effect of Compositional Context on Synthetic Gene Net- works | bioRxiv
It is well known that synthetic gene expression is highly sensitive to how genetic elements (promoter structure, spacing regions between promoter and cod- ing sequences, ribosome binding sites, etc.) are spatially configured. An important topic that has received far less attention is how the compositional context, or spatial arrangement, of entire genes within a synthetic gene network affects their individual expression levels. In this paper we show, both quantitatively and qualitatively, that compositional context significantly alters transcription levels in synthetic gene networks. We demonstrate that key characteristics of gene induction, such as ultra-sensitivity and dynamic range, strongly depend on compositional context. We postulate that supercoiling can be used to explain this interference and validate this hypothesis through modeling and a series of in vitro supercoiling relaxation experiments. This compo- sitional interference enables a novel form of feedback in synthetic gene networks. We illustrate the use of this feedback by redesigning the toggle switch to incorporate compositional context. We show the context-optimized toggle switch has improved threshold detection and memory properties.
gene-regulatory-networks  biological-engineering  systems-biology  rather-interesting  synthetic-biology  molecular-design  to-write-about  performance-measure
4 days ago
[1607.05342] On Integer Programming and the Path-width of the Constraint Matrix
In the classic Integer Programming (IP) problem, the objective is to decide whether, for a given m×n matrix A and an m-vector b=(b1,…,bm), there is a non-negative integer n-vector x such that Ax=b. Solving (IP) is an important step in numerous algorithms and it is important to obtain an understanding of the precise complexity of this problem as a function of natural parameters of the input. Two significant results in this line of research are the pseudo-polynomial time algorithms for (IP) when the number of constraints is a constant [Papadimitriou, J. ACM 1981] and when the branch-width of the column-matroid corresponding to the constraint matrix is a constant [Cunningham and Geelen, IPCO 2007]. In this paper, we prove matching upper and lower bounds for (IP) when the path-width of the corresponding column-matroid is a constant. These lower bounds provide evidence that the algorithm of Cunningham and Geelen, are probably optimal. We also obtain a separate lower bound providing evidence that the algorithm of Papadimitriou is close to optimal.
classification  benchmarking  rather-interesting  mathematical-programming  matrices  feature-construction  nudge-targets  consider:rediscovery  consider:performance-measures  computational-complexity
4 days ago
[1610.04041] A resource dependent protein synthesis model for evaluating synthetic circuits
Reliable in-silico design of synthetic gene networks necessitates novel approaches to model the process of protein synthesis under the influence of limited resources. We present such a novel protein synthesis model which originates from the Ribosome Flow Model and among other things describes the movement of RNA-polymerase and Ribosomes on mRNA and DNA templates respectively. By analyzing the convergence properties of this model based upon geometric considerations we present additional insights into the dynamic mechanisms of the process of protein synthesis. Further, we exemplarily show how this model can be used to evaluate the performance of synthetic gene circuits under different loading scenarios.
systems-biology  reaction-networks  engineering-design  emergent-design  biological-engineering  to-write-about  performance-measure  nudge-targets  consider:performance-measures
4 days ago
[1606.07163] Interpretable Machine Learning Models for the Digital Clock Drawing Test
The Clock Drawing Test (CDT) is a rapid, inexpensive, and popular neuropsychological screening tool for cognitive conditions. The Digital Clock Drawing Test (dCDT) uses novel software to analyze data from a digitizing ballpoint pen that reports its position with considerable spatial and temporal precision, making possible the analysis of both the drawing process and final product. We developed methodology to analyze pen stroke data from these drawings, and computed a large collection of features which were then analyzed with a variety of machine learning techniques. The resulting scoring systems were designed to be more accurate than the systems currently used by clinicians, but just as interpretable and easy to use. The systems also allow us to quantify the tradeoff between accuracy and interpretability. We created automated versions of the CDT scoring systems currently used by clinicians, allowing us to benchmark our models, which indicated that our machine learning models substantially outperformed the existing scoring systems.
machine-learning  benchmarking  rather-interesting  nudge-targets  consider:representation  consider:looking-to-see
4 days ago
Objectivity and Distant Reading · Ryan Cordell
I was drawn to read Objectivity as part of my growing interest, following the work of scholars such as Lauren Klein or Jacqueline Wernimont, in pre-histories of computing: around ideas of information, data, programming, quantification, or visualization. I am drawn to such work because I believe deep historicization can help build a more robust and integrative digital humanities. In such a DH computation—and in this post that word is, admittedly, doing too much work, but—in such a DH computation would not be simply a powerful modern tool applied to the past or, equally simply, an impoverished neoliberal framework incommensurate with the nuances of the past. Instead, computation would be both subject and methodology, both of history and capable of dialogue with history. More robust historical contextualization can, I believe, assist on all sides of the DH debates, mitigating both the millennial and apocalyptic rhetoric swirling around the field.
history-of-science  objectivity  philosophy-of-science  books  to-read  rather-interesting
4 days ago
[1709.02015] The microstructure of high frequency markets
We present a novel approach to describing the microstructure of high frequency trading using two key elements. First we introduce a new notion of informed trader which we starkly contrast to current informed trader models. We describe the exact nature of the superior information' high frequency traders have access to, and how these agents differ from the more standard insider traders' described in past papers. This then leads to a model and an empirical analysis of the data which strongly supports our claims. The second key element is a rigorous description of clearing conditions on a limit order book and how to derive correct formulas for such a market. From a theoretical point of view, this allows the exact identification of two frictions in the market, one of which is intimately linked to our notion of superior information'. Empirically, we show that ignoring these frictions can misrepresent the wealth exchanged on the market by 50%. Finally, we showcase two applications of our approach: we measure the profits made by high frequency traders on NASDAQ and re-visit the standard Black - Scholes model to determine how trading frictions alter the delta-hedging strategy.
financial-engineering  planning  trading  agent-based  economics  horse-races  rather-interesting  nudge-targets  consider:looking-to-see  consider:rediscovery
4 days ago
Counting Your Chickens Before They’re Pecked | bit-player
It started with a brief story in the New York Times about Luke Robitaille, a 13-year-old student from Euless, Texas, who won the Raytheon Mathcounts National Competition by correctly answering the following question:
In a barn, 100 chicks sit peacefully in a circle. Suddenly, each chick randomly pecks the chick immediately to its left or right. What is the expected number of unpecked chicks?
mathematical-recreations  probability-theory  simulation  learning-in-public  rather-interesting  to-write-about
4 days ago
[1501.03992] PSPACE-Completeness of Majority Automata Networks
We study the dynamics of majority automata networks when the vertices are updated according to a block sequential updating scheme. In particular, we show that the complexity of the problem of predicting an eventual state change in some vertex, given an initial configuration, is PSPACE-complete.
cellular-automata  computational-complexity  prediction  nudge-targets  consider:looking-to-see  to-write-about
4 days ago
[1602.01241] Using separable non-negative matrix factorization techniques for the analysis of time-resolved Raman spectra
The key challenge of time-resolved Raman spectroscopy is the identification of the constituent species and the analysis of the kinetics of the underlying reaction network. In this work we present an integral approach that allows for determining both the component spectra and the rate constants simultaneously from a series of vibrational spectra. It is based on an algorithm for non-negative matrix factorization which is applied to the experimental data set following a few pre-processing steps. As a prerequisite for physically unambiguous solutions, each component spectrum must include one vibrational band that does not significantly interfere with vibrational bands of other species. The approach is applied to synthetic "experimental" spectra derived from model systems comprising a set of species with component spectra differing with respect to their degree of spectral interferences and signal-to-noise ratios. In each case, the species involved are connected via monomolecular reaction pathways. The potential and limitations of the approach for recovering the respective rate constants and component spectra are discussed.
spectroscopy  data-analysis  inference  numerical-methods  modeling  statistics  rather-interesting  nudge-targets  consider:representation
4 days ago
How to Set Up and Get Started with Your Synology NAS
Synology offers a very user friendly Network Attached Storage (NAS) device experience, but that doesn’t mean unboxing it and starting it up is exactly a one-click affair. Let’s get things up and running so we can move onto all the fun projects a compact NAS with server-like functionality can facilitate.
4 days ago
[1710.04247] Lagrange's Theorem for Binary Squares
We prove, using a decision procedure based on finite automata, that every natural number > 686 is the sum of at most 4 natural numbers whose canonical base-2 representation is a binary square, that is, a string of the form xx for some block of bits x.
5 days ago
[1604.03159] Phase Transitions and a Model Order Selection Criterion for Spectral Graph Clustering
One of the longstanding open problems in spectral graph clustering (SGC) is the so-called model order selection problem: automated selection of the correct number of clusters. This is equivalent to the problem of finding the number of connected components or communities in an undirected graph. We propose automated model order selection (AMOS), a solution to the SGC model selection problem under a random interconnection model (RIM) using a novel selection criterion that is based on an asymptotic phase transition analysis. AMOS can more generally be applied to discovering hidden block diagonal structure in symmetric non-negative matrices. Numerical experiments on simulated graphs validate the phase transition analysis, and real-world network data is used to validate the performance of the proposed model selection procedure.
network-theory  clustering  community-detection  algorithms  performance-measure  rather-interesting  consider:looking-to-see  consider:performance-measures
7 days ago
[1705.08617] Which bridge estimator is optimal for variable selection?
We study the problem of variable selection for linear models under the high dimensional asymptotic setting, where the number of observations n grows at the same rate as the number of predictors p. We consider two stage variable selection techniques (TVS) in which the first stage uses bridge estimators to obtain an estimate of the regression coefficients, and the second stage simply thresholds the regression coefficients estimate to select the "important" predictors. The asymptotic false discovery proportion (AFDP) and true positive proportion (ATPP) of these TVS are evaluated. We prove that for a fixed ATTP, in order to obtain the smallest AFDP one should pick an estimator that minimizes the asymptotic mean square error in the first stage of TVS. This simple observation enables us to evaluate and compare the performances of different TVS with each other and with some standard variable selection techniques, such as LASSO and Sure Independence Screening. For instance, we prove that a TVS with LASSO in its first stage can outperform LASSO (only one stage) in a large range of ATTP. Furthermore, we will show that for large values of noise, a TVS with ridge in its first stage outperforms TVS with other bridge estimators including the one that has LASSO in its first stage.
variable-selection  modeling  algorithms  statistics  nudge-targets  consider:looking-to-see
7 days ago
[1608.08225] Why does deep and cheap learning work so well?
We show how the success of deep learning could depend not only on mathematics but also on physics: although well-known mathematical theorems guarantee that neural networks can approximate arbitrary functions well, the class of functions of practical interest can frequently be approximated through "cheap learning" with exponentially fewer parameters than generic ones. We explore how properties frequently encountered in physics such as symmetry, locality, compositionality, and polynomial log-probability translate into exceptionally simple neural networks. We further argue that when the statistical process generating the data is of a certain hierarchical form prevalent in physics and machine-learning, a deep neural network can be more efficient than a shallow one. We formalize these claims using information theory and discuss the relation to the renormalization group. We prove various "no-flattening theorems" showing when efficient linear deep networks cannot be accurately approximated by shallow ones without efficiency loss, for example, we show that n variables cannot be multiplied using fewer than 2^n neurons in a single hidden layer.
deep-learning  machine-learning  approximation  looking-to-see  algorithms  representation  rather-interesting  learning-algorithms  information-theory  to-write-about
7 days ago
[1610.07277] Rapid calculation of side chain packing and free energy with applications to protein molecular dynamics
To address the large gap between time scales that can be easily reached by molecular simulations and those required to understand protein dynamics, we propose a rapid self-consistent approximation of the side chain free energy at every integration step. In analogy with the adiabatic Born-Oppenheimer approximation for electronic structure, the protein backbone dynamics are simulated as preceding according to the dictates of the free energy of an instantaneously-equilibrated side chain potential. The side chain free energy is computed on the fly, allowing the protein backbone dynamics to traverse a greatly smoothed energetic landscape. This results in extremely rapid equilibration and sampling of the Boltzmann distribution. Because our method employs a reduced model involving single-bead side chains, we also provide a novel, maximum-likelihood method to parameterize the side chain model using input data from high resolution protein crystal structures. We demonstrate state-of-the-art accuracy for predicting χ1 rotamer states while consuming only milliseconds of CPU time. We also show that the resulting free energies of side chains is sufficiently accurate for de novo folding of some proteins.
structural-biology  approximation  heuristics  algorithms  protein-folding  to-write-about  nudge-targets
7 days ago
[1702.03286] The Beneficial Role of Mobility for the Emergence of Innovation
Innovation is a key ingredient for the evolution of several systems, including social and biological ones. Focused investigations and lateral thinking may lead to innovation, as well as serendipity and other random discovery processes. Some individuals are talented at proposing innovation (say innovators), while others at deeply exploring proposed novelties, at getting further insights on a theory, or at developing products, services, and so on (say developers). This separation in terms of innovators and developers raises an issue of paramount importance: under which conditions a system is able to maintain innovators? According to a simple model, this work investigates the evolutionary dynamics that characterize the emergence of innovation. In particular, we consider a population of innovators and developers, in which agents form small groups whose composition is crucial for their payoff. The latter depends on the heterogeneity of the formed groups, on the amount of innovators they include, and on an award-factor that represents the policy of the system for promoting innovation. Under the hypothesis that a "mobility" effect may support the emergence of innovation, we compare the equilibria reached by our population in different cases. Results confirm the beneficial role of "mobility", and the emergence of further interesting phenomena.
innovation  agent-based  simulation  community-assembly  organizational-behavior  to-write-about
7 days ago
Discovery in mathematics is a prototypical intelligent behavior, and an early and continuing goal of artificial intelligence research. We present a heuristic for producing mathematical conjectures of a certain typical form and demonstrate its utility. Our program conjectures relations that hold between properties of objects (property-relation conjectures). These objects can be of a wide variety of types. The statements are true for all objects known to the program, and are the simplest statements which are true of all these objects. The examples here include new conjectures for the hamiltonicity of a graph, a well-studied property of graphs. While our motivation and experiments have been to produce mathematical conjectures—and to contribute to mathematical research—other kinds of interesting property-relation conjectures can be imagined, and this research may be more generally applicable to the development of intelligent machinery.
automated-conjecture  exploration  mathematics  machine-learning  algorithms  representation  performance-measure  nudge-targets  old-project
7 days ago
On the notion of interestingness in automated mathematical discovery - ScienceDirect
We survey five mathematical discovery programs by looking in detail at the discovery processes they illustrate and the success they had. We focus on how they estimate the interestingness of concepts and conjectures and extract some common notions about interestingness in automated mathematical discovery. We detail how empirical evidence is used to give plausibility to conjectures, and the different ways in which a result can be thought of as novel. We also look at the ways in which the programs assess how surprising and complex a conjecture statement is, and the different ways in which the applicability of a concept or conjecture is used. Finally, we note how a user can set tasks for the program to achieve and how this affects the calculation of interestingness. We conclude with some hints on the use of interestingness measures for future developers of discovery programs in mathematics.
mathematics  machine-learning  automated-conjecture  exploration  novelty-search  performance-measure  nudge-targets  old-ideas
7 days ago
The Destruction of the 3rd World | Ian Welsh
The but is that they want you to stop subsidies of food and let food prices float.  Then they want you to reduce tariffs on goods, even though tariffs are a huge source of tax revenue, because your government is crippled and your people have tiny incomes, so you really don’t have the ability to tax them.  Then they want you to open up your economy to foreigners buying it up, so foreigners can own every part of your economy worth having (anything that generates hard currency, basically.)
public-policy  economics  colonialism
8 days ago
Math Notes - Futility Closet
Can a sum of such fractions produce any natural number? That’s conjectured — but so far unproven.
number-theory  continued-fractions  mathematical-recreations  open-questions  nudge-targets  consider:looking-to-see  consider:performance-measures
8 days ago
[1012.1128] Yet another aperiodic tile set
We present here an elementary construction of an aperiodic tile set. Although there already exist dozens of examples of aperiodic tile sets we believe this construction introduces an approach that is different enough to be interesting and that the whole construction and the proof of aperiodicity are hopefully simpler than most existing techniques.
tiling  aperiodic-tiling  construction  rather-interesting  mathematical-recreations  to-write-about  to-simulate  consider:expanding
8 days ago
[1610.00323] L-Convex Polyominoes are Recognizable in Real Time by 2D Cellular Automata
A polyomino is said to be L-convex if any two of its cells are connected by a 4-connected inner path that changes direction at most once. The 2-dimensional language representing such polyominoes has been recently proved to be recognizable by tiling systems by S. Brocchi, A. Frosini, R. Pinzani and S. Rinaldi. In an attempt to compare recognition power of tiling systems and cellular automata, we have proved that this language can be recognized by 2-dimensional cellular automata working on the von Neumann neighborhood in real time.
Although the construction uses a characterization of L-convex polyominoes that is similar to the one used for tiling systems, the real time constraint which has no equivalent in terms of tilings requires the use of techniques that are specific to cellular automata.
polyominoes  cellular-automata  fun  rather-interesting  algorithms  nonstandard-computation  classification  nudge-targets  consider:looking-to-see  to-write-about
8 days ago
[1701.00146] Even $1 times n$ Edge-Matching and Jigsaw Puzzles are Really Hard
We prove the computational intractability of rotating and placing n square tiles into a 1×n array such that adjacent tiles are compatible--either equal edge colors, as in edge-matching puzzles, or matching tab/pocket shapes, as in jigsaw puzzles. Beyond basic NP-hardness, we prove that it is NP-hard even to approximately maximize the number of placed tiles (allowing blanks), while satisfying the compatibility constraint between nonblank tiles, within a factor of 0.9999999851. (On the other hand, there is an easy 12-approximation.) This is the first (correct) proof of inapproximability for edge-matching and jigsaw puzzles. Along the way, we prove NP-hardness of distinguishing, for a directed graph on n nodes, between having a Hamiltonian path (length n−1) and having at most 0.999999284(n−1) edges that form a vertex-disjoint union of paths. We use this gap hardness and gap-preserving reductions to establish similar gap hardness for 1×n jigsaw and edge-matching puzzles.
puzzles  combinatorics  computational-complexity  nudge-targets  consider:looking-to-see  consider:intermediate-results
8 days ago
Riddled: Your master he's a monster He will come on a bridge of paper Inscribed with a hundred names of God
UPDATE: Helpful Pubpeer brownie Macrophthalmus Grandidieri prepared a useful though now incomplete diagram of papers and their shared pictorial heritage, including twenty-seven 8-by-10 color glossy pictures with circles and arrows and a paragraph on the back of each one explaining what each one was.
8 days ago
[1704.08292] Deep Cross-Modal Audio-Visual Generation
Cross-modal audio-visual perception has been a long-lasting topic in psychology and neurology, and various studies have discovered strong correlations in human perception of auditory and visual stimuli. Despite works in computational multimodal modeling, the problem of cross-modal audio-visual generation has not been systematically studied in the literature. In this paper, we make the first attempt to solve this cross-modal generation problem leveraging the power of deep generative adversarial training. Specifically, we use conditional generative adversarial networks to achieve cross-modal audio-visual generation of musical performances. We explore different encoding methods for audio and visual signals, and work on two scenarios: instrument-oriented generation and pose-oriented generation. Being the first to explore this new problem, we compose two new datasets with pairs of images and sounds of musical performances of different instruments. Our experiments using both classification and human evaluations demonstrate that our model has the ability to generate one modality, i.e., audio/visual, from the other modality, i.e., visual/audio, to a good extent. Our experiments on various design choices along with the datasets will facilitate future research in this new problem space.
deep-learning  neural-networks  generative-art  generative-models  rather-interesting  video  computer-vision  nudge-targets  consider:rediscovery
8 days ago
Laudator Temporis Acti: The Pleasure of Reading
I myself, even though I have no greater pleasure than reading, indeed I have no others, and in whom the pleasure of reading is so great that since my earliest childhood I have always followed this habit (and habit is what produces the pleasure), when I have sometimes, in a moment of idleness, settled down to read some book simply to pass the time, and for the sole and express purpose of finding pleasure and delight, I have always discovered, not without surprise and regret, that not only did I experience no delight at all, but I felt boredom and distaste from the very beginning. And therefore I went immediately to change books, but without any benefit, until in desperation I stopped reading, fearing that it had become dull and disagreeable to me forever, and that I would no longer find pleasure in it. But the pleasure returned to me as soon as I took it up again as an occupation, and as a way of studying, and in order to learn something, or to generally improve my knowledge, without any particular purpose of enjoyment. Therefore, those books which I have enjoyed least, and which for some time now I no longer have the habit of reading, have always been those which are described, [4274] as if with their proper name, as amusements and pastimes. (6 April 1827.)
8 days ago
New Shapes Solve Infinite Pool-Table Problem | Quanta Magazine
Two “rare jewels” have illuminated a mysterious multidimensional object that connects a huge variety of mathematical work.
dynamical-systems  geometry  rather-interesting  mathematical-recreations  nudge-targets  consider:looking-to-see  consider:feature-discovery
8 days ago
[1705.08743] Fast algorithms for anti-distance matrices as a generalization of Boolean matrices
We show that Boolean matrix multiplication, computed as a sum of products of column vectors with row vectors, is essentially the same as Warshall's algorithm for computing the transitive closure matrix of a graph from its adjacency matrix.
Warshall's algorithm can be generalized to Floyd's algorithm for computing the distance matrix of a graph with weighted edges. We will generalize Boolean matrices in the same way, keeping matrix multiplication essentially equivalent to the Floyd-Warshall algorithm. This way, we get matrices over a semiring, which are similar to the so-called "funny matrices".
We discuss our implementation of operations on Boolean matrices and on their generalization, which make use of vector instructions.
matrices  algorithms  graph-theory  rather-interesting  insight  nudge-targets  consider:looking-to-see
8 days ago
An obscure copyright law is letting the Internet Archive distribute books published 1923-1941 / Boing Boing
Section 108h of the Copyright Act gives libraries the power to scan and serve copies of out-of-print books published between 1923 and 1941; it's never been used before but now the mighty Internet Archive is giving it a serious workout, adding them to their brilliantly named Sonny Bono Memorial Collection (when Bono was a Congressman, he tried to pass a law that would extend copyright to "forever less a day" and was instrumental in moving millions of works from the public domain back into copyright, "orphaning" them so that no one could preserve them and no one knew who the copyrights belonged to).
8 days ago
Visualizing Intersecting Sets
Understanding relationships between sets is an important analysis task. The major challenge in this context is the combinatorial explosion of the number of set intersections if the number of sets exceeds a trivial threshold. To address this, we introduce UpSet, a novel visualization technique for the quantitative analysis of sets, their intersections, and aggregates of intersections.
visualization  set-theory  data-analysis  rather-interesting  to-write-about  to-do
8 days ago
HLF Blogs – Math ⇔ Art: what is a rotogon? | The Aperiodical
This animation (Eli Spizzichino, 2017) shows a cube being simultaneously rotated around all its edges. You can see the complex shapes created inside the object, before they’re finally covered by the outside layers of the shape as the cube completes its rotation.

One of the artworks in the exhibit shows a cross-sectional slice through one such shape – a rotogon based on a heptagon. Cross-sections like this reveal the internal structure of the shape and create beautiful images. Spizzichino points out that these internal slices are equivalent to looking at the pieces of the shape part-way through the rotating process.
mathematical-recreations  geometry  rather-interesting  art  mathematics
8 days ago
On reciprocal causation in the evolutionary process | bioRxiv
Recent calls for a revision the standard evolutionary theory (ST) are based on arguments about the reciprocal causation of evolutionary phenomena. Reciprocal causation means that cause-effect relationships are obscured, as a cause could later become an effect and vice versa. Such dynamic cause-effect relationships raises questions about the distinction between proximate and ultimate causes, as originally formulated by Ernst Mayr. They have also motivated some biologists and philosophers to argue for an Extended Evolutionary Synthesis (EES). Such an EES will supposedly replace the Modern Synthesis (MS), with its claimed focus on unidirectional causation. I critically examine this conjecture by the proponents of the EES, and conclude, on the contrary, that reciprocal causation has long been recognized as important in ST and in the MS tradition. Numerous empirical examples of reciprocal causation in the form of positive and negative feedbacks now exists from both natural and laboratory systems. Reciprocal causation has been explicitly incorporated in mathematical models of coevolutionary arms races, frequency-dependent selection and sexual selection. Such feedbacks were already recognized by Richard Levins and Richard Lewontin, long before the call for an EES and the associated concept of niche construction. Reciprocal causation and feedbacks is therefore one of the few contributions of dialectical thinking and Marxist philosophy in evolutionary theory, and should be recognized as such. While reciprocal causation have helped us to understand many evolutionary processes, I caution against its extension to heredity and directed development if such an extension involves futile attempts to restore Lamarckian or soft inheritance.
theoretical-biology  evolutionary-biology  cause-and-effect  philosophy-of-science
8 days ago
[1601.04798] Scale-aware Pixel-wise Object Proposal Networks
Object proposal is essential for current state-of-the-art object detection pipelines. However, the existing proposal methods generally fail in producing results with satisfying localization accuracy. The case is even worse for small objects which however are quite common in practice. In this paper we propose a novel Scale-aware Pixel-wise Object Proposal (SPOP) network to tackle the challenges. The SPOP network can generate proposals with high recall rate and average best overlap (ABO), even for small objects. In particular, in order to improve the localization accuracy, a fully convolutional network is employed which predicts locations of object proposals for each pixel. The produced ensemble of pixel-wise object proposals enhances the chance of hitting the object significantly without incurring heavy extra computational cost. To solve the challenge of localizing objects at small scale, two localization networks which are specialized for localizing objects with different scales are introduced, following the divide-and-conquer philosophy. Location outputs of these two networks are then adaptively combined to generate the final proposals by a large-/small-size weighting network. Extensive evaluations on PASCAL VOC 2007 show the SPOP network is superior over the state-of-the-art models. The high-quality proposals from SPOP network also significantly improve the mean average precision (mAP) of object detection with Fast-RCNN framework. Finally, the SPOP network (trained on PASCAL VOC) shows great generalization performance when testing it on ILSVRC 2013 validation set.
image-processing  image-segmentation  rather-interesting  representation  nudge-targets  consider:looking-to-see  neural-networks
8 days ago
The Moldbug Variations | Corey Pein
To be enlightened, in Yarvin’s world, means forming an uncomfortable alliance with street Nazis—the Stormfront set—and other déclassé white nationalists. The same goes for right-wing terrorists such as Anders Behring Breivik, whom Yarvin denounced, but only in the most limited and depraved terms possible. Yarvin wrote that Breivik should be condemned because his 2011 massacre in Oslo was ineffective as terrorism, which Yarvin considers a legitimate military tactic. Nazi terror was legitimate because it worked, Yarvin wrote. Breivik’s killing spree, which targeted young Norwegian leftists, was illegitimate because it was insufficient to “free Norway from Eurocommunism.” After all, he only killed ninety-two people! “We can note the only thing he didn’t screw up. At least he shot communists, not Muslims. He gored the matador and not the cape,” Yarvin wrote on July 23, 2011, one day after the terror in Oslo, and five years before going to Thiel’s house to hang out and watch their guy, Trump, get closer to power.
startup-culture-must-die  fascism  not-surprising  ideology
9 days ago
[1708.03146] Zero resistance from one atmosphere to the pressure of earth's outer core in a superconducting high entropy alloy
We report the observation of extraordinarily robust zero-resistance superconductivity in the pressurized (TaNb)0.67(HfZrTi)0.33 high entropy alloy - a new kind of material with a body-centered cubic crystal structure made from five randomly distributed transition metal elements. The transition to superconductivity (TC) increases from an initial temperature of 7.7 K at ambient pressure to 10 K at ~ 60 GPa, and then slowly decreases to 9 K by 190.6 GPa, a pressure that falls within that of the outer core of the earth. We infer that the continuous existence of the zero-resistance superconductivity from one atmosphere up to such a high pressure requires a special combination of electronic and mechanical characteristics. This high entropy alloy superconductor thus may have a bright future for applications under extreme conditions, and also poses a challenge for understanding the underlying quantum physics.
superconductors  materials-science  indistinguishable-from-magic  combinatorics  to-write-about  rather-interesting
10 days ago
Sylver Coinage - Futility Closet
This curious game was invented by Princeton mathematician John H. Conway. Two players take turns naming positive integers, but an integer is off limits if it’s the sum of nonnegative multiples of integers that have already been named. Once 1 is named, everything is off limits (because any positive integer is a sum of 1s), so that ends the game; the player who is forced to name 1 is the loser. An example gives the idea:
game-theory  number-theory  rather-interesting  mathematical-recreations  nudge-targets  consider:looking-to-see
10 days ago
Books and the ‘Boredom Boom’ - The New York Times
If there is a lesson imparted by boredom studies, it is that there are hundreds of kinds of boredom. Herman Melville or David Foster Wallace or Danya Ruttenberg can plunge you into a thick soup of micro-details and jargon. Manoush Zomorodi can mediate your media in two mediums. Book reviewers like me can talk about themselves as much as the books we write about.

All this variety should be a balm, no? Whether you view boredom as the graveyard of your spirit, or as a lull before the gorgeous storm, knowing that you can always shift to another flavor of dullness is a kind of succor. Sippy cups for whale anatomy; ethico-politcal praxis for repetitive personal anecdotes. As Ms. Ruttenberg might put it, the promise of the new is the nuance of the now. Interesting.
10 days ago
Dear tech world, STEMism is hurting us | VentureBeat
The idea that the tech world is comprised exclusively of techies is a myth. People with humanities and art degrees (aka “fuzzies”) are crucial players in the innovation space.
two-cultures  startup-culture-must-die  STEMism  liberal-arts  work-is-not-programming  work-is-social  worklife  American-cultural-assumptions  technocracy
10 days ago
[1602.04967] Strongly Universal Reversible Gate Sets
It is well-known that the Toffoli gate and the negation gate together yield a universal gate set, in the sense that every permutation of {0,1}n can be implemented as a composition of these gates. Since every bit operation that does not use all of the bits performs an even permutation, we need to use at least one auxiliary bit to perform every permutation, and it is known that one bit is indeed enough. Without auxiliary bits, all even permutations can be implemented. We generalize these results to non-binary logic: If A is a finite set of odd cardinality then a finite gate set can generate all permutations of An for all n, without any auxiliary symbols. If the cardinality of A is even then, by the same argument as above, only even permutations of An can be implemented for large n, and we show that indeed all even permutations can be obtained from a finite universal gate set. We also consider the conservative case, that is, those permutations of An that preserve the weight of the input word. The weight is the vector that records how many times each symbol occurs in the word. It turns out that no finite conservative gate set can, for all n, implement all conservative even permutations of An without auxiliary bits. But we provide a finite gate set that can implement all those conservative permutations that are even within each weight class of An.
automata  non-binary-representation  representation  engineering-design  formal-languages  rather-interesting  distributed-processing  digital-processing  nudge-targets  consider:performance-measures  combinatorics
10 days ago
[1709.05701] Transkingdom Networks: A Systems Biology Approach to Identify Causal Members of Host-Microbiota Interactions
Improvements in sequencing technologies and reduced experimental costs have resulted in a vast number of studies generating high-throughput data. Although the number of methods to analyze these "omics" data has also increased, computational complexity and lack of documentation hinder researchers from analyzing their high-throughput data to its true potential. In this chapter we detail our data-driven, transkingdom network (TransNet) analysis protocol to integrate and interrogate multi-omics data. This systems biology approach has allowed us to successfully identify important causal relationships between different taxonomic kingdoms (e.g. mammals and microbes) using diverse types of data.
rather-interesting  bioinformatics  community-detection  symbiosis  machine-learning  to-write-about  consider:feature-discovery
10 days ago
[1606.07467] Efficient Analog Circuits for Boolean Satisfiability
Efficient solutions to NP-complete problems would significantly benefit both science and industry. However, such problems are intractable on digital computers based on the von Neumann architecture, thus creating the need for alternative solutions to tackle such problems. Recently, a deterministic, continuous-time dynamical system (CTDS) was proposed (Nat.Phys. {\bf 7}(12), 966 (2011)) to solve a representative NP-complete problem, Boolean Satisfiability (SAT). This solver shows polynomial analog time-complexity on even the hardest benchmark k-SAT (k≥3) formulas, but at an energy cost through exponentially driven auxiliary variables. This paper presents a novel analog hardware SAT solver, AC-SAT, implementing the CTDS via incorporating novel, analog circuit design ideas. AC-SAT is intended to be used as a co-processor and is programmable for handling different problem specifications. It is especially effective for solving hard k-SAT problem instances that are challenging for algorithms running on digital machines. Furthermore, with its modular design, AC-SAT can readily be extended to solve larger size problems, while the size of the circuit grows linearly with the product of the number of variables and number of clauses. The circuit is designed and simulated based on a 32nm CMOS technology. SPICE simulation results show speedup factors of ∼104 on even the hardest 3-SAT problems, when compared with a state-of-the-art SAT solver on digital computers. As an example, for hard problems with N=50 variables and M=212 clauses, solutions are found within from a few ns to a few hundred ns.
very-nice  satisfiability  representation  out-of-the-box  analog-circuits  nudge-targets  consider:looking-to-see  evolvable  to-write-about
10 days ago
[1708.08377] Two-Dimensional Indirect Binary Search for the Positive One-in-Three Satisfiability Problem
In this paper, we propose an algorithm for the positive one-in-three satisfiability problem (Pos1in3SAT). The proposed algorithm can efficiently decide the existence of a satisfying assignment in all assignments for a given formula by using a 2-dimensional binary search method without constructing an exponential number of assignments.
satisfiability  algorithms  computational-complexity  machine-learning  nudge-targets  consider:looking-to-see  consider:representation  matrices
10 days ago
[1709.04524] Workflow Complexity for Collaborative Interactions: Where are the Metrics? -- A Challenge
In this paper, we introduce the problem of denoting and deriving the complexity of workflows (plans, schedules) in collaborative, planner-assisted settings where humans and agents are trying to jointly solve a task. The interactions -- and hence the workflows that connect the human and the agents -- may differ according to the domain and the kind of agents. We adapt insights from prior work in human-agent teaming and workflow analysis to suggest metrics for workflow complexity. The main motivation behind this work is to highlight metrics for human comprehensibility of plans and schedules. The planning community has seen its fair share of work on the synthesis of plans that take diversity into account -- what value do such plans hold if their generation is not guided at least in part by metrics that reflect the ease of engaging with and using those plans?
computational-complexity  performance-measure  to-understand  what-gets-measured-gets-fudged  nudge  to-write-about  engineering-design  philosophy-of-engineering  machine-learning  artificial-intelligence
10 days ago
Cumulative Computing - ScienceDirect
In this paper we use the concept of resource cumulation to model various forms of computation. The space of cumulations (called a cumulator) is simply represented as a five tuple consisting of a well-founded partial order, a monoid and a volume function. The volume function is introduced to simplify reasoning about limit points and other topological properties. A specification command is a set of cumulations. Typical phenomena of concurrency such as reactiveness, safety and liveness, fairness, real time and branching time naturally arise from the model. In order to support a programming theory, we introduce a specification language that incorporates sequentiality, nondeterminism, simple parallelism, negation and general recursions. A new fixpoint technique is used to model general recursions. The language is applied to the case study on CSP, which becomes a special model of cumulative computing with a combination of four resource cumulators of alphabet, termination, trace and refusal. All laws of cumulative computing are also valid for CSP and the generalization from CSP to Timed CSP can be achieved by simply combining the four cumulators with real time. Loops whose bodies may take zero time can then be modeled more satisfactorily.
computer-science  to-understand  concurrency  representation
10 days ago
[1205.6460] A Combinatorial Approach to Positional Number Systems
Although the representation of the real numbers in terms of a base and a set of digits has a long history, new questions arise even in simple situations. This paper concerns binary radix systems, i.e., positional number systems with digits 0 and 1. Our combinatorial approach is to construct infinitely many binary radix systems, each one from a single pair of binary strings. Every binary radix system that satisfies even a minimal set of conditions that would be expected of a positional number system can be constructed in this way.
combinatorics  number-theory  representation  to-understand  rather-interesting  mathematical-recreations
10 days ago
[1610.03839] Variational approximation of functionals defined on 1-dimensional connected sets: the planar case
In this paper we consider variational problems involving 1-dimensional connected sets in the euclidean plane, such as the classical Steiner tree problem and the irrigation (Gilbert-Steiner) problem. We relate them to optimal partition problems and provide a variational approximation through Modica-Mortola type energies proving a full Γ-convergence result. We also introduce a suitable convex relaxation and develop the corresponding numerical implementations. The proposed methods are quite general and the results we obtain can be extended to n-dimensional euclidean space or to more general manifold ambients, as shown in the companion paper [11].
optimization  operations-research  computational-geometry  continuous-functions  algorithms  relaxations  rather-interesting  nudge-targets  consider:rediscovery
11 days ago
How Neill Blomkamp and Unity are shaping the future of filmmaking - The Verge
The advantage for Oats is that the software helped streamline the studio’s filmmaking efforts. “The biggest thing for me was the cameras,” Blomkamp says. “If you’re working live-action, you have no choice but to work with what you shot six months earlier.” And if a shot comes across badly, directors are stuck with the results, unless they have the time and resources to go back and reshoot. With Unity, Blomkamp explains, he can make shot adjustments immediately. In this particular short film, he says Oats started the film with harsh overhead lighting, but later changed the position of the sun, which led to softer, more appealing visuals.
animation  visualization  filmmaking  rather-interesting  via:?
11 days ago
Story Curves
A nonlinear narrative is a storytelling device that portrays events of a story out of chronological order, e.g., in reverse order or going back and forth between past and future events. Story curves visualize the nonlinear narrative of a movie by showing the order in which events are told in the movie and comparing them to their actual chronological order, resulting in possibly meandering visual patterns in the curve. We also developed Story Explorer, an interactive tool that visualizes a story curve together with complementary information such as characters and settings. Story Explorer further provides a script curation interface that allows users to specify the chronological order of events in movies. We used Story Explorer to analyze 10 popular nonlinear movies and describe the spectrum of narrative patterns that we discovered, including some novel patterns not previously described in the literature.
PDF
digital-humanities  visualization  narrative  rather-interesting  to-understand  to-write-about
11 days ago
The GOP's Evolution into a True Fascist, White Nationalist Party Is Inevitable :: Politics :: Features :: Republicanism :: Paste
Led by Mitch McConnell and John Boehner, the party made the cynical decision to oppose Obama’s entire agenda in the midst of a harrowing and dislocating recession. They embraced groups like Americans for Prosperity, backed by those cardboard-cutout billionaire villains, the Koch Brothers, which in turn fomented the Tea Party movement. Supposedly these groups were about tax and spending issues and had no racial agenda—or at least that’s what the National Review would claim every time crowds showed up with overtly racist signs. The fearsome animus of the 2008 election, uncorked by Sarah Palin’s embarrassing tenure as John McCain’s running mate, forewarned of a malevolent turn in Republican messaging: Obama was alien, a foreigner, a radical, a socialist, a Muslim—whatever fit in the moment. As a sideshow, a dipshit reality show host injected the “birther” conspiracy theory with fresh life and media attention every time it threatened to vanish into the dumber corners of the internet.

The Republicans rode this backlash to a stunning victory in 2010. White Americans saw in Obama the very real changing demographic nature of the country. Each presidential election cycle, the potential non-white electorate grows by roughly 2%. The Census Bureau estimates that the minorities will become 56% of the population by 2060. Minorities will become the nation’s majority. Given this, perhaps a resurgence of white identity politics was inevitable, but the way it manifested in the halls of power could have been averted.
fascism  corporatism  politics  ayup
11 days ago
We’re probably due for another discussion of Stanley Fish | The Stone and the Shell
Of course, if you pursue that approach systematically enough, it will lead you away from topic modeling toward methods that rely more explicitly on human judgment. I have been leaning on supervised algorithms a lot lately—not because they’re easier to test or more reliable than unsupervised ones—but because they explicitly acknowledge that interpretation has to be anchored in human history.

At a first glance, this may seem to make progress impossible. “All we can ever discover is which books resemble these other books selected by a particular group of readers. The algorithm can only reproduce a category someone else already defined!” And yes, supervised modeling is circular. But this is a circularity shared by all interpretation of history, and it never merely reproduces its starting point. You can discover that books resemble each other to different degrees. You can discover that models defined by the responses of one interpretive community do or don’t align with models of another. And often you can, carefully, provisionally, draw explanatory inferences from the model itself, assisted perhaps by a bit of close reading.
digital-humanities  machine-learning  reasonableness  it's-more-complicated-than-you-think  modeling  philosophy  criticism  to-write-about
11 days ago
[1709.09022] On Integer Images of Max-plus Linear Mappings
Let us extend the pair of operations (max,+) over real numbers to matrices in the same way as in conventional linear algebra. We study integer images of max-plus linear mappings. The question whether Ax (in the max-plus algebra) is an integer vector for at least one x has been studied for some time but polynomial solution methods seem to exist only in special cases. In the terminology of combinatorial matrix theory this question reads: is it possible to add constants to the columns of a given matrix so that all row maxima are integer? This problem has been motivated by attempts to solve a class of job-scheduling problems. We present two polynomially solvable special cases aiming to move closer to a polynomial solution method in the general case.
representation  linear-algebra  out-of-the-box  mathematics  algebra  nudge-targets  consider:looking-to-see  consider:representation
13 days ago
[1609.04212] Formalizing Neurath's Ship: Approximate Algorithms for Online Causal Learning
Higher-level cognition depends on the ability to learn models of the world. We can characterize this at the computational level as a structure-learning problem with the goal of best identifying the prevailing causal relationships among a set of relata. However, the computational cost of performing exact Bayesian inference over causal models grows rapidly as the number of relata increases. This implies that the cognitive processes underlying causal learning must be substantially approximate. A powerful class of approximations that focuses on the sequential absorption of successive inputs is captured by the Neurath's ship metaphor in philosophy of science, where theory change is cast as a stochastic and gradual process shaped as much by people's limited willingness to abandon their current theory when considering alternatives as by the ground truth they hope to approach. Inspired by this metaphor and by algorithms for approximating Bayesian inference in machine learning, we propose an algorithmic-level model of causal structure learning under which learners represent only a single global hypothesis that they update locally as they gather evidence. We propose a related scheme for understanding how, under these limitations, learners choose informative interventions that manipulate the causal system to help elucidate its workings. We find support for our approach in the analysis of four experiments.
machine-learning  philosophy-of-engineering  algorithms  representation  nudge-targets  consider:looking-to-see  to-write-about
13 days ago
Poetic Computation: Reader is an online-book by Taeyoon Choi that discusses code as a form of poetry and aesthetic while raising ethical questions associated with it. The book is based on Choi’s lectures at the School for Poetic Computation, an independent school he co-founded in New York City. The first two chapters will be published in September 2017, with the following chapters to be published over the year.

Designed by HAWRAF, Poetic Computation: Reader presents new possibilities for enhanced accessibility and legibility in web browsers. Readers can change the design elements and format parameters to create their ideal reading experience. Poetic Computation: Reader is edited by Hannah Son and includes interviews with a select group of scholars and practitioners.
14 days ago
[1703.07695] Selfish Cops and Adversarial Robber: Multi-Player Pursuit Evasion on Graphs
We introduce and study the game of Selfish Cops and Adversarial Robber (SCAR) which is an N-player generalization of the classic two-player cops and robbers (CR) game. We prove that SCAR has a Nash equilibrium in deterministic strategies.
game-theory  graph-theory  dynamical-systems  feature-construction  to-write-about  to-simulate  nudge-targets  consider:looking-to-see
14 days ago
[1404.6238] Recurrence and transience for the frog model on trees
The frog model is a growing system of random walks where a particle is added whenever a new site is visited. A longstanding open question is how often the root is visited on the infinite d-ary tree. We prove the model undergoes a phase transition, finding it recurrent for d=2 and transient for d≥5. Simulations suggest strong recurrence for d=2, weak recurrence for d=3, and transience for d≥4. Additionally, we prove a 0-1 law for all d-ary trees, and we exhibit a graph on which a 0-1 law does not hold.
To prove recurrence when d=2, we construct a recursive distributional equation for the number of visits to the root in a smaller process and show the unique solution must be infinity a.s. The proof of transience when d=5 relies on computer calculations for the transition probabilities of a large Markov chain. We also include the proof for d≥6, which uses similar techniques but does not require computer assistance.
probability-theory  graph-theory  random-walks  dynamical-systems  rather-interesting  to-understand  to-write-about  consider:feature-discovery  consider:classification
14 days ago
Bridges 2017
The 2017 international conference of Bridges: Mathematical Connections in Art, Music and Science was held at University of Waterloo, Ontario, Canada, July 27-31.
mathematical-recreations  conferences  to-do
14 days ago
Corporate Gibberish Generator on AndrewDavidson.com
Welcome to the Corporate Gibberish Generator™ by Andrew Davidson. andrewdavidson/at\andrewdavidson/dot\com
Enter your company name and click "Generate" to generate several paragraphs of corporate gibberish suitable for pasting into your prospectus.
(The gibberish is geared more toward Internet and technology companies.)
branding  corporatism  humor  algorithms  natural-language-processing  generative-art
14 days ago
Spline Script · inconvergent
It's been a while since the last time I was down the rabbit hole of generative handwriting. However, I thought I'd describe the experiments I've been doing over the past week or so in some more detail.