[1401.6200] Three Series for the Generalized Golden Mean

8 hours ago

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

yesterday

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

yesterday

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

yesterday

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

yesterday

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

yesterday

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

yesterday

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

4 days ago

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
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.

4 days ago

[1605.04550] Finite-size effects and percolation properties of Poisson geometries

4 days ago

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

4 days ago

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

4 days ago

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

4 days ago

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

4 days ago

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

4 days ago

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

4 days ago

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

4 days ago

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

4 days ago

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

4 days ago

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

4 days ago

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

4 days ago

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

4 days ago

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

4 days ago

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

4 days ago

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

4 days ago

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
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?

4 days ago

[1501.03992] PSPACE-Completeness of Majority Automata Networks

4 days ago

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

4 days ago

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

4 days ago

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.

helpful
devops
to-understand
Synology
NAS
4 days ago

[1710.04247] Lagrange's Theorem for Binary Squares

5 days ago

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.

via:twitter
rather-interesting
number-theory
proof
representation
to-write-about
formal-languages
nudge-targets
consider:looking-to-see
consider:open-questions
5 days ago

[1604.03159] Phase Transitions and a Model Order Selection Criterion for Spectral Graph Clustering

7 days ago

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?

7 days ago

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?

7 days ago

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

7 days ago

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

7 days ago

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

Automated conjecturing III | SpringerLink

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

7 days ago

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

8 days ago

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

8 days ago

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

8 days ago

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

8 days ago

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
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.

8 days ago

[1701.00146] Even $1 times n$ Edge-Matching and Jigsaw Puzzles are Really Hard

8 days ago

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

8 days ago

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.

paper-mills
academic-culture
academia-doesn't-guarantee-acuity
publishing
amusing
and-yet
8 days ago

[1704.08292] Deep Cross-Modal Audio-Visual Generation

8 days ago

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

8 days ago

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.)

quotes
reading
8 days ago

New Shapes Solve Infinite Pool-Table Problem | Quanta Magazine

8 days ago

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

8 days ago

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
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.

8 days ago

An obscure copyright law is letting the Internet Archive distribute books published 1923-1941 / Boing Boing

8 days ago

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).

copyright
digitization
to-learn-about
to-write-about
openness
commons
8 days ago

Visualizing Intersecting Sets

8 days ago

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

8 days ago

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
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.

8 days ago

On reciprocal causation in the evolutionary process | bioRxiv

8 days ago

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

8 days ago

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

9 days ago

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

10 days ago

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

10 days ago

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

10 days ago

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.

worklife
advice
book-reviews
to-write-about
mindfulness
boredom
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

10 days ago

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

10 days ago

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

10 days ago

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

10 days ago

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

10 days ago

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

10 days ago

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

10 days ago

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

10 days ago

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

11 days ago

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

11 days ago

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

11 days ago

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

11 days ago

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
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.

11 days ago

We’re probably due for another discussion of Stanley Fish | The Stone and the Shell

11 days ago

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
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.

11 days ago

[1709.09022] On Integer Images of Max-plus Linear Mappings

13 days ago

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

13 days ago

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

14 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.

to-read
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

14 days ago

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

14 days ago

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
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.

14 days ago

Bridges 2017

14 days ago

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

14 days ago

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
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.)

14 days ago

Spline Script · inconvergent

14 days ago

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.

generative-art
rather-interesting
to-do
to-write-about
algorithms
14 days ago

academia
academic-culture
activism
advice
agent-based
agility
algorithms
amusing
ann-arbor
approximation
architecture
archive
art
artificial-intelligence
artificial-life
benchmarking
bioinformatics
biological-engineering
blogging
books
bushism
business
business-culture
business-model
cellular-automata
classification
clustering
collaboration
collective-intelligence
combinatorics
commons
communication
community
complex-systems
complexology
compressed-sensing
computational-complexity
computational-geometry
computer-science
conservatism
consider:feature-discovery
consider:looking-to-see
consider:performance-measures
consider:rediscovery
consider:representation
consider:stress-testing
constraint-satisfaction
copyright
corporatism
criticism
crowdsourcing
cultural-assumptions
cultural-dynamics
cultural-norms
data-analysis
data-mining
deep-learning
design
design-patterns
development
digital-humanities
digitization
disintermediation-in-action
distributed-processing
diversity
dynamical-systems
economics
education
emergence
emergent-design
engineering
engineering-design
evolutionary-algorithms
evolutionary-economics
experiment
feature-construction
feature-extraction
finance
financial-crisis
fitness-landscapes
formalization
game-theory
games
generative-art
generative-models
genetic-programming
geometry
google
government
graph-theory
graphic-design
heuristics
history
horse-races
humor
image-analysis
image-processing
image-segmentation
inference
information-theory
innovation
intellectual-property
interesting
inverse-problems
javascript
kauffmania
language
law
lawyers
learning
learning-by-doing
learning-from-data
library
local
machine-learning
macos
management
marketing
mathematical-recreations
mathematics
matrices
media
metaheuristics
metrics
michigan
modeling
models
models-and-modes
multiobjective-optimization
nanohistory
nanotechnology
natural-language-processing
network-theory
networks
neural-networks
nonlinear-dynamics
nudge
nudge-targets
number-theory
numerical-methods
open-access
open-questions
open-source
openness
operations-research
optimization
pedagogy
performance-measure
philosophy
philosophy-of-science
photography
physics
planning
politics
prediction
probability-theory
programming
project-management
proof
public-policy
publishing
rather-interesting
representation
research
review
robotics
robustness
ruby
science
self-organization
signal-processing
simulation
social-dynamics
social-engineering
social-networks
social-norms
sociology
software
software-development
statistics
strings
sustainability
systems-biology
technology
the-mangle-in-practice
theoretical-biology
tiling
time-series
to-read
to-understand
to-write-about
tools
trading
tutorial
typography
user-experience
via:cshalizi
video
visualization
web-design
web2.0
worklife
writing