abscondment/clj-kdtree: kd-trees in Clojure

3 days ago

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

3 days ago

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

3 days ago

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

3 days ago

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

3 days ago

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

3 days ago

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

[1611.10055] How bees and foams respond to curved confinement: level set boundary representations in the Surface Evolver

3 days ago

"Ultimately, we believe that the strongly curved surface proved to much of a frustration to the bees…"

BEES!
packing
self-organization
rather-interesting
experiment
soap-bubbles
3 days ago

[1612.00197] Learning in an Uncertain World: Representing Ambiguity Through Multiple Hypotheses

3 days ago

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

3 days ago

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

3 days ago

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

3 days ago

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

3 days ago

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

3 days ago

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

3 days ago

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

3 days ago

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

3 days ago

[1702.07969] Related Pins at Pinterest: The Evolution of a Real-World Recommender System

3 days ago

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

3 days ago

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

3 days ago

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

3 days ago

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

3 days ago

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

3 days ago

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

Tanya Khovanova's Math Blog » Blog Archive » My Favorite Problems from the Moscow Math Olympiad 2016

3 days ago

I picked four problems that I liked from the Moscow Math Olympiad 2016:

mathematical-recreations
puzzles
to-write-about
nudge-targets
consider:looking-to-see
3 days ago

[1612.08220] Understanding Neural Networks through Representation Erasure

3 days ago

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

3 days ago

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

3 days ago

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

4 days ago

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

4 days ago

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

4 days ago

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

4 days ago

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
Keywords and phrases: day of the week, calendar algorithms, doomsday method, first Sunday algorithm, mental arithmetic, year share

4 days ago

[1604.01760] Solving Diophantine Equations

4 days ago

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

4 days ago

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

4 days ago

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

4 days ago

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

4 days ago

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

4 days ago

[1505.00446] Tessellations and Positional Representation

4 days ago

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

4 days ago

[1605.00180] Counting the number of isosceles triangles in rectangular regular grids

4 days ago

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

4 days ago

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

4 days ago

[1609.05240] A Computation in a Cellular Automaton Collider Rule 110

4 days ago

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

4 days ago

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

4 days ago

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

4 days ago

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

4 days ago

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

4 days ago

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

4 days ago

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

4 days ago

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

4 days ago

[1212.2846] Expressiveness of Elementary Cellular Automata

4 days ago

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

4 days ago

[1106.3046] Computation with competing patterns in Life-like automaton

4 days ago

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

4 days ago

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}

4 days ago

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"

4 days ago

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

4 days ago

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

4 days ago

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

4 days ago

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

4 days ago

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

4 days ago

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

4 days ago

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

4 days ago

mathrecreation: polynomial grid division examples

4 days ago

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

4 days ago

[1606.06940] Minimum Rectilinear Polygons for Given Angle Sequences

4 days ago

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

5 days ago

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

5 days ago

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

5 days ago

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

5 days ago

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

5 days ago

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

5 days ago

[0807.0552] Decomposition of Multiple Coverings into More Parts

5 days ago

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

5 days ago

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

5 days ago

[1612.03638] Intersection Graphs of Rays and Grounded Segments

5 days ago

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

5 days ago

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

5 days ago

[cs/9906022] Zero-Parity Stabbing Information

5 days ago

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

5 days ago

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

6 days ago

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

6 days ago

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

6 days ago

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

6 days ago

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

6 days ago

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

6 days ago

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

6 days ago

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

6 days ago

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

6 days ago

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

6 days ago

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

6 days ago

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

6 days ago

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

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