abscondment/clj-kdtree: kd-trees in Clojure
A Kd-tree is a special type of binary tree that partitions points in a k-dimensional space. It can be used for efficient nearest-neighbor searches.
Clojure  programming  library  nudge 
3 days ago
mathrecreation: build your own knight's tour
A couple of posts back I mentioned some knight and king's tour puzzles that I had put together (knights here, kings here). I've added another page based on the same underlying framework where you can build your own knight's tour.
mathematical-recreations  javascript  lovely  learn-by-doing  heuristics  to-write-about 
3 days ago
[1109.4994] The finite-state character of physical dynamics
Finite physical systems have only a finite amount of distinct state. This finiteness is fundamental in statistical mechanics, where the maximum number of distinct states compatible with macroscopic constraints defines entropy. Here we show that finiteness of distinct state is similarly fundamental in ordinary mechanics: energy and momentum are defined by the maximum number of distinct states possible in a given time or distance. More generally, any moment of energy or momentum bounds distinct states in time or space. These results generalise both the Nyquist bandwidth-bound on distinct values in classical signals, and quantum uncertainty bounds. The new certainty bounds are achieved by finite-bandwidth evolutions in which time and space are effectively discrete, including quantum evolutions that are effectively classical. Since energy and momentum count distinct states, they are defined in classical finite-state dynamics, and they relate classical relativity to finite-state evolution.
hey-I-know-this-guy  physics  automata  theoretical-physics  complexology 
3 days ago
Reference-free comparison of microbial communities via de Bruijn graphs | bioRxiv
Microbial communities inhabiting the human body exhibit significant variability across different individuals and tissues, and are suggested to play an important role in health and disease. High-throughput sequencing offers unprecedented possibilities to profile microbial community composition, but limitations of existing taxonomic classification methods (including incompleteness of existing microbial reference databases) limits the ability to accurately compare microbial communities across different samples. In this paper, we present a method able to overcome these limitations by circumventing the classification step and directly using the sequencing data to compare microbial communities. The proposed method provides a powerful reference-free way to assess differences in microbial abundances across samples. This method, called EMDeBruijn, condenses the sequencing data into a de Bruijn graph. The Earth Mover's Distance (EMD) is then used to measure similarities and differences of the microbial communities associated with the individual graphs. We apply this method to RNA-Seq data sets from a coronary artery calcification (CAC) study and shown that EMDeBruijn is able to differentiate between case and control CAC samples while utilizing all the candidate microbial reads. We compare these results to current reference-based methods, which are shown to have a limited capacity to discriminate between case and control samples. We conclude that this reference-free approach is a viable choice in comparative metatranscriptomic studies.
microbiology  bioinformatics  microbial-ecology  wow  indistinguishable-from-magic  algorithms  to-understand  to-learn 
3 days ago
[1203.3373] Dense packings of spheres in cylinders I. Simulations
We study the optimal packing of hard spheres in an infinitely long cylinder, using simulated annealing, and compare our results with the analogous problem of packing disks on the unrolled surface of a cylinder. The densest structures are described and tabulated in detail up to D/d=2.873 (ratio of cylinder and sphere diameters). This extends previous computations into the range of structures which include internal spheres that are not in contact with the cylinder.
phyllotaxis  packing  rather-interesting  parametric-sweep  to-write-about  nudge-targets  consider:symbolic-regression 
3 days ago
[1012.3684] Phyllotactic description of hard sphere packing in cylindrical channels
We develop a simple analytical theory that relates dense sphere packings in a cylinder to corresponding disk packings on its surface. It applies for ratios R=D/d (where d and D are the diameters of the hard spheres and the bounding cylinder, respectively) up to R=1+1/sin(pi/5). Within this range the densest packings are such that all spheres are in contact with the cylindrical boundary. The detailed results elucidate extensive numerical simulations by ourselves and others by identifying the nature of all competing phases.
packing  phyllotaxis  rather-interesting  models  to-write-about  geometry  constraint-satisfaction 
3 days ago
[1612.00197] Learning in an Uncertain World: Representing Ambiguity Through Multiple Hypotheses
Many prediction tasks contain uncertainty. In some cases, uncertainty is inherent in the task itself. In next-frame or future prediction, for example, many distinct outcomes are equally valid. In other cases, uncertainty arises from the way data is labeled. For example, in object detection, many objects of interest often go unlabeled, and in human pose estimation, occluded joints are often labeled with ambiguous values. In this work we focus on a principled approach for handling such scenarios. In particular, we propose a framework for reformulating existing single-prediction models as multiple hypothesis prediction (MHP) models, and we propose an associated meta loss and optimization procedure to train them. To demonstrate our approach, we consider three diverse applications: human pose estimation, future prediction and image classification. We find that MHP models outperform their single-hypothesis counterparts in all cases, and that MHP models simultaneously expose valuable insights into the variability of predictions.
machine-learning  reinventing-the-wheel  Pareto-GP  modeling-is-not-mathematics  representation  to-write-about 
3 days ago
[1501.01300] Minimum Probabilistic Finite State Learning Problem on Finite Data Sets: Complexity, Solution and Approximations
In this paper, we study the problem of determining a minimum state probabilistic finite state machine capable of generating statistically identical symbol sequences to samples provided. This problem is qualitatively similar to the classical Hidden Markov Model problem and has been studied from a practical point of view in several works beginning with the work presented in: Shalizi, C.R., Shalizi, K.L., Crutchfield, J.P. (2002) \textit{An algorithm for pattern discovery in time series.} Technical Report 02-10-060, Santa Fe Institute. arxiv.org/abs/cs.LG/0210025. We show that the underlying problem is NP-hard and thus all existing polynomial time algorithms must be approximations on finite data sets. Using our NP-hardness proof, we show how to construct a provably correct algorithm for constructing a minimum state probabilistic finite state machine given data and empirically study its running time.
hey-I-know-this-guy  automata  time-series  optimization  modeling  performance-measure  computational-complexity  rather-interesting  to-write-about  nudge-targets  consider:rewriting-the-damned-algorithm 
3 days ago
[1608.05824] Phyllotaxis, disk packing and Fibonacci numbers
We consider the evolution of the packing of disks (representing the position of buds) that are introduced at the top of a surface which has the form of a growing stem. They migrate downwards, while conforming to three principles, applied locally: dense packing, homogeneity and continuity. We show that spiral structures characterised by the widely observed Fibonacci sequence (1,1,2,3,5,8,13...), as well as related structures, occur naturally under such rules. Typical results are presented in a animation.
phyllotaxis  fibonacci-everything  developmental-biology  physics  packing  nudge-targets  consider:robustness  consider:performance-measures 
3 days ago
[1606.06329] Recognizing Surgical Activities with Recurrent Neural Networks
We apply recurrent neural networks to the task of recognizing surgical activities from robot kinematics. Prior work in this area focuses on recognizing short, low-level activities, or gestures, and has been based on variants of hidden Markov models and conditional random fields. In contrast, we work on recognizing both gestures and longer, higher-level activites, or maneuvers, and we model the mapping from kinematics to gestures/maneuvers with recurrent neural networks. To our knowledge, we are the first to apply recurrent neural networks to this task. Using a single model and a single set of hyperparameters, we match state-of-the-art performance for gesture recognition and advance state-of-the-art performance for maneuver recognition, in terms of both accuracy and edit distance. Code is available at this https URL .
neural-networks  recurrent-networks  control-theory  robotics  machine-learning  rather-interesting  representation  nudge-targets  consider:representation 
3 days ago
[1605.07493] Safely Optimizing Highway Traffic with Robust Model Predictive Control-based Cooperative Adaptive Cruise Control
Road traffic crashes have been the leading cause of death among young people. Most of these accidents occur when the driver becomes distracted due to fatigue or external factors. Vehicle platooning systems such as Cooperative Adaptive Cruise Control (CACC) are one of the results of the effort devoted to the development of technologies for decreasing the number of road crashes and fatalities. Previous studies have suggested such systems improve up to 273\% highway traffic throughput and fuel consumption in more than 15\% if the clearance between vehicles in this class of roads can be reduced to 2 meters. This paper proposes an approach that guarantees a minimum safety distance between vehicles taking into account the overall system delays and braking capacity of each vehicle. A l∞-norm Robust Model Predictive Controller (RMPC) is developed to guarantee the minimum safety distance is not violated due to uncertainties on the lead vehicle behavior. A formulation for a lower bound clearance of vehicles inside a platoon is also proposed. Simulation results show the performance of the proposed approach compared to a nominal controller when the system is subject to both modeled and unmodeled disturbances.
robotics  operations-research  planning  algorithms  performance-measure  rather-interesting  engineering-design  nudge-targets  consider:looking-to-see 
3 days ago
[1309.1837] Evolution and non-equilibrium physics. A study of the Tangled Nature Model
We argue that the stochastic dynamics of interacting agents which replicate, mutate and die constitutes a non-equilibrium physical process akin to aging in complex materials. Specifically, our study uses extensive computer simulations of the Tangled Nature Model (TNM) of biological evolution to show that punctuated equilibria successively generated by the model's dynamics have increasing entropy and are separated by increasing entropic barriers. We further show that these states are organized in a hierarchy and that limiting the values of possible interactions to a finite interval leads to stationary fluctuations within a component of the latter. A coarse-grained description based on the temporal statistics of quakes, the events leading from one component of the hierarchy to the next, accounts for the logarithmic growth of the population and the decaying rate of change of macroscopic variables. Finally, we question the role of fitness in large scale evolution models and speculate on the possible evolutionary role of rejuvenation and memory effects.
theoretical-biology  artificial-life  complexology  ecology  Bak-Sneppen-stuff  fitness-landscapes  Oh  Physics! 
3 days ago
[1608.04568] Decision Making on Fitness Landscapes
We discuss fitness landscapes and how they can be modified to account for co-evolution. We are interested in using the landscape as a way to model rational decision making in a toy economic system. We develop a model very similar to the Tangled Nature Model of Christensen et. al. that we call the Tangled Decision Model. This is a natural setting for our discussion of co-evolutionary fitness landscapes. We use a Monte Carlo step to simulate decision making and investigate two different decision making procedures.
Kauffmania  fitness-landscapes  coevolution  theoretical-biology  evolutionary-economics  to-write-about  consider:looking-to-see 
3 days ago
[1512.05213] The Tangled Nature Model of evolutionary dynamics reconsidered: structural and dynamical effects of trait inheritance
The Tangled Nature Model of biological and cultural evolution features interacting agents which compete for limited resources and reproduce in an error prone fashion and at a rate depending on the `tangle' of interactions they maintain with others.
The set of interactions linking a TNM individual to others is key to its reproductive success and arguably constitutes its most important property. Yet, in many studies, the interactions of an individual and those of its mutated off-spring are unrelated, a rather unrealistic feature corresponding to a point mutation turning a giraffe into an elephant. To bring out the structural and dynamical effects of trait inheritance , we introduce and numerically analyze a family of TNM models where a positive integer K parametrises correlations between the interactions of an agent and those of its mutated offspring. For K=1 a single point mutation randomizes all the interactions, while increasing K up to the length of the genome ensures an increasing level of trait inheritance. We show that the distribution of the interactions generated by our rule is nearly independent of the value of K. Changing K strengthens the core structure of the ecology, leads to population abundance distributions which are better approximated by log-normal probability densities and increases the probability that a species extant at time tw is also extant at a later time t. In particular, survival probabilities are shown to decay as powers of the ratio t/tw, similarity to the pure aging behaviour approximately describing glassy systems of physical origin. Increasing the value of K decreases the numerical value of the decay exponent of the power law, which is a clear quantitative dynamical effect of trait inheritance.
theoretical-biology  ecology  evolutionary-biology  agent-based  simulation  rather-interesting  to-write-about 
3 days ago
[1702.07969] Related Pins at Pinterest: The Evolution of a Real-World Recommender System
Related Pins is the Web-scale recommender system that powers over 40% of user engagement on Pinterest. This paper is a longitudinal study of three years of its development, exploring the evolution of the system and its components from prototypes to present state. Each component was originally built with many constraints on engineering effort and computational resources, so we prioritized the simplest and highest-leverage solutions. We show how organic growth led to a complex system and how we managed this complexity. Many challenges arose while building this system, such as avoiding feedback loops, evaluating performance, activating content, and eliminating legacy heuristics. Finally, we offer suggestions for tackling these challenges when engineering Web-scale recommender systems.
recommendations  machine-learning  social-networks  feature-construction  rather-interesting  performance-measure 
3 days ago
[1701.08381] Random Forest regression for manifold-valued responses
An increasing array of biomedical and computer vision applications requires the predictive modeling of complex data, for example images and shapes. The main challenge when predicting such objects lies in the fact that they do not comply to the assumptions of Euclidean geometry. Rather, they occupy non-linear spaces, a.k.a. manifolds, where it is difficult to define concepts such as coordinates, vectors and expected values. In this work, we construct a non-parametric predictive methodology for manifold-valued objects, based on a distance modification of the Random Forest algorithm. Our method is versatile and can be applied both in cases where the response space is a well-defined manifold, but also when such knowledge is not available. Model fitting and prediction phases only require the definition of a suitable distance function for the observed responses. We validate our methodology using simulations and apply it on a series of illustrative image completion applications, showcasing superior predictive performance, compared to various established regression methods.
machine-learning  representation  to-understand  regression  metrics  distance-measures 
3 days ago
[1611.00939] Recent Advances in Transient Imaging: A Computer Graphics and Vision Perspective
Transient imaging has recently made a huge impact in the computer graphics and computer vision fields. By capturing, reconstructing, or simulating light transport at extreme temporal resolutions, researchers have proposed novel techniques to show movies of light in motion, see around corners, detect objects in highly-scattering media, or infer material properties from a distance, to name a few. The key idea is to leverage the wealth of information in the temporal domain at the pico or nanosecond resolution, information usually lost during the capture-time temporal integration. This paper presents recent advances in this field of transient imaging from a graphics and vision perspective, including capture techniques, analysis, applications and simulation.
image-analysis  indistinguishable-from-magic  review  to-write-about 
3 days ago
[1612.03471] Reinforcement Learning With Temporal Logic Rewards
Reinforcement learning (RL) depends critically on the choice of reward functions used to capture the de- sired behavior and constraints of a robot. Usually, these are handcrafted by a expert designer and represent heuristics for relatively simple tasks. Real world applications typically involve more complex tasks with rich temporal and logical structure. In this paper we take advantage of the expressive power of temporal logic (TL) to specify complex rules the robot should follow, and incorporate domain knowledge into learning. We propose Truncated Linear Temporal Logic (TLTL) as specifications language, that is arguably well suited for the robotics applications, together with quantitative semantics, i.e., robustness degree. We propose a RL approach to learn tasks expressed as TLTL formulae that uses their associated robustness degree as reward functions, instead of the manually crafted heuristics trying to capture the same specifications. We show in simulated trials that learning is faster and policies obtained using the proposed approach outperform the ones learned using heuristic rewards in terms of the robustness degree, i.e., how well the tasks are satisfied. Furthermore, we demonstrate the proposed RL approach in a toast-placing task learned by a Baxter robot.
machine-learning  performance-measure  planning  rather-interesting  what-gets-measured-gets-fudged  "reward-hacking"  nudge-targets  consider:representation 
3 days ago
[1612.08631] Random Multi-Hopper Model. Super-Fast Random Walks on Graphs
We develop a model for a random walker with long-range hops on general graphs. This random multi-hopper jumps from a node to any other node in the graph with a probability that decays as a function of the shortest-path distance between the two nodes. We consider here two decaying functions in the form of the Laplace and Mellin transforms of the shortest-path distances. Remarkably, when the parameters of these transforms approach zero asymptotically, the multi-hopper's hitting times between any two nodes in the graph converge to their minimum possible value, given by the hitting times of a normal random walker on a complete graph. Stated differently, for small parameter values the multi-hopper explores a general graph as fast as possible when compared to a random walker on a full graph. Using computational experiments we show that compared to the normal random walker, the multi-hopper indeed explores graphs with clusters or skewed degree distributions more efficiently for a large parameter range. We provide further computational evidence of the speed-up attained by the random multi-hopper model with respect to the normal random walker by studying deterministic, random and real-world networks.
network-theory  feature-construction  graph-theory  random-walks  rather-interesting  nudge-targets  consider:rediscovery  consider:prediction-from-graph 
3 days ago
mathrecreation: Ulam's two step cellular automata
Above are some of the nice images generated by a cellular automata described in one of Martin Gardner's essays about Conway's Game of Life (you can find the essays here). Cells have four neighbours (north, south, east, west), and follow only two rules that are applied at each step: if a cell has one live neighbour it turns on, and if a cell is on it turns off after two steps. The images above start happening around step 100 after turning on a single cell at the centre of a 61 by 61 grid.
cellular-automata  mathematical-recreations  open-questions  simulation 
3 days ago
[1612.08220] Understanding Neural Networks through Representation Erasure
While neural networks have been successfully applied to many natural language processing tasks, they come at the cost of interpretability. In this paper, we propose a general methodology to analyze and interpret decisions from a neural model by observing the effects on the model of erasing various parts of the representation, such as input word-vector dimensions, intermediate hidden units, or input words. We present several approaches to analyzing the effects of such erasure, from computing the relative difference in evaluation metrics, to using reinforcement learning to erase the minimum set of input words in order to flip a neural model's decision. In a comprehensive analysis of multiple NLP tasks, including linguistic feature classification, sentence-level sentiment analysis, and document level sentiment aspect prediction, we show that the proposed methodology not only offers clear explanations about neural model decisions, but also provides a way to conduct error analysis on neural models.
deep-learning  neural-networks  interpretability  natural-language-processing  robustness  rather-interesting  feature-construction 
3 days ago
[1702.00382] Understanding trained CNNs by indexing neuron selectivity
The impressive performance and plasticity of convolutional neural networks to solve different vision problems are shadowed by their black-box nature and its consequent lack of full understanding. To reduce this gap we propose to describe the activity of individual neurons by quantifying their inherent selectivity to specific properties. Our approach is based on the definition of feature selectivity indexes that allow the ranking of neurons according to specific properties. Here we report the results of exploring selectivity indexes for: (a) an image feature (color); and (b) an image label (class membership). Our contribution is a framework to seek or classify neurons by indexing on these selectivity properties. It helps to find color selective neurons, such as a red-mushroom neuron in layer conv4 or class selective neurons such as dog-face neurons in layer conv5, and establishes a methodology to derive other selectivity properties. Indexing on neuron selectivity can statistically draw how features and classes are represented through layers at a moment when the size of trained nets is growing and automatic tools to index can be helpful.
deep-learning  black-boxes  rather-interesting  explanatory-power  neural-networks  modeling-is-not-mathematics 
3 days ago
The Past Sure Is Tense: On Interpreting Phylogenetic Divergence Time Estimates | bioRxiv
Divergence time estimation --- the calibration of a phylogeny to geological time --- is a integral first step in modelling the tempo of biological evolution (traits and lineages). However, despite increasingly sophisticated methods to infer divergence times from molecular genetic sequences, the estimated age of many nodes across the tree of life contrast significantly and consistently with timeframes conveyed by the fossil record. This is perhaps best exemplified by crown angiosperms, where molecular clock (Triassic) estimates predate the oldest (Early Cretaceous) undisputed angiosperm fossils by tens of millions of years or more. While the incompleteness of the fossil record is a common concern, issues of data limitation and model inadequacy are viable (if underexplored) alternative explanations. In this vein, Beaulieu et al. (2015) convincingly demonstrated how methods of divergence time inference can be misled by both (i) extreme state-dependent molecular substitution rate heterogeneity and (ii) biased sampling of representative major lineages. While these (essentially model-violation) results are robust (and probably common in empirical data sets), we note a further alternative: that the configuration of the statistical inference problem alone precluded the reconstruction of the paleontological timeframe for the crown age of angiosperms. We demonstrate, through sampling from the joint prior (formed by combining the tree (diversification) prior with the various calibration densities specified for fossil-calibrated nodes), that with no data present at all, an Early Cretaceous crown angiosperms is rejected (i.e., has essentially zero probability). More worrisome, however, is that for the 24 nodes calibrated by fossils, almost all have indistinguishable marginal prior and posterior age distributions, indicating an absence of relevant information in the data. Given that these calibrated nodes are strategically placed in disparate regions of the tree, they essentially anchor the tree scaffold, and so the posterior inference for the tree as a whole is largely determined by the pseudo-data present in the (often arbitrary) calibration densities. We recommend, as for any Bayesian analysis, that marginal prior and posterior distributions be carefully compared, especially for parameters of direct interest. Finally, we note that the results presented here do not refute the biological modelling concerns identified by Beaulieu et al. (2015). Both sets of issues remain apposite to the goals of accurate divergence time estimation, and only by considering them in tandem can we move forward more confidently.
cladistics  statistics  modeling  paleontology  inference  rather-interesting  modeling-is-not-mathematics 
3 days ago
[math/0407479] Properties and Problems related to Smarandache Type Functions
In this paper we present the definitions and some properties of several Samrandache Type Functions that are involved in many solved and unsolved problems and conjectures in number theory and recreational mathematics.
number-theory  open-questions  nudge-targets  consider:looking-to-see 
4 days ago
[1508.04721] Every natural number is the sum of forty-nine palindromes
It is shown that the set of decimal palindromes is an additive basis for the natural numbers. Specifically, we prove that every natural number can be expressed as the sum of forty-nine (possibly zero) decimal palindromes.
number-theory  cute  nudge-targets  consider:looking-to-see  to-write-about 
4 days ago
[1610.09371] The Mutando of Insanity
Puzzles based on coloured cubes and other coloured geometrical figures have a long history in the recreational mathematical literature. One of the most commercially famous of these puzzles is the Instant Insanity that consists of four cubes. Their faces are coloured with four different colours in such a way that each colour is present in each one of the four cubes. To solve the puzzle, one needs to stack the cubes in a tower in such a way that each one of the colours appears exactly once in the four long faces of the tower. The main purpose of this paper is to study the combinatorial richness of a mathematical model of this puzzle by analysing all possible ways of colouring the cubes to form a puzzle analogous to the Instant Insanity. We have done this analysis for $n$ cubes and $n$ colours for $n=4, 5, 6$. This combinatorial analysis allowed us to design the Mutando of Insanity, a puzzle that we presented at Gathering for Gardner 12 (G4G12).
puzzles  mathematical-recreations  combinatorics  enumeration  constraint-satisfaction  nudge-targets  consider:rediscovery  consider:generalization  consider:looking-to-see 
4 days ago
[1605.06857] Finding the Year's Share in Day-of-Week Calculations
The dominant part in the mental calculation of the day of the week for any given date is to determine the year share, that is, the contribution of the two-digit year part of the date. This paper describes a number of year share computation methods, some well-known and some new. The "Parity Minus 3" method, in particular, is a new alternative to the popular "Odd+11" method. The paper categorizes the methods of year share computation, and presents simpler proofs of their correctness than usually provided.
Keywords and phrases: day of the week, calendar algorithms, doomsday method, first Sunday algorithm, mental arithmetic, year share
mathematics  mnemonics  approximation  rather-interesting  mathematical-recreations  nudge-targets  consider:looking-to-see 
4 days ago
[1604.01760] Solving Diophantine Equations
In this book a multitude of Diophantine equations and their partial or complete solutions are presented. How should we solve, for example, the equation {\eta}({\pi}(x)) = {\pi}({\eta}(x)), where {\eta} is the Smarandache function and {\pi} is Riemann function of counting the number of primes up to x, in the set of natural numbers? If an analytical method is not available, an idea would be to recall the empirical search for solutions. We establish a domain of searching for the solutions and then we check all possible situations, and of course we retain among them only those solutions that verify our equation. In other words, we say that the equation does not have solutions in the search domain, or the equation has n solutions in this domain. This mode of solving is called partial resolution. Partially solving a Diophantine equation may be a good start for a complete solving of the problem. The authors have identified 62 Diophantine equations that impose such approach and they partially solved them. For an efficient resolution it was necessarily that they have constructed many useful tools for partially solving the Diophantine equations into a reasonable time. The computer programs as tools were written in Mathcad, because this is a good mathematical software where many mathematical functions are implemented. Transposing the programs into another computer language is facile, and such algorithms can be turned to account on other calculation systems with various processors.
algebra  number-theory  rather-interesting  books  nudge-targets  consider:looking-to-see  algorithms  numerical-methods 
4 days ago
[1202.4358] Natural Product Xn on matrices
This book has eight chapters. The first chapter is introductory in nature. Polynomials with matrix coefficients are introduced in chapter two. Algebraic structures on these polynomials with matrix coefficients is defined and described in chapter three. Chapter four introduces natural product on matrices. Natural product on super matrices is introduced in chapter five. Super matrix linear algebra is introduced in chapter six. Chapter seven claims only after this notion becomes popular we can find interesting applications of them. The final chapter suggests over 100 problems some of which are at research level.
matrices  algebra  open-questions  rather-interesting  book  nudge-targets  consider:looking-to-see 
4 days ago
[1605.03275] Complements to Classic Topics of Circles Geometry
We approach several themes of classical geometry of the circle and complete them with some original results, showing that not everything in traditional math is revealed, and that it still has an open character. The topics were chosen according to authors aspiration and attraction, as a poet writes lyrics about spring according to his emotions.
plane-geometry  review  rather-interesting  nudge-targets  consider:novelty-search 
4 days ago
[1603.08456] Various Arithmetic Functions and their Applications
Over 300 sequences and many unsolved problems and conjectures related to them are presented herein. These notions, definitions, unsolved problems, questions, theorems corollaries, formulae, conjectures, examples, mathematical criteria, etc. on integer sequences, numbers, quotients, residues, exponents, sieves, pseudo-primes squares cubes factorials, almost primes, mobile periodicals, functions, tables, prime square factorial bases, generalized factorials, generalized palindromes, so on.
number-theory  open-questions  rather-interesting  review  nudge-targets  to-write-about 
4 days ago
[1507.07970] Dividing the circle
There are known constructions for some regular polygons, usually inscribed in a circle, but not for all polygons - the Gauss-Wantzel Theorem states precisely which ones can be constructed.
The constructions differ greatly from one polygon to the other. There are, however, general processes for determining the side of the $n$-gon (approximately, but sometimes with great precision), which we describe in this paper. We present a joint mathematical analysis of the so-called Bion and Tempier approximation methods, comparing the errors and trying to explain why these constructions would work at all.
compass-and-straightedge  constructible-numbers  rather-interesting  nudge-targets  consider:benchmarks  plane-geometry 
4 days ago
[1505.00446] Tessellations and Positional Representation
The main goal of this paper is to define a 1-1 correspondence between between substitution tilings constructed by inflation and the arithmetic of positional representation in the underlying real vector space.
It introduces a generalization of inflationary tessellations to equivalence classes of tiles. Two tiles belong to the same class if they share a defined geometric property, such as equivalence under a group of isometries, having the same measure, or having the same `decoration'. Some properties of ordinary tessellations for which the equivalence relation is congruence with respect to the full group of isometries are already determined by the weaker relation of equivalence with respect to equal measure. In particular, the multiplier for an inflationary tiling (such as a Penrose aperiodic tiling) is an algebraic number.
Equivalence of tiles under measure facilitates the investigation of properties of tilings that are independent of dimension, and provides a method for transferring tilings from one dimension to another.
Three well-known aperiodic tilings illustrate aspects of the correspondence: a tiling of Ammann, a Penrose tiling, and the monotiling of Taylor and Socolar-Taylor.
geometry  rather-interesting  mathematical-recreations  tiling  to-write-about  nudge-targets  consider:rediscovery  consider:robustness  consider:performance-measures 
4 days ago
[1605.00180] Counting the number of isosceles triangles in rectangular regular grids
In general graph theory, the only relationship between vertices are expressed via the edges. When the vertices are embedded in an Euclidean space, the geometric relationships between vertices and edges can be interesting objects of study. We look at the number of isosceles triangles where the vertices are points on a regular grid and show that they satisfy a recurrence relation when the grid is large enough. We also derive recurrence relations for the number of acute, obtuse and right isosceles triangles.
combinatorics  number-theory  rather-interesting  enumeration  nudge-targets  consider:looking-to-see 
4 days ago
[1311.6763] Outer Billiards on Regular Polygons
In 1973, J. Moser proposed that his Twist Theorem could be used to show that orbits of the outer billiards map on a sufficiently smooth closed curve were always bounded. Five years later Moser asked the same question for a convex polygon. In 1987 F. Vivaldi and A. Shaidenko showed that all orbits for a regular polygon must be bounded. R. Schwartz recently showed that a quadrilateral known as a Penrose Kite has unbounded orbits and he proposed that 'most' convex polygons support unbounded orbits.
Except for a few special cases, very little is known about the dynamics of the outer billiards map on regular polygons. In this paper we present a unified approach to the analysis of regular polygons - using the canonical 'resonances' which are shared by all regular N-gons. In the case of the regular pentagon and regular octagon these resonances exist on all scales and the fractal structure is well documented, but these are the only non-trivial cases that have been analyzed. We present a partial analysis of the regular heptagon, but the limiting structure is poorly understood and this does not bode well for the remaining regular polygons. The minimal polynomial for the vertices of a regular N-gon has degree Phi(N)/2 where Phi is the Euler totient function, so N = 5, 7 and 11 are respectively quadratic, cubic and quintic. In the words of R. Schwartz, "A case such as N = 11 seems beyond the reach of current technology."
Some of the graphics have embedded high-resolution versions so this file is about 39Mb in size. This file and a smaller version can be downloaded at dynamicsofpolygons.org. Just click on PDFs.
This paper is dedicated to the memory of Eugene Gutkin (1946-2013) who made fundamental contributions to both inner and outer billiards.
billiards  dynamical-systems  chaos  rather-interesting  to-write-about  visualization 
4 days ago
[1609.05240] A Computation in a Cellular Automaton Collider Rule 110
A cellular automaton collider is a finite state machine build of rings of one-dimensional cellular automata. We show how a computation can be performed on the collider by exploiting interactions between gliders (particles, localisations). The constructions proposed are based on universality of elementary cellular automaton rule 110, cyclic tag systems, supercolliders, and computing on rings.
cellular-automata  cute  to-write-about 
4 days ago
[1406.2277] Designing Complex Dynamics in Cellular Automata with Memory
Since their inception at {\it Macy conferences} in later 1940s complex systems remain the most controversial topic of inter-disciplinary sciences. The term `complex system' is the most vague and liberally used scientific term. Using elementary cellular automata (ECA), and exploiting the CA classification, we demonstrate elusiveness of `complexity' by shifting space-time dynamics of the automata from simple to complex by enriching cells with {\it memory}. This way, we can transform any ECA class to another ECA class --- without changing skeleton of cell-state transition function --- and vice versa by just selecting a right kind of memory. A systematic analysis display that memory helps `discover' hidden information and behaviour on trivial --- uniform, periodic, and non-trivial --- chaotic, complex --- dynamical systems.
emergent-design  cellular-automata  to-write-about  feature-construction  complexology 
4 days ago
[1603.01185] Evolving Boolean Regulatory Networks with Variable Gene Expression Times
The time taken for gene expression varies not least because proteins vary in length considerably. This paper uses an abstract, tuneable Boolean regulatory network model to explore gene expression time variation. In particular, it is shown how non-uniform expression times can emerge under certain conditions through simulated evolution. That is, gene expression time variance appears beneficial in the shaping of the dynamical behaviour of the regulatory network without explicit consideration of protein function.
Kauffmania  emergent-design  gene-regulatory-networks  engineering-design  to-write-about  genetic-algorithm  nudge-targets  consider:looking-to-see 
4 days ago
[1608.05578] Haploid-Diploid Evolutionary Algorithms
This paper uses the recent idea that the fundamental haploid-diploid lifecycle of eukaryotic organisms implements a rudimentary form of learning within evolution. A general approach for evolutionary computation is here derived that differs from all previous known work using diploid representations. The primary role of recombination is also changed from that previously considered in both natural and artificial evolution under the new view. Using well-known abstract tuneable models it is shown that varying fitness landscape ruggedness varies the benefit of the new approach.
genetic-algorithm  theoretical-biology  algorithms  metaheuristics 
4 days ago
[1306.5533] Evolving Gene Regulatory Networks with Mobile DNA Mechanisms
This paper uses a recently presented abstract, tuneable Boolean regulatory network model extended to consider aspects of mobile DNA, such as transposons. The significant role of mobile DNA in the evolution of natural systems is becoming increasingly clear. This paper shows how dynamically controlling network node connectivity and function via transposon-inspired mechanisms can be selected for in computational intelligence tasks to give improved performance. The designs of dynamical networks intended for implementation within the slime mould Physarum polycephalum and for the distributed control of a smart surface are considered.
gene-regulatory-networks  Kauffmania  engineering-design  emergent-design  complexology  rather-interesting  nudge-targets  consider:looking-to-see 
4 days ago
[1305.2537] On Creativity of Elementary Cellular Automata
We map cell-state transition rules of elementary cellular automata (ECA) onto the cognitive control versus schizotypy spectrum phase space and interpret cellular automaton behaviour in terms of creativity. To implement the mapping we draw analogies between a degree of schizotypy and generative diversity of ECA rules, and between cognitive control and robustness of ECA rules (expressed via Derrida coefficient). We found that null and fixed point ECA rules lie in the autistic domain and chaotic rules are 'schizophrenic'. There are no highly articulated 'creative' ECA rules. Rules closest to 'creativity' domains are two-cycle rules exhibiting wave-like patterns in the space-time evolution.
hey-I-know-this-guy  cellular-automata  emergent-design  complexology  stamp-collecting  to-write-about  consider:feature-discovery 
4 days ago
[1304.2050] On Creativity of Slime Mould
Slime mould Physarum polycephalum is large single cell with intriguingly smart behaviour. The slime mould shows outstanding abilities to adapt its protoplasmic network to varying environmental conditions. The slime mould can solve tasks of computational geometry, image processing, logics and arithmetics when data are represented by configurations of attractants and repellents. We attempt to map behavioural patterns of slime onto the cognitive control versus schizotypy spectrum phase space and thus interpret slime mould's activity in terms of creativity.
emergent-design  engineering-design  rather-interesting  collective-intelligence  to-write-about  nonstandard-computation 
4 days ago
[1409.3588] Density Classification Quality of the Traffic-majority Rules
The density classification task is a famous problem in the theory of cellular automata. It is unsolvable for deterministic automata, but recently solutions for stochastic cellular automata have been found. One of them is a set of stochastic transition rules depending on a parameter η, the traffic-majority rules.
Here I derive a simplified model for these cellular automata. It is valid for a subset of the initial configurations and uses random walks and generating functions. I compare its prediction with computer simulations and show that it expresses recognition quality and time correctly for a large range of η values.
cellular-automata  hey-I-know-this-guy  emergent-design  to-write-about  nudge-targets  consider:representation  consider:higher-order-problems  consider:classification-of-rules 
4 days ago
[1212.2846] Expressiveness of Elementary Cellular Automata
We investigate expressiveness, a parameter of one-dimensional cellular automata, in the context of simulated biological systems. The development of elementary cellular automata is interpreted in terms of biological systems, and biologically inspired parameters for biodiversity are applied to the configurations of cellular automata.
This article contains a survey of the Elementary Cellular Automata in terms of their expressiveness and an evaluation whether expressiveness is a meaningful term in the context of simulated biology.
cellular-automata  emergent-design  rather-interesting  to-write-about  consider:performance-measures  expressive-representations 
4 days ago
[1106.3046] Computation with competing patterns in Life-like automaton
We study a Life-like cellular automaton rule B2/S2345 where a cell in state `0' takes state `1' if it has exactly two neighbors in state `1' and the cell remains in the state `1' if it has between two and five neighbors in state `1.' This automaton is a discrete analog spatially extended chemical media, combining both properties of sub-excitable and precipitating chemical media. When started from random initial configuration B2/S2345 automaton exhibits chaotic behavior. Configurations with low density of state `1' show emergence of localized propagating patterns and stationary localizations. We construct basic logical gates and elementary arithmetical circuits by simulating logical signals with mobile localizations reaction propagating geometrically restricted by stationary non-destructible localizations. Values of Boolean variables are encoded into two types of patterns --- symmetric (False) and asymmetric (True) patterns --- which compete for the `empty' space when propagate in the channels. Implementations of logical gates and binary adders are illustrated explicitly.
cellular-automata  game-of-life  nonstandard-computation  rather-interesting  to-write-about 
4 days ago
[1102.2315] Cellular Automata and Discrete Geometry
In this paper, we look at the possibility to implement the algorithm to construct a discrete line devised by the first author in cellular automata. It turns out that such an implementation is feasible.
cellular-automata  nonstandard-computation  rather-interesting  algorithms  to-write-about  nudge-targets  consider:looking-to-see  consider:performance-measures 
4 days ago
[1501.06328] A weakly universal cellular automaton with 2 states on the tiling {11,3}
In this paper, we construct a weakly universal cellular automaton with two states only on the tiling {11,3}. The cellular automaton is rotation invariant and it is a true planar one.
cellular-automata  computer-science  universal-computation  mathematical-recreations  rather-interesting  to-write-about  visualization 
4 days ago
[1408.3696] On A Generalization of "Eight Blocks to Madness"
We consider a puzzle such that a set of colored cubes is given as an instance. Each cube has unit length on each edge and its surface is colored so that what we call the Surface Color Condition is satisfied. Given a palette of six colors, the condition requires that each face should have exactly one color and all faces should have different colors from each other. The puzzle asks to compose a 2x2x2 cube that satisfies the Surface Color Condition from eight suitable cubes in the instance. Note that cubes and solutions have 30 varieties respectively. In this paper, we give answers to three problems on the puzzle: (i) For every subset of the 30 solutions, is there an instance that has the subset exactly as its solution set? (ii) Create a maximum sized infeasible instance (i.e., one having no solution). (iii) Create a minimum sized universal instance (i.e., one having all 30 solutions). We solve the problems with the help of a computer search. We show that the answer to (i) is no. For (ii) and (iii), we show examples of the required instances, where their sizes are 23 and 12, respectively. The answer to (ii) solves one of the open problems that were raised in [E.Berkove et al., "An Analysis of the (Colored Cubes)^3 Puzzle," Discrete Mathematics, 308 (2008) pp. 1033-1045].
puzzles  combinatorics  constraint-satisfaction  proof  mathematical-recreations  rather-interesting  to-write-about 
4 days ago
[1408.0302] Imitative learning as a connector of collective brains
The notion that cooperation can aid a group of agents to solve problems more efficiently than if those agents worked in isolation is prevalent, despite the little quantitative groundwork to support it. Here we consider a primordial form of cooperation -- imitative learning -- that allows an effective exchange of information between agents, which are viewed as the processing units of a social intelligence system or collective brain. In particular, we use agent-based simulations to study the performance of a group of agents in solving a cryptarithmetic problem. An agent can either perform local random moves to explore the solution space of the problem or imitate a model agent -- the best performing agent in its influence network. There is a complex trade-off between the number of agents N and the imitation probability p, and for the optimal balance between these parameters we observe a thirtyfold diminution in the computational cost to find the solution of the cryptarithmetic problem as compared with the independent search. If those parameters are chosen far from the optimal setting, however, then imitative learning can impair greatly the performance of the group. The observed maladaptation of imitative learning for large N offers an alternative explanation for the group size of social animals.
collective-intelligence  agent-based  wisdom-of-crowds  rather-interesting  experiment  simulation  to-write-about 
4 days ago
[1406.5213] How many ways can you make change: Some easy proofs
Given a dollar, how many ways are there to make change using pennies, nickels, dimes, and quarters? What if you are given a different amount of money? What if you use different coin denominations? This is a well known problem and formulas are known. We present simpler proofs in several cases. We use recurrences to derive formulas if the coin denominations are {1,x,kx,rx}, and we use a simple proof using generating functions to derive a formula for any coin set.
mathematical-recreations  puzzles  number-theory  nudge-targets  consider:looking-to-see  consider:symbolic-regression  consider:novelty-search 
4 days ago
[1406.2212] A Markov Chain Analysis of a Pattern Matching Coin Game
In late May of 2014 I received an email from a colleague introducing to me a non-transitive game developed by Walter Penney. This paper explores this probability game from the perspective of a coin tossing game, and further discusses some similarly interesting properties arising out of a Markov Chain analysis. In particular, we calculate the number of "rounds" that are expected to be played in each variation of the game by leveraging the fundamental matrix. Additionally, I derive a novel method for calculating the probabilistic advantage obtained by the player following Penney's strategy. I also produce an exhaustive proof that Penney's strategy is optimal for his namesake game.
game-theory  mathematical-recreations  nudge-targets  consider:looking-to-see  to-write-about 
4 days ago
[1703.02671] Symmetric Assembly Puzzles are Hard, Beyond a Few Pieces
We study the complexity of symmetric assembly puzzles: given a collection of simple polygons, can we translate, rotate, and possibly flip them so that their interior-disjoint union is line symmetric? On the negative side, we show that the problem is strongly NP-complete even if the pieces are all polyominos. On the positive side, we show that the problem can be solved in polynomial time if the number of pieces is a fixed constant.
puzzles  computational-complexity  rather-interesting  nudge-targets  consider:looking-to-see  consider:representation  tangrams  to-write-about 
4 days ago
[1208.3663] Space-Time Trade-offs for Stack-Based Algorithms
In memory-constrained algorithms we have read-only access to the input, and the number of additional variables is limited. In this paper we introduce the compressed stack technique, a method that allows to transform algorithms whose space bottleneck is a stack into memory-constrained algorithms. Given an algorithm \alg\ that runs in O(n) time using Θ(n) variables, we can modify it so that it runs in O(n2/s) time using a workspace of O(s) variables (for any s∈o(logn)) or O(nlogn/logp) time using O(plogn/logp) variables (for any 2≤p≤n). We also show how the technique can be applied to solve various geometric problems, namely computing the convex hull of a simple polygon, a triangulation of a monotone polygon, the shortest path between two points inside a monotone polygon, 1-dimensional pyramid approximation of a 1-dimensional vector, and the visibility profile of a point inside a simple polygon. Our approach exceeds or matches the best-known results for these problems in constant-workspace models (when they exist), and gives the first trade-off between the size of the workspace and running time. To the best of our knowledge, this is the first general framework for obtaining memory-constrained algorithms.
computational-complexity  algorithms  stacks  to-understand  computational-geometry  nudge  to-write-about 
4 days ago
[0806.0928] Drawing Binary Tanglegrams: An Experimental Evaluation
A binary tanglegram is a pair <S,T> of binary trees whose leaf sets are in one-to-one correspondence; matching leaves are connected by inter-tree edges. For applications, for example in phylogenetics or software engineering, it is required that the individual trees are drawn crossing-free. A natural optimization problem, denoted tanglegram layout problem, is thus to minimize the number of crossings between inter-tree edges.
The tanglegram layout problem is NP-hard and is currently considered both in application domains and theory. In this paper we present an experimental comparison of a recursive algorithm of Buchin et al., our variant of their algorithm, the algorithm hierarchy sort of Holten and van Wijk, and an integer quadratic program that yields optimal solutions.
graph-layout  algorithms  visualization  optimization  rather-interesting  to-write-about  nudge-targets  consider:looking-to-see 
4 days ago
mathrecreation: polynomial grid division examples
There are not enough examples of polynomial division using the grid method out there. To remedy that, I have posted about 100 billion examples for your viewing pleasure. Please check ‘em out: https://dmackinnon1.github.io/polygrid/

Jokes aside, I was looking for a small JavaScript project, and this one looked like it would be fun. It was, and I learned a few things by building it. The page will generate a small number of examples, but you can get a fresh batch by reloading. Each example is calculated on the fly, and rendered using MathJax. Currently, the displayed calculations look like this:
matrices  javascript  visualization  nudge-targets  to-write-about  algorithms 
4 days ago
[1606.06940] Minimum Rectilinear Polygons for Given Angle Sequences
A rectilinear polygon is a polygon whose edges are axis-aligned. Walking counterclockwise on the boundary of such a polygon yields a sequence of left turns and right turns. The number of left turns always equals the number of right turns plus 4. It is known that any such sequence can be realized by a rectilinear polygon. In this paper, we consider the problem of finding realizations that minimize the perimeter or the area of the polygon or the area of the bounding box of the polygon. We show that all three problems are NP-hard in general. Then we consider the special cases of x-monotone and xy-monotone rectilinear polygons. For these, we can optimize the three objectives efficiently.
optimization  computational-geometry  inverse-problems  rather-interesting  constraint-satisfaction  nudge-targets  consider:looking-to-see  consider:feature-discovery 
4 days ago
[1509.02627] Rectilinear convex hull with minimum area
Let P be a planar set of n points in general position. We consider the problem of computing an orientation of the plane for which the Rectilinear Convex Hull of P has minimum area. Bae et al. (Computational Geometry: Theory and Applications, Vol. 42, 2009) solved the problem in quadratic time and linear space. We describe an algorithm that reduces this time complexity to Θ(nlogn).
computational-geometry  rather-interesting  optimization  convex-hulls  constraint-satisfaction  nudge-targets  consider:looking-to-see  consider:feature-discovery 
5 days ago
[1511.02393] On Stabbing Queries for Generalized Longest Repeat
A longest repeat query on a string, motivated by its applications in many subfields including computational biology, asks for the longest repetitive substring(s) covering a particular string position (point query). In this paper, we extend the longest repeat query from point query to \emph{interval query}, allowing the search for longest repeat(s) covering any position interval, and thus significantly improve the usability of the solution. Our method for interval query takes a different approach using the insight from a recent work on \emph{shortest unique substrings} [1], as the prior work's approach for point query becomes infeasible in the setting of interval query. Using the critical insight from [1], we propose an indexing structure, which can be constructed in the optimal O(n) time and space for a string of size n, such that any future interval query can be answered in O(1) time. Further, our solution can find \emph{all} longest repeats covering any given interval using optimal O(occ) time, where occ is the number of longest repeats covering that given interval, whereas the prior O(n)-time and space work can find only one candidate for each point query. Experiments with real-world biological data show that our proposal is competitive with prior works, both time and space wise, while providing with the new functionality of interval queries as opposed to point queries provided by prior works.
strings  bioinformatics  search-algorithms  algorithms  computational-complexity  nudge-targets  consider:looking-to-see 
5 days ago
[0707.0610] Unfolding Orthogonal Terrains
It is shown that every orthogonal terrain, i.e., an orthogonal (right-angled) polyhedron based on a rectangle that meets every vertical line in a segment, has a grid unfolding: its surface may be unfolded to a single non-overlapping piece by cutting along grid edges defined by coordinate planes through every vertex.
computational-geometry  just-plain-neat  to-write-about  unfoldings 
5 days ago
[1007.3181] On Folding a Polygon to a Polyhedron
We show that the open problem presented in "Geometric Folding Algorithms: Linkages, Origami, Polyhedra" [DO07] is solved by a theorem of Burago and Zalgaller [BZ96] from more than a decade earlier.
computational-geometry  rather-interesting  polygons  polyhedra  proof  to-write-about 
5 days ago
[1205.5162] Coloring and Guarding Arrangements
Given an arrangement of lines in the plane, what is the minimum number c of colors required to color the lines so that no cell of the arrangement is monochromatic? In this paper we give bounds on the number c both for the above question, as well as some of its variations. We redefine these problems as geometric hypergraph coloring problems. If we define $\Hlinecell$ as the hypergraph where vertices are lines and edges represent cells of the arrangement, the answer to the above question is equal to the chromatic number of this hypergraph. We prove that this chromatic number is between Ω(logn/loglogn). and O(n‾√).
Similarly, we give bounds on the minimum size of a subset S of the intersections of the lines in  such that every cell is bounded by at least one of the vertices in S. This may be seen as a problem on guarding cells with vertices when the lines act as obstacles. The problem can also be defined as the minimum vertex cover problem in the hypergraph $\Hvertexcell$, the vertices of which are the line intersections, and the hyperedges are vertices of a cell. Analogously, we consider the problem of touching the lines with a minimum subset of the cells of the arrangement, which we identify as the minimum vertex cover problem in the $\Hcellzone$ hypergraph.
computational-geometry  graph-theory  constraint-satisfaction  hypergraphs  nudge-targets  consider:looking-to-see 
5 days ago
[0807.0552] Decomposition of Multiple Coverings into More Parts
We prove that for every centrally symmetric convex polygon Q, there exists a constant alpha such that any alpha*k-fold covering of the plane by translates of Q can be decomposed into k coverings. This improves on a quadratic upper bound proved by Pach and Toth (SoCG'07). The question is motivated by a sensor network problem, in which a region has to be monitored by sensors with limited battery lifetime.
computational-geometry  coverings  plane-geometry  rather-interesting  to-write-about  nudge-targets  consider:looking-to-see 
5 days ago
[0908.2442] Detecting all regular polygons in a point set
In this paper, we analyze the time complexity of finding regular polygons in a set of n points. We combine two different approaches to find regular polygons, depending on their number of edges. Our result depends on the parameter alpha, which has been used to bound the maximum number of isosceles triangles that can be formed by n points. This bound has been expressed as O(n^{2+2alpha+epsilon}), and the current best value for alpha is ~0.068.
Our algorithm finds polygons with O(n^alpha) edges by sweeping a line through the set of points, while larger polygons are found by random sampling. We can find all regular polygons with high probability in O(n^{2+alpha+epsilon}) expected time for every positive epsilon. This compares well to the O(n^{2+2alpha+epsilon}) deterministic algorithm of Brass.
computational-geometry  algorithms  nudge-targets  consider:looking-to-see  consider:classification  consider:representation 
5 days ago
[1612.03638] Intersection Graphs of Rays and Grounded Segments
We consider several classes of intersection graphs of line segments in the plane and prove new equality and separation results between those classes. In particular, we show that: (1) intersection graphs of grounded segments and intersection graphs of downward rays form the same graph class, (2) not every intersection graph of rays is an intersection graph of downward rays, and (3) not every intersection graph of rays is an outer segment graph. The first result answers an open problem posed by Cabello and Jej\v{c}i\v{c}. The third result confirms a conjecture by Cabello. We thereby completely elucidate the remaining open questions on the containment relations between these classes of segment graphs. We further characterize the complexity of the recognition problems for the classes of outer segment, grounded segment, and ray intersection graphs. We prove that these recognition problems are complete for the existential theory of the reals. This holds even if a 1-string realization is given as additional input.
computational-geometry  graph-theory  nudge-targets  consider:looking-to-see  consider:classification  consider:transformation-function-from-rays-to-segments 
5 days ago
[0806.1416] Highway Hull Revisited
A highway H is a line in the plane on which one can travel at a greater speed than in the remaining plane. One can choose to enter and exit H at any point. The highway time distance between a pair of points is the minimum time required to move from one point to the other, with optional use of H.
The highway hull HH(S,H) of a point set S is the minimal set containing S as well as the shortest paths between all pairs of points in HH(S,H), using the highway time distance.
We provide a Theta(n log n) worst-case time algorithm to find the highway hull under the L_1 metric, as well as an O(n log^2 n) time algorithm for the L_2 metric which improves the best known result of O(n^2).
We also define and construct the useful region of the plane: the region that a highway must intersect in order that the shortest path between at least one pair of points uses the highway.
metrics  computational-geometry  optimization  rather-interesting  mathematical-recreations  to-write-about  consider:planning  consider:highway-positioning 
5 days ago
[cs/9906022] Zero-Parity Stabbing Information
Everett et al. introduced several varieties of stabbing information for the lines determined by pairs of vertices of a simple polygon P, and established their relationships to vertex visibility and other combinatorial data. In the same spirit, we define the ``zero-parity (ZP) stabbing information'' to be a natural weakening of their ``weak stabbing information,'' retaining only the distinction among {zero, odd, even>0} in the number of polygon edges stabbed. Whereas the weak stabbing information's relation to visibility remains an open problem, we completely settle the analogous questions for zero-parity information, with three results: (1) ZP information is insufficient to distinguish internal from external visibility graph edges; (2) but it does suffice for all polygons that avoid a certain complex substructure; and (3) the natural generalization of ZP information to the continuous case of smooth curves does distinguish internal from external visibility.
computational-geometry  feature-construction  polygons  plane-geometry  rather-interesting  nudge-targets  consider:looking-to-see  consider:counterexamples 
5 days ago
“Excellence R Us”: university research and the fetishisation of excellence : Palgrave Communications
The rhetoric of “excellence” is pervasive across the academy. It is used to refer to research outputs as well as researchers, theory and education, individuals and organizations, from art history to zoology. But does “excellence” actually mean anything? Does this pervasive narrative of “excellence” do any good? Drawing on a range of sources we interrogate “excellence” as a concept and find that it has no intrinsic meaning in academia. Rather it functions as a linguistic interchange mechanism. To investigate whether this linguistic function is useful we examine how the rhetoric of excellence combines with narratives of scarcity and competition to show that the hyper-competition that arises from the performance of “excellence” is completely at odds with the qualities of good research. We trace the roots of issues in reproducibility, fraud, and homophily to this rhetoric. But we also show that this rhetoric is an internal, and not primarily an external, imposition. We conclude by proposing an alternative rhetoric based on soundness and capacity-building. In the final analysis, it turns out that that “excellence” is not excellent. Used in its current unqualified form it is a pernicious and dangerous rhetoric that undermines the very foundations of good research and scholarship. This article is published as part of a collection on the future of research assessment.
academia  academic-culture  higher-ed  what-gets-measured-gets-fudged  benchmarking  corporatism 
5 days ago
[1608.03544] On Context-Dependent Clustering of Bandits
We investigate a novel cluster-of-bandit algorithm CAB for collaborative recommendation tasks that implements the underlying feedback sharing mechanism by estimating the neighborhood of users in a context-dependent manner. CAB makes sharp departures from the state of the art by incorporating collaborative effects into inference as well as learning processes in a manner that seamlessly interleaving explore-exploit tradeoffs and collaborative steps. We prove regret bounds under various assumptions on the data, which exhibit a crisp dependence on the expected number of clusters over the users, a natural measure of the statistical difficulty of the learning task. Experiments on production and real-world datasets show that CAB offers significantly increased prediction performance against a representative pool of state-of-the-art methods.
recommendations  exploration  exploitation  machine-learning  algorithms  clustering  rather-interesting  to-understand 
6 days ago
[1605.02424] Learning Discriminative Features with Class Encoder
Deep neural networks usually benefit from unsupervised pre-training, e.g. auto-encoders. However, the classifier further needs supervised fine-tuning methods for good discrimination. Besides, due to the limits of full-connection, the application of auto-encoders is usually limited to small, well aligned images. In this paper, we incorporate the supervised information to propose a novel formulation, namely class-encoder, whose training objective is to reconstruct a sample from another one of which the labels are identical. Class-encoder aims to minimize the intra-class variations in the feature space, and to learn a good discriminative manifolds on a class scale. We impose the class-encoder as a constraint into the softmax for better supervised training, and extend the reconstruction on feature-level to tackle the parameter size issue and translation issue. The experiments show that the class-encoder helps to improve the performance on benchmarks of classification and face recognition. This could also be a promising direction for fast training of face recognition models.
autoencoders  machine-learning  dimension-reduction  rather-interesting  semi-supervised-learning  algorithms  nudge-targets  consider:looking-to-see  consider:as-primitives 
6 days ago
[1605.00596] Graph Clustering Bandits for Recommendation
We investigate an efficient context-dependent clustering technique for recommender systems based on exploration-exploitation strategies through multi-armed bandits over multiple users. Our algorithm dynamically groups users based on their observed behavioral similarity during a sequence of logged activities. In doing so, the algorithm reacts to the currently served user by shaping clusters around him/her but, at the same time, it explores the generation of clusters over users which are not currently engaged. We motivate the effectiveness of this clustering policy, and provide an extensive empirical analysis on real-world datasets, showing scalability and improved prediction performance over state-of-the-art methods for sequential clustering of users in multi-armed bandit scenarios.
recommendations  machine-learning  exploration  exploitation  multiobjective-optimization  to-write-about  rather-interesting 
6 days ago
[1611.09485] Dispersing Points on Intervals
We consider a problem of dispersing points on disjoint intervals on a line. Given n pairwise disjoint intervals sorted on a line, we want to find a point in each interval such that the minimum pairwise distance of these points is maximized. Based on a greedy strategy, we present a linear time algorithm for the problem. Further, we also solve in linear time the cycle version of the problem where the intervals are given on a cycle.
optimization  computational-geometry  operations-research  constraint-satisfaction  rather-interesting  simple-but-hard-problems  nudge-targets  consider:looking-to-see  algorithms  consider:generalization  consider:blocks-in-a-plane 
6 days ago
[0808.1225] Optics-less smart sensors and a possible mechanism of cutaneous vision in nature
Optics-less cutaneous (skin) vision is not rare among living organisms, though its mechanisms and capabilities have not been thoroughly investigated. This paper demonstrates, using methods from statistical parameter estimation theory and numerical simulations, that an array of bare sensors with a natural cosine-law angular sensitivity arranged on a flat or curved surface has the ability to perform imaging tasks without any optics at all. The working principle of this type of optics-less sensor and the model developed here for determining sensor performance may be used to shed light upon possible mechanisms and capabilities of cutaneous vision in nature.
optics  physiology  distributed-processing  rather-interesting  to-write-about  nudge-targets  consider:rediscovery  consider:algorithms 
6 days ago
[1304.3196] Artificial color perception using microwaves
We report the feasibility of artificial color perception under microwave illumination using a standard microwave source and an antenna. We have sensed transmitted microwave power through color objects and have distinguished the colors by analyzing the sensed transmitted power. Experiments are carried out using a Gunn diode as the microwave source, some colored liquids as the objects and a microwave diode as the detector. Results are presented which open up an unusual but new way of perceiving colors using microwaves.
optics  indistinguishable-from-magic  science-fiction-inspirations  rather-interesting  spectroscopy 
6 days ago
[physics/0703096] Computational Vision in Nature and Technology
It is hard for us humans to recognize things in nature until we have invented them ourselves. For image-forming optics, nature has made virtually every kind of lens humans have devised. But what about lensless "imaging"? Recently, we showed that a bare array of sensors on a curved substrate could achieve resolution not limited by diffraction- without any lens at all provided that the objects imaged conform to our a priori assumptions. Is it possible that somewhere in nature we will find this kind of vision system? We think so and provide examples that seem to make no sense whatever unless they are using something like our lensless imaging work.
optics  review  rather-interesting  lensless-imaging  to-write-about  algorithms 
6 days ago
[1610.05834] Lensless Imaging with Compressive Ultrafast Sensing
Conventional imaging uses a set of lenses to form an image on the sensor plane. This pure hardware-based approach doesn't use any signal processing, nor the extra information in the time of arrival of photons to the sensor. Recently, modern compressive sensing techniques have been applied for lensless imaging. However, this computational approach tends to depend as much as possible on signal processing (for example, single pixel camera) and results in a long acquisition time. Here we propose using compressive ultrafast sensing for lensless imaging. We use extremely fast sensors (picosecond time resolution) to time tag photons as they arrive to an omnidirectional pixel. Thus, each measurement produces a time series where time is a function of the photon source location in the scene. This allows lensless imaging with significantly fewer measurements compared to regular single pixel imaging (33× less measurements in our experiments). To achieve this goal, we developed a framework for using ultrafast pixels with compressive sensing, including an algorithm for ideal sensor placement, and an algorithm for optimized active illumination patterns. We show that efficient lensless imaging is possible with ultrafast imaging and compressive sensing. This paves the way for novel imaging architectures, and remote sensing in extreme situations where imaging with a lens is not possible.
optics  indistinguishable-from-magic  inverse-problems  compressed-sensing  rather-interesting  to-understand 
6 days ago
[1702.08516] Lensless computational imaging through deep learning
Deep learning has been proven to yield reliably generalizable answers to numerous classification and decision tasks. Here, we demonstrate for the first time, to our knowledge, that deep neural networks (DNNs) can be trained to solve inverse problems in computational imaging. We experimentally demonstrate a lens-less imaging system where a DNN was trained to recover a phase object given a raw intensity image recorded some distance away.
image-processing  rather-interesting  deep-learning  inverse-problems  optics  inference  to-understand 
6 days ago
[1611.05571] Random matrix approach to estimation of high-dimensional factor models
In dealing with high-dimensional data sets, factor models are often useful for dimension reduction. The estimation of factor models has been actively studied in various fields. In the first part of this paper, we present a new approach to estimate high-dimensional factor models, using the empirical spectral density of residuals. The spectrum of covariance matrices from financial data typically exhibits two characteristic aspects: a few spikes and bulk. The former represent factors that mainly drive the features and the latter arises from idiosyncratic noise. Motivated by these two aspects, we consider a minimum distance between two spectrums; one from a covariance structure model and the other from real residuals of financial data that are obtained by subtracting principal components. Our method simultaneously provides estimators of the number of factors and information about correlation structures in residuals. Using free random variable techniques, the proposed algorithm can be implemented and controlled effectively. Monte Carlo simulations confirm that our method is robust to noise or the presence of weak factors. Furthermore, the application to financial time-series shows that our estimators capture essential aspects of market dynamics.
time-series  probability-theory  modeling  dimension-reduction  random-matrices  to-understand  statistics  algorithms 
6 days ago
[1702.07916] Random ultrametric trees and applications
Ultrametric trees are trees whose leaves lie at the same distance from the root. They are used to model the genealogy of a population of particles co-existing at the same point in time. We show how the boundary of an ultrametric tree, like any compact ultrametric space, can be represented in a simple way via the so-called comb metric. We display a variety of examples of random combs and explain how they can be used in applications. In particular, we review some old and recent results regarding the genetic structure of the population when throwing neutral mutations on the skeleton of the tree.
probability-theory  trees  to-understand  consider:random-mutations  consider:variation-operators 
6 days ago
[1701.03461] Rules for Folding Polyminoes from One Level to Two Levels
Polyominoes have been the focus of many recreational and research investigations. In this article, the authors investigate whether a paper cutout of a polyomino can be folded to produce a second polyomino in the same shape as the original, but now with two layers of paper. For the folding, only "corner folds" and "half edge cuts" are allowed, unless the polyomino forms a closed loop, in which case one is allowed to completely cut two squares in the polyomino apart. With this set of allowable moves, the authors present algorithms for folding different types of polyominoes and prove that certain polyominoes can successfully be folded to two layers. The authors also establish that other polyominoes cannot be folded to two layers if only these moves are allowed.
polyominoes  folding  mathematical-recreations  rather-interesting  hard-problems 
6 days ago
« earlier      
academia academic-culture activism advice agent-based agility algorithms amusing ann-arbor approximation architecture archive art artificial-intelligence artificial-life bankers-should-start-avoiding-lampposts-right-about-now 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 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 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 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 investment javascript 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 music 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 testing the-mangle-in-practice theoretical-biology tiling time-series to-read to-understand to-write-about tools trading typography user-experience via:cshalizi video visualization web-design web2.0 worklife writing

Copy this bookmark: