Vaguery + consider:feature-discovery   272

 « earlier
[1808.06013] Realization and Connectivity of the Graphs of Origami Flat Foldings
We investigate the graphs formed from the vertices and creases of an origami pattern that can be folded flat along all of its creases. As we show, this is possible for a tree if and only if the internal vertices of the tree all have even degree greater than two. However, we prove that (for unbounded sheets of paper, with a vertex at infinity representing a shared endpoint of all creased rays) the graph of a folding pattern must be 2-vertex-connected and 4-edge-connected.
origami  constraint-satisfaction  graph-theory  computational-geometry  rather-interesting  nudge-targets  consider:looking-to-see  consider:feature-discovery
13 days ago by Vaguery
[1809.04881] The Zeckendorf Game
Zeckendorf proved that every positive integer n can be written uniquely as the sum of non-adjacent Fibonacci numbers. We use this to create a two-player game. Given a fixed integer n and an initial decomposition of n=nF1, the two players alternate by using moves related to the recurrence relation Fn+1=Fn+Fn−1, and whoever moves last wins. The game always terminates in the Zeckendorf decomposition, though depending on the choice of moves the length of the game and the winner can vary. We find upper and lower bounds on the number of moves possible. The upper bound is on the order of nlogn, and the lower bound is sharp at n−Z(n) moves, where Z(n) is the number of terms in the Zeckendorf decomposition of n. Notably, Player 2 has the winning strategy for all n>2; interestingly, however, the proof is non-constructive.
number-theory  game-theory  rather-interesting  nudge-targets  consider:feature-discovery
6 weeks ago by Vaguery
[0909.5452] Palindromes in Different Bases: A Conjecture of J. Ernest Wilkins
We show that there exist exactly 203 positive integers N such that for some integer d≥2 this number is a d-digit palindrome base 10 as well as a d-digit palindrome for some base b different from 10. To be more precise, such N range from 22 to 9986831781362631871386899.
number-theory  palindromes  mathematical-recreations  open-questions  to-write-about  consider:feature-discovery
7 weeks ago by Vaguery
[1512.01289] Predicting and visualizing psychological attributions with a deep neural network
Judgments about personality based on facial appearance are strong effectors in social decision making, and are known to have impact on areas from presidential elections to jury decisions. Recent work has shown that it is possible to predict perception of memorability, trustworthiness, intelligence and other attributes in human face images. The most successful of these approaches require face images expertly annotated with key facial landmarks. We demonstrate a Convolutional Neural Network (CNN) model that is able to perform the same task without the need for landmark features, thereby greatly increasing efficiency. The model has high accuracy, surpassing human-level performance in some cases. Furthermore, we use a deconvolutional approach to visualize important features for perception of 22 attributes and demonstrate a new method for separately visualizing positive and negative features.
face-recognition  neural-networks  rather-interesting  cultural-norms  social-psychology  psychology  to-write-about  consider:feature-discovery
7 weeks ago by Vaguery
[1709.09683] Exact Camera Location Recovery by Least Unsquared Deviations
We establish exact recovery for the Least Unsquared Deviations (LUD) algorithm of Ozyesil and Singer. More precisely, we show that for sufficiently many cameras with given corrupted pairwise directions, where both camera locations and pairwise directions are generated by a special probabilistic model, the LUD algorithm exactly recovers the camera locations with high probability. A similar exact recovery guarantee was established for the ShapeFit algorithm by Hand, Lee and Voroninski, but with typically less corruption.
inverse-problems  image-processing  rather-interesting  benchmarking  nudge-targets  consider:feature-discovery  consider:rediscovery
7 weeks ago by Vaguery
[1509.00488] The Tournament Scheduling Problem with Absences
We study time scheduling problems with allowed absences as a new kind of graph coloring problem. One may think of a sport tournament where each player (each team) is permitted a certain number t of absences. We then examine how many rounds are needed to schedule the whole tournament in the worst case. This upper limit depends on t and on the structure of the graph G whose edges represent the games that have to be played, but also on whether or not the absences are announced before the tournament starts. Therefore, we actually have two upper limits for the number of required rounds. We have χt(G) for pre-scheduling if all absences are pre-fixed, and we have χtOL(G) for on-line scheduling if we have to stay flexible and deal with absences when they occur. We conjecture that χt(G)=Δ(G)+2t and that χtOL(G)=χ′(G)+2t. The first conjecture is stronger than the Total Coloring Conjecture while the second is weaker than the On-Line List Edge Coloring Conjecture. Our conjectures hold for all bipartite graphs. For complete graphs, we prove them partially. Lower and upper bounds to χt(G) and χtOL(G) for general multigraphs G are established, too.
combinatorics  graph-theory  graph-coloring  enumeration  queueing-theory  constraint-satisfaction  to-simulate  to-write-about  consider:looking-to-see  consider:feature-discovery
8 weeks ago by Vaguery
[1804.00947] The Transactional Conflict Problem
The transactional conflict problem arises in transactional systems whenever two or more concurrent transactions clash on a data item.
While the standard solution to such conflicts is to immediately abort one of the transactions, some practical systems consider the alternative of delaying conflict resolution for a short interval, which may allow one of the transactions to commit. The challenge in the transactional conflict problem is to choose the optimal length of this delay interval so as to minimize the overall running time penalty for the conflicting transactions. In this paper, we propose a family of optimal online algorithms for the transactional conflict problem.
Specifically, we consider variants of this problem which arise in different implementations of transactional systems, namely "requestor wins" and "requestor aborts" implementations: in the former, the recipient of a coherence request is aborted, whereas in the latter, it is the requestor which has to abort. Both strategies are implemented by real systems.
We show that the requestor aborts case can be reduced to a classic instance of the ski rental problem, while the requestor wins case leads to a new version of this classical problem, for which we derive optimal deterministic and randomized algorithms.
Moreover, we prove that, under a simplified adversarial model, our algorithms are constant-competitive with the offline optimum in terms of throughput.
We validate our algorithmic results empirically through a hardware simulation of hardware transactional memory (HTM), showing that our algorithms can lead to non-trivial performance improvements for classic concurrent data structures.
concurrency  distributed-processing  constraint-satisfaction  asynchronous-dynamics  heuristics  game-theory  mechanism-design  to-simulate  consider:genetic-programming  consider:performance-measures  consider:feature-discovery
8 weeks ago by Vaguery
[1812.07014] Tiling an Equilateral Triangle
Let ABC be an equilateral triangle. For certain triangles T (the "tile") and certain N, it is possible to cut ABC into N copies of T. It is known that only certain shapes of T are possible, but until now very little was known about the possible values of N. Here we prove that for N>3, N cannot be prime.
tiling  combinatorics  constraint-satisfaction  plane-geometry  rather-interesting  to-write-about  to-do  to-simulate  consider:looking-to-see  consider:genetic-programming  consider:rediscovery  consider:feature-discovery
8 weeks ago by Vaguery
[1809.07481] $L_1$ Shortest Path Queries in Simple Polygons
Let P be a simple polygon of n vertices. We consider two-point L1 shortest path queries in P. We build a data structure of O(n) size in O(n) time such that given any two query points s and t, the length of an L1 shortest path from s to t in P can be computed in O(logn) time, or in O(1) time if both s and t are vertices of P, and an actual shortest path can be output in additional linear time in the number of edges of the path. To achieve the result, we propose a mountain decomposition of simple polygons, which may be interesting in its own right. Most importantly, our approach is much simpler than the previous work on this problem.
computational-geometry  planning  algorithms  computational-complexity  representation  to-write-about  consider:feature-discovery
december 2018 by Vaguery
[1801.08056] The ascent-plateau statistics on Stirling permutations
In this paper, several variants of the ascent-plateau statistic are introduced, including flag ascent-plateau, double ascent and descent-plateau. We first study the flag ascent-plateau statistic on Stirling permutations by using context-free grammars. We then present a unified refinement of the ascent polynomials and the ascent-plateau polynomials. In particular, by using Foata and Strehl's group action, we prove two bistatistics over the set of Stirling permutations of order n are equidistributed.
combinatorics  permutations  enumeration  probability-theory  to-understand  nudge-targets  consider:feature-discovery
december 2018 by Vaguery
[1803.11463] Arctic curves for paths with arbitrary starting points: a tangent method approach
We use the tangent method to investigate the arctic curve in a model of non-intersecting lattice paths with arbitrary fixed starting points aligned along some boundary and whose distribution is characterized by some arbitrary piecewise differentiable function. We find that the arctic curve has a simple explicit parametric representation depending of this function, providing us with a simple transform that maps the arbitrary boundary condition to the arctic curve location. We discuss generic starting point distributions as well as particular freezing ones which create additional frozen domains adjacent to the boundary, hence new portions for the arctic curve. A number of examples are presented, corresponding to both generic and freezing distributions.
combinatorics  arctic-curves  tiling  statistical-mechanics  simulation  looking-to-see  feature-construction  emergence  to-write-about  consider:prediction  consider:feature-discovery
december 2018 by Vaguery
[1809.07390] A general framework for secondary constructions of bent and plateaued functions
In this work, we employ the concept of {\em composite representation} of Boolean functions, which represents an arbitrary Boolean function as a composition of one Boolean function and one vectorial function, for the purpose of specifying new secondary constructions of bent/plateaued functions. This representation gives a better understanding of the existing secondary constructions and it also allows us to provide a general construction framework of these objects. This framework essentially gives rise to an {\em infinite number} of possibilities to specify such secondary construction methods (with some induced sufficient conditions imposed on initial functions) and in particular we solve several open problems in this context. We provide several explicit methods for specifying new classes of bent/plateaued functions and demonstrate through examples that the imposed initial conditions can be easily satisfied. Our approach is especially efficient when defining new bent/plateaued functions on larger variable spaces than initial functions. For instance, it is shown that the indirect sum methods and Rothaus' construction are just special cases of this general framework and some explicit extensions of these methods are given. In particular, similarly to the basic indirect sum method of Carlet, we show that it is possible to derive (many) secondary constructions of bent functions without any additional condition on initial functions apart from the requirement that these are bent functions. In another direction, a few construction methods that generalize the secondary constructions which do not extend the variable space of the employed initial functions are also proposed.
representation  boolean-functions  decomposition  construction  inverse-problems  rather-interesting  Walsh-polynomials  to-write-about  consider:feature-discovery
december 2018 by Vaguery
[1810.04692] Probability distributions related to tilings of non-convex Polygons
This paper is based on the study of random lozenge tilings of non-convex polygonal regions with interacting non-convexities (cuts) and the corresponding asymptotic kernel as in  and  (discrete tacnode kernel). Here this kernel is used to find the probability distributions and joint probability distributions for the fluctuation of tiles along lines in between the cuts. These distributions are new.
combinatorics  tiling  counting  rather-interesting  phase-transitions  condensed-matter  statistical-mechanics  feature-extraction  representation  to-write-about  consider:feature-discovery
december 2018 by Vaguery
[1806.01378] Strong Pseudo Transitivity and Intersection Graphs
A directed graph G=(V,E) is {\it strongly pseudo transitive} if there is a partition {A,E−A} of E so that graphs G1=(V,A) and G2=(V,E−A) are transitive, and additionally, if ab∈A and bc∈E implies that ac∈E. A strongly pseudo transitive graph G=(V,E) is strongly pseudo transitive of the first type, if ab∈A and bc∈E implies ac∈A. An undirected graph is co-strongly pseudo transitive (co-strongly pseudo transitive of the first type) if its complement has an orientation which is strongly pseudo transitive (co-strongly pseudo transitive of the first type). Our purpose is show that the results in computational geometry \cite{CFP, Lu} and intersection graph theory \cite{Ga2, ES} can be unified and extended, using the notion of strong pseudo transitivity. As a consequence the general algorithmic framework in \cite{Sh} is applicable to solve the maximum independent set in O(n3) time in a variety of problems, thereby, avoiding case by case lengthily arguments for each problem. We show that the intersection graphs of axis parallel rectangles intersecting a diagonal line from bottom, and half segments are co-strongly pseudo transitive. In addition, we show that the class of the interval filament graphs is co-strongly transitive of the first type, and hence the class of polygon circle graphs which is contained in the class of interval filament graphs (but contains the classes of chordal graphs, circular arc, circle, and outer planar graphs), and the class of incomparability graphs are strongly transitive of the first type. For class of chordal graphs we give two different proofs, using two different characterizations, verifying that they are co-strongly transitive of the first type. We present some containment results.
graph-theory  feature-extraction  feature-construction  algorithms  computational-complexity  nudge-targets  consider:feature-discovery
december 2018 by Vaguery
[1811.03516] Learning from Demonstration in the Wild
Learning from demonstration (LfD) is useful in settings where hand-coding behaviour or a reward function is impractical. It has succeeded in a wide range of problems but typically relies on artificially generated demonstrations or specially deployed sensors and has not generally been able to leverage the copious demonstrations available in the wild: those that capture behaviour that was occurring anyway using sensors that were already deployed for another purpose, e.g., traffic camera footage capturing demonstrations of natural behaviour of vehicles, cyclists, and pedestrians. We propose video to behaviour (ViBe), a new approach to learning models of road user behaviour that requires as input only unlabelled raw video data of a traffic scene collected from a single, monocular, uncalibrated camera with ordinary resolution. Our approach calibrates the camera, detects relevant objects, tracks them through time, and uses the resulting trajectories to perform LfD, yielding models of naturalistic behaviour. We apply ViBe to raw videos of a traffic intersection and show that it can learn purely from videos, without additional expert knowledge.
machine-learning  learning-by-watching  training  deep-learning  to-write-about  consider:representation  consider:feature-discovery
november 2018 by Vaguery
Evolution of metazoan morphological disparity | PNAS
We attempt to quantify animal “bodyplans” and their variation within Metazoa. Our results challenge the view that maximum variation was achieved early in animal evolutionary history by nonuniformitarian mechanisms. Rather, they are compatible with the view that the capacity for fundamental innovation is not limited to the early evolutionary history of clades. We perform quantitative tests of the principal hypotheses of the molecular mechanisms underpinning the establishment of animal bodyplans and corroborate the hypothesis that animal evolution has been permitted or driven by gene regulatory evolution.
developmental-biology  biology  rather-interesting  clustering  looking-to-see  to-write-about  consider:feature-discovery
october 2018 by Vaguery
[1512.04722] Visible lattice points in random walks
We consider the possible visits to visible points of a random walker moving up and right in the integer lattice (with probability α and 1−α, respectively) and starting from the origin.
We show that, almost surely, the asymptotic proportion of strings of k consecutive visible lattice points visited by such an α-random walk is a certain constant ck(α), which is actually an (explicitly calculable) polynomial in α of degree 2⌊(k−1)/2⌋. For k=1, this gives that, almost surely, the asymptotic proportion of time the random walker is visible from the origin is c1(α)=6/π2, independently of α.
random-walks  rather-interesting  combinatorics  probability-theory  simulation  nudge-targets  number-theory  representation  to-simulate  consider:feature-discovery
october 2018 by Vaguery
We define a plane curve to be threadable if it can rigidly pass through a point-hole in a line L without otherwise touching L. Threadable curves are in a sense generalizations of monotone curves. We have two main results. The first is a linear-time algorithm for deciding whether a polygonal curve is threadable---O(n) for a curve of n vertices---and if threadable, finding a sequence of rigid motions to thread it through a hole. We also sketch an argument that shows that the threadability of algebraic curves can be decided in time polynomial in the degree of the curve. The second main result is an O(n polylog n)-time algorithm for deciding whether a 3D polygonal curve can thread through hole in a plane in R^3, and if so, providing a description of the rigid motions that achieve the threading.
computational-geometry  geometry  rather-interesting  definition  nudge-targets  consider:feature-discovery  to-write-about  consider:algorithms
october 2018 by Vaguery
Same-different problems strain convolutional neural networks | the morning paper
Digging deeper, when learning did occur in SD, increasing item size never strained performance. But increasing the overall image size, or increasing the number of items did. (Gray bars in the above figures indicate the number of trials in which learning failed). The results suggest that straining is not simply a direct outcome of an increase in image variability. Using CNNs with more than twice the number of kernels (wide), or twice as many layers (deep) did not change the observed trend.
neural-networks  representation  problem-solving  rather-interesting  ontology  generalization  to-write-about  nudge-targets  consider:feature-discovery
september 2018 by Vaguery
Figuring out when you can do a puzzle. – Occupy Math
This week’s Occupy Math looks at a type of puzzle where you want to fill a rectangle with a shape. We will be using the L-shaped 3-square polyomino, used to fill a 5×9 rectangle below, as our example shape. The goal is to figure out every possible size of rectangle that can be filled with this shape. If you are constructing puzzles for other people — e.g., your students — knowing which problems can be solved gives you an edge. The post will not only solve the problem for our example shape, but also give you tools for doing this for other shapes. The answers, and the tools, are at the bottom if you don’t feel like working through the reasoning.
mathematical-recreations  polyominoes  proof  rather-interesting  nudge-targets  consider:classification  consider:feature-discovery
august 2018 by Vaguery
Kumaraswamy distribution: a beta-like probability density
Maybe the algorithm I suggested for picking parameters is not very good, but I suspect the optimal parameters are not much better. Rather than saying that the Kumaraswamy distribution approximates the beta distribution, I’d say that the Kumaraswamy distribution is capable of assuming roughly the same shapes as the beta distribution. If the only reason you’re using a beta distribution is to get a certain density shape, the Kumaraswamy distribution would be a reasonable alternative. But if you need to approximate a beta distribution closely, it may not work well enough.
probability-theory  representation  rather-interesting  to-write-about  consider:feature-discovery  consider:heuristics  consider:approximation
june 2018 by Vaguery
Exactly how bad is the 13 times table? | The Aperiodical
Along the way, OEIS editor Charles R Greathouse IV added this intriguing conjecture:

Conjecture: a(n)≤N
for all n
. Perhaps N
can be taken as 81
.
april 2018 by Vaguery
[1709.04109] Empower Sequence Labeling with Task-Aware Neural Language Model
Linguistic sequence labeling is a general modeling approach that encompasses a variety of problems, such as part-of-speech tagging and named entity recognition. Recent advances in neural networks (NNs) make it possible to build reliable models without handcrafted features. However, in many cases, it is hard to obtain sufficient annotations to train these models. In this study, we develop a novel neural framework to extract abundant knowledge hidden in raw texts to empower the sequence labeling task. Besides word-level knowledge contained in pre-trained word embeddings, character-aware neural language models are incorporated to extract character-level knowledge. Transfer learning techniques are further adopted to mediate different components and guide the language model towards the key knowledge. Comparing to previous methods, these task-specific knowledge allows us to adopt a more concise model and conduct more efficient training. Different from most transfer learning methods, the proposed framework does not rely on any additional supervision. It extracts knowledge from self-contained order information of training sequences. Extensive experiments on benchmark datasets demonstrate the effectiveness of leveraging character-level knowledge and the efficiency of co-training. For example, on the CoNLL03 NER task, model training completes in about 6 hours on a single GPU, reaching F1 score of 91.71±0.10 without using any extra annotation.
natural-language-processing  deep-learning  neural-networks  nudge-targets  consider:feature-discovery  consider:representation  to-write-about
march 2018 by Vaguery
Estimating barriers to gene flow from distorted isolation by distance patterns | bioRxiv
In continuous populations with local migration, nearby pairs of individuals have on average more similar genotypes than geographically well separated pairs. A barrier to gene flow distorts this classical pattern of isolation by distance. Genetic similarity is decreased for sample pairs on different sides of the barrier and increased for pairs on the same side near the barrier. Here, we introduce an inference scheme that utilizes this signal to detect and estimate the strength of a linear barrier to gene flow in two-dimensions. We use a diffusion approximation to model the effects of a barrier on the geographical spread of ancestry backwards in time. This approach allows us to calculate the chance of recent coalescence and probability of identity by descent. We introduce an inference scheme that fits these theoretical results to the geographical covariance structure of bialleleic genetic markers. It can estimate the strength of the barrier as well as several demographic parameters. We investigate the power of our inference scheme to detect barriers by applying it to a wide range of simulated data. We also showcase an example application to a Antirrhinum majus (snapdragon) flower color hybrid zone, where we do not detect any signal of a strong genome wide barrier to gene flow.
population-biology  theoretical-biology  rather-interesting  simulation  to-write-about  consider:feature-discovery
march 2018 by Vaguery
[1712.08373] Notes on complexity of packing coloring
A packing k-coloring for some integer k of a graph G=(V,E) is a mapping
φ:V→{1,…,k} such that any two vertices u,v of color φ(u)=φ(v) are in distance at least φ(u)+1. This concept is motivated by frequency assignment problems. The \emph{packing chromatic number} of G is the smallest k such that there exists a packing k-coloring of G.
Fiala and Golovach showed that determining the packing chromatic number for chordal graphs is \NP-complete for diameter exactly 5. While the problem is easy to solve for diameter 2, we show \NP-completeness for any diameter at least 3. Our reduction also shows that the packing chromatic number is hard to approximate within n1/2−ε for any ε>0.
In addition, we design an \FPT algorithm for interval graphs of bounded diameter. This leads us to exploring the problem of finding a partial coloring that maximizes the number of colored vertices.
graph-theory  algorithms  combinatorics  proof  approximation  nudge-targets  consider:looking-to-see  consider:feature-discovery
march 2018 by Vaguery
[1710.02271] Unsupervised Extraction of Representative Concepts from Scientific Literature
This paper studies the automated categorization and extraction of scientific concepts from titles of scientific articles, in order to gain a deeper understanding of their key contributions and facilitate the construction of a generic academic knowledgebase. Towards this goal, we propose an unsupervised, domain-independent, and scalable two-phase algorithm to type and extract key concept mentions into aspects of interest (e.g., Techniques, Applications, etc.). In the first phase of our algorithm we propose PhraseType, a probabilistic generative model which exploits textual features and limited POS tags to broadly segment text snippets into aspect-typed phrases. We extend this model to simultaneously learn aspect-specific features and identify academic domains in multi-domain corpora, since the two tasks mutually enhance each other. In the second phase, we propose an approach based on adaptor grammars to extract fine grained concept mentions from the aspect-typed phrases without the need for any external resources or human effort, in a purely data-driven manner. We apply our technique to study literature from diverse scientific domains and show significant gains over state-of-the-art concept extraction techniques. We also present a qualitative analysis of the results obtained.
natural-language-processing  POS-tagging  algorithms  data-fusion  machine-learning  text-mining  nudge-targets  consider:feature-discovery
february 2018 by Vaguery
[1802.08435] Efficient Neural Audio Synthesis
Sequential models achieve state-of-the-art results in audio, visual and textual domains with respect to both estimating the data distribution and generating high-quality samples. Efficient sampling for this class of models has however remained an elusive problem. With a focus on text-to-speech synthesis, we describe a set of general techniques for reducing sampling time while maintaining high output quality. We first describe a single-layer recurrent neural network, the WaveRNN, with a dual softmax layer that matches the quality of the state-of-the-art WaveNet model. The compact form of the network makes it possible to generate 24kHz 16-bit audio 4x faster than real time on a GPU. Second, we apply a weight pruning technique to reduce the number of weights in the WaveRNN. We find that, for a constant number of parameters, large sparse networks perform better than small dense networks and this relationship holds for sparsity levels beyond 96%. The small number of weights in a Sparse WaveRNN makes it possible to sample high-fidelity audio on a mobile CPU in real time. Finally, we propose a new generation scheme based on subscaling that folds a long sequence into a batch of shorter sequences and allows one to generate multiple samples at once. The Subscale WaveRNN produces 16 samples per step without loss of quality and offers an orthogonal method for increasing sampling efficiency.
audio-synthesis  machine-learning  WaveNet  neural-networks  signal-processing  time-series  generative-models  to-write-about  nudge-targets  recurrent-networks  performance-measure  consider:feature-discovery
february 2018 by Vaguery
[1506.09039] Scalable Discrete Sampling as a Multi-Armed Bandit Problem
Drawing a sample from a discrete distribution is one of the building components for Monte Carlo methods. Like other sampling algorithms, discrete sampling suffers from the high computational burden in large-scale inference problems. We study the problem of sampling a discrete random variable with a high degree of dependency that is typical in large-scale Bayesian inference and graphical models, and propose an efficient approximate solution with a subsampling approach. We make a novel connection between the discrete sampling and Multi-Armed Bandits problems with a finite reward population and provide three algorithms with theoretical guarantees. Empirical evaluations show the robustness and efficiency of the approximate algorithms in both synthetic and real-world large-scale problems.
sampling  inverse-problems  rather-interesting  probability-theory  simulation  engineering-design  nudge-targets  consider:feature-discovery
february 2018 by Vaguery
[1707.05994] Computing Tutte Paths
Tutte paths are one of the most successful tools for attacking Hamiltonicity problems in planar graphs. Unfortunately, results based on them are non-constructive, as their proofs inherently use an induction on overlapping subgraphs and these overlaps hinder to bound the running time to a polynomial. For special cases however, computational results of Tutte paths are known: For 4-connected planar graphs, Tutte paths are in fact Hamiltonian paths and Chiba and Nishizeki showed how to compute such paths in linear time. For 3-connected planar graphs, Tutte paths have a more complicated structure, and it has only recently been shown that they can be computed in polynomial time. However, Tutte paths are defined for general 2-connected planar graphs and this is what most applications need. Unfortunately, no computational results are known. We give the first efficient algorithm that computes a Tutte path (for the general case of 2-connected planar graphs). One of the strongest existence results about such Tutte paths is due to Sanders, which allows to prescribe the end vertices and an intermediate edge of the desired path. Encompassing and strengthening all previous computational results on Tutte paths, we show how to compute this special Tutte path efficiently. Our method refines both, the results of Thomassen and Sanders, and avoids overlapping subgraphs by using a novel iterative decomposition along 2-separators. Finally, we show that our algorithm runs in quadratic time.
graph-theory  algorithms  representation  rather-interesting  to-understand  nudge-targets  consider:representation  consider:feature-discovery
january 2018 by Vaguery
[1710.04640] Hard and Easy Instances of L-Tromino Tilings
In this work we study tilings of regions in the square lattice with L-shaped trominoes. Deciding the existence of a tiling with L-trominoes for an arbitrary region in general is NP-complete, nonetheless, we indentify restrictions to the problem where either it remains NP-complete or it has a polynomial time algorithm. First we show that an aztec diamond of order n always has an L-tromino tiling if and only if n(n+1)≡0mod3; if an aztec diamond has at least two defects or holes, however, the problem of deciding a tiling is NP-complete. Then we study tilings of arbitrary regions where only 180∘ rotations of L-trominoes are available. For this particular case we show that deciding the existence of a tiling remains NP-complete, yet, if a region contains certain so-called "forbidden polyominoes" as subregions, then there exists a polynomial time algorithm for deciding a tiling.
polyominoes  tiling  benchmarking  rather-interesting  problem-solving  nudge-targets  consider:feature-discovery  updated
november 2017 by Vaguery
[1405.2378] Covering Folded Shapes
Can folding a piece of paper flat make it larger? We explore whether a shape S must be scaled to cover a flat-folded copy of itself. We consider both single folds and arbitrary folds (continuous piecewise isometries S→R2). The underlying problem is motivated by computational origami, and is related to other covering and fixturing problems, such as Lebesgue's universal cover problem and force closure grasps. In addition to considering special shapes (squares, equilateral triangles, polygons and disks), we give upper and lower bounds on scale factors for single folds of convex objects and arbitrary folds of simply connected objects.
computational-geometry  to-write  paper-folding  rather-interesting  nudge-targets  consider:algorithms  consider:feature-discovery
november 2017 by Vaguery
[1411.6371] Folding a Paper Strip to Minimize Thickness
In this paper, we study how to fold a specified origami crease pattern in order to minimize the impact of paper thickness. Specifically, origami designs are often expressed by a mountain-valley pattern (plane graph of creases with relative fold orientations), but in general this specification is consistent with exponentially many possible folded states. We analyze the complexity of finding the best consistent folded state according to two metrics: minimizing the total number of layers in the folded state (so that a "flat folding" is indeed close to flat), and minimizing the total amount of paper required to execute the folding (where "thicker" creases consume more paper). We prove both problems strongly NP-complete even for 1D folding. On the other hand, we prove the first problem fixed-parameter tractable in 1D with respect to the number of layers.
paper-folding  computational-geometry  optimization  rather-interesting  to-write-about  to-simulate  nudge-targets  consider:feature-discovery
november 2017 by Vaguery
[1501.00561] A linear-time algorithm for the geodesic center of a simple polygon
Given two points in a simple polygon P of n vertices, its geodesic distance is the length of the shortest path that connects them among all paths that stay within P. The geodesic center of P is the unique point in P that minimizes the largest geodesic distance to all other points of P. In 1989, Pollack, Sharir and Rote [Disc. \& Comput. Geom. 89] showed an O(nlogn)-time algorithm that computes the geodesic center of P. Since then, a longstanding question has been whether this running time can be improved (explicitly posed by Mitchell [Handbook of Computational Geometry, 2000]). In this paper we affirmatively answer this question and present a linear time algorithm to solve this problem.
computational-complexity  computational-geometry  optimization  rather-interesting  algorithms  distance  nudge-targets  consider:rediscovery  consider:feature-discovery
november 2017 by Vaguery
[1604.08797] Ortho-polygon Visibility Representations of Embedded Graphs
An ortho-polygon visibility representation of an n-vertex embedded graph G (OPVR of G) is an embedding-preserving drawing of G that maps every vertex to a distinct orthogonal polygon and each edge to a vertical or horizontal visibility between its end-vertices. The vertex complexity of an OPVR of G is the minimum k such that every polygon has at most k reflex corners. We present polynomial time algorithms that test whether G has an OPVR and, if so, compute one of minimum vertex complexity. We argue that the existence and the vertex complexity of an OPVR of G are related to its number of crossings per edge and to its connectivity. More precisely, we prove that if G has at most one crossing per edge (i.e., G is a 1-plane graph), an OPVR of G always exists while this may not be the case if two crossings per edge are allowed. Also, if G is a 3-connected 1-plane graph, we can compute an OPVR of G whose vertex complexity is bounded by a constant in O(n) time. However, if G is a 2-connected 1-plane graph, the vertex complexity of any OPVR of G may be Ω(n). In contrast, we describe a family of 2-connected 1-plane graphs for which an embedding that guarantees constant vertex complexity can be computed in O(n) time. Finally, we present the results of an experimental study on the vertex complexity of ortho-polygon visibility representations of 1-plane graphs.
graph-layout  computational-geometry  optimization  rather-interesting  to-write-about  nudge-targets  consider:representation  consider:feature-discovery  algorithms  computational-complexity
november 2017 by Vaguery
[1609.06972] Minimal completely asymmetric (4,n)-regular matchstick graphs
A matchstick graph is a graph drawn with straight edges in the plane such that the edges have unit length, and non-adjacent edges do not intersect. We call a matchstick graph $(m,n)$-regular if every vertex has only degree $m$ or $n$. In this article we present the latest known $(4,n)$-regular matchstick graphs for $4\leq n\leq11$ with a minimum number of vertices and a completely asymmetric structure. We call a matchstick graph completely asymmetric, if the following conditions are complied. 1) The graph is rigid. 2) The graph has no point, rotational or mirror symmetry. 3) The graph has an asymmetric outer shape. 4) The graph can not be decomposed into rigid subgraphs and rearrange to a similar graph which contradicts to any of the other conditions.
computational-geometry  graph-theory  rather-interesting  purdy-pitchers  to-write-about  nudge-targets  consider:looking-to-see  consider:feature-discovery
october 2017 by Vaguery
[1512.03421] The extended 1-perfect trades in small hypercubes
An extended 1-perfect trade is a pair (T0,T1) of two disjoint binary distance-4 even-weight codes such that the set of words at distance 1 from T0 coincides with the set of words at distance 1 from T1. Such trade is called primary if any pair of proper subsets of T0 and T1 is not a trade. Using a computer-aided approach, we classify nonequivalent primary extended 1-perfect trades of length 10, constant-weight extended 1-perfect trades of length 12, and Steiner trades derived from them. In particular, all Steiner trades with parameters (5,6,12) are classified.
combinatorics  to-understand  graph-theory  strings  optimization  constraint-satisfaction  looking-to-see  nudge-targets  consider:looking-to-see  consider:classification  consider:feature-discovery
october 2017 by Vaguery
[1006.4176] Unknotting Unknots
A knot is an an embedding of a circle into three-dimensional space. We say that a knot is unknotted if there is an ambient isotopy of the embedding to a standard circle. By representing knots via planar diagrams, we discuss the problem of unknotting a knot diagram when we know that it is unknotted. This problem is surprisingly difficult, since it has been shown that knot diagrams may need to be made more complicated before they may be simplified. We do not yet know, however, how much more complicated they must get. We give an introduction to the work of Dynnikov who discovered the key use of arc--presentations to solve the problem of finding a way to detect the unknot directly from a diagram of the knot. Using Dynnikov's work, we show how to obtain a quadratic upper bound for the number of crossings that must be introduced into a sequence of unknotting moves. We also apply Dynnikov's results to find an upper bound for the number of moves required in an unknotting sequence.
knot-theory  rather-interesting  representation  algorithms  classification  nudge-targets  consider:looking-to-see  consider:feature-discovery
october 2017 by Vaguery
[1605.08396] Robust Downbeat Tracking Using an Ensemble of Convolutional Networks
In this paper, we present a novel state of the art system for automatic downbeat tracking from music signals. The audio signal is first segmented in frames which are synchronized at the tatum level of the music. We then extract different kind of features based on harmony, melody, rhythm and bass content to feed convolutional neural networks that are adapted to take advantage of each feature characteristics. This ensemble of neural networks is combined to obtain one downbeat likelihood per tatum. The downbeat sequence is finally decoded with a flexible and efficient temporal model which takes advantage of the metrical continuity of a song. We then perform an evaluation of our system on a large base of 9 datasets, compare its performance to 4 other published algorithms and obtain a significant increase of 16.8 percent points compared to the second best system, for altogether a moderate cost in test and training. The influence of each step of the method is studied to show its strengths and shortcomings.
neural-networks  music  deep-learning  rather-interesting  to-write-about  nudge-targets  consider:feature-discovery
october 2017 by Vaguery
[cs/0302027] Tiling space and slabs with acute tetrahedra
We show it is possible to tile three-dimensional space using only tetrahedra with acute dihedral angles. We present several constructions to achieve this, including one in which all dihedral angles are less than 77.08∘, and another which tiles a slab in space.
computational-geometry  tiling  rather-interesting  constraint-satisfaction  nudge-targets  consider:feature-discovery  consider:simpler-planar-problem
october 2017 by Vaguery
[1406.5156] Pattern-avoiding permutations and Brownian excursion Part I: Shapes and fluctuations
Permutations that avoid given patterns are among the most classical objects in combinatorics and have strong connections to many fields of mathematics, computer science and biology. In this paper we study the scaling limits of a random permutation avoiding a pattern of length 3 and their relations to Brownian excursion. Exploring this connection to Brownian excursion allows us to strengthen the recent results of Madras and Pehlivan, and Miner and Pak as well as to understand many of the interesting phenomena that had previously gone unexplained.
permutations  combinatorics  review  rather-interesting  feature-extraction  ranimuladom-walks  simulation  nudge-targets  consider:feature-discovery
october 2017 by Vaguery
[1406.0670] Decision Algorithms for Fibonacci-Automatic Words, with Applications to Pattern Avoidance
We implement a decision procedure for answering questions about a class of infinite words that might be called (for lack of a better name) "Fibonacci-automatic". This class includes, for example, the famous Fibonacci word f = 01001010..., the fixed point of the morphism 0 -> 01 and 1 -> 0. We then recover many results about the Fibonacci word from the literature (and improve some of them), such as assertions about the occurrences in f of squares, cubes, palindromes, and so forth. As an application of our method we prove a new result: there exists an aperiodic infinite binary word avoiding the pattern x x x^R. This is the first avoidability result concerning a nonuniform morphism proven purely mechanically.
strings  combinatorics  classification  nudge-targets  consider:looking-to-see  consider:feature-discovery
october 2017 by Vaguery
New Shapes Solve Infinite Pool-Table Problem | Quanta Magazine
Two “rare jewels” have illuminated a mysterious multidimensional object that connects a huge variety of mathematical work.
dynamical-systems  geometry  rather-interesting  mathematical-recreations  nudge-targets  consider:looking-to-see  consider:feature-discovery
october 2017 by Vaguery
[1709.05701] Transkingdom Networks: A Systems Biology Approach to Identify Causal Members of Host-Microbiota Interactions
Improvements in sequencing technologies and reduced experimental costs have resulted in a vast number of studies generating high-throughput data. Although the number of methods to analyze these "omics" data has also increased, computational complexity and lack of documentation hinder researchers from analyzing their high-throughput data to its true potential. In this chapter we detail our data-driven, transkingdom network (TransNet) analysis protocol to integrate and interrogate multi-omics data. This systems biology approach has allowed us to successfully identify important causal relationships between different taxonomic kingdoms (e.g. mammals and microbes) using diverse types of data.
rather-interesting  bioinformatics  community-detection  symbiosis  machine-learning  to-write-about  consider:feature-discovery
october 2017 by Vaguery
[1404.6238] Recurrence and transience for the frog model on trees
The frog model is a growing system of random walks where a particle is added whenever a new site is visited. A longstanding open question is how often the root is visited on the infinite d-ary tree. We prove the model undergoes a phase transition, finding it recurrent for d=2 and transient for d≥5. Simulations suggest strong recurrence for d=2, weak recurrence for d=3, and transience for d≥4. Additionally, we prove a 0-1 law for all d-ary trees, and we exhibit a graph on which a 0-1 law does not hold.
To prove recurrence when d=2, we construct a recursive distributional equation for the number of visits to the root in a smaller process and show the unique solution must be infinity a.s. The proof of transience when d=5 relies on computer calculations for the transition probabilities of a large Markov chain. We also include the proof for d≥6, which uses similar techniques but does not require computer assistance.
probability-theory  graph-theory  random-walks  dynamical-systems  rather-interesting  to-understand  to-write-about  consider:feature-discovery  consider:classification
october 2017 by Vaguery
[1608.08087] Equisectional equivalence of triangles
We study equivalence relation of the set of triangles generated by similarity and operation on a triangle to get a new one by joining division points of three edges with the same ratio. Using the moduli space of similarity classes of triangles introduced by Nakamura and Oguiso, we give characterization of equivalent triangles in terms of circles of Apollonius (or hyperbolic pencil of circles) and properties of special equivalent triangles. We also study rationality problem and constructibility problem.
plane-geometry  compass-and-straightedge  looking-to-see  rather-interesting  algebra  nudge-targets  consider:feature-discovery
october 2017 by Vaguery
Unsupervised Sentiment Neuron
It’s interesting to note that the system also makes large updates after the completion of sentences and phrases. For example, in “And about 99.8 percent of that got lost in the film”, there’s a negative update after “lost” and a larger update at the sentence’s end, even though “in the film” has no sentiment content on its own.
sentiment-analysis  neural-networks  machine-learning  natural-language-processing  rather-interesting  to-write-about  consider:cause-and-effect  consider:feature-discovery
september 2017 by Vaguery
[1606.02220] Non-aligned drawings of planar graphs
A non-aligned drawing of a graph is a drawing where no two vertices are in the same row or column. Auber et al. showed that not all planar graphs have non-aligned drawings that are straight-line, planar, and in the minimal-possible n×n-grid. They also showed that such drawings exist if up to n−3 edges may have a bend. In this paper, we give algorithms for non-aligned planar drawings that improve on the results by Auber et al. In particular, we give such drawings in an n×n-grid with significantly fewer bends, and we study what grid-size can be achieved if we insist on having straight-line drawings
graph-layout  computational-geometry  algorithms  constraint-satisfaction  rather-interesting  to-write-about  multiobjective-optimization  nudge-targets  consider:feature-discovery
september 2017 by Vaguery
[0801.3306] Chip-Firing and Rotor-Routing on Directed Graphs
We give a rigorous and self-contained survey of the abelian sandpile model and rotor-router model on finite directed graphs, highlighting the connections between them. We present several intriguing open problems.
sandpiles  complexology  graph-theory  dynamical-systems  feature-construction  to-write-about  nudge-targets  consider:classification  consider:feature-discovery
september 2017 by Vaguery
[1709.05769] Where to Focus: Deep Attention-based Spatially Recurrent Bilinear Networks for Fine-Grained Visual Recognition
Fine-grained visual recognition typically depends on modeling subtle difference from object parts. However, these parts often exhibit dramatic visual variations such as occlusions, viewpoints, and spatial transformations, making it hard to detect. In this paper, we present a novel attention-based model to automatically, selectively and accurately focus on critical object regions with higher importance against appearance variations. Given an image, two different Convolutional Neural Networks (CNNs) are constructed, where the outputs of two CNNs are correlated through bilinear pooling to simultaneously focus on discriminative regions and extract relevant features. To capture spatial distributions among the local regions with visual attention, soft attention based spatial Long-Short Term Memory units (LSTMs) are incorporated to realize spatially recurrent yet visually selective over local input patterns. All the above intuitions equip our network with the following novel model: two-stream CNN layers, bilinear pooling layer, spatial recurrent layer with location attention are jointly trained via an end-to-end fashion to serve as the part detector and feature extractor, whereby relevant features are localized and extracted attentively. We show the significance of our network against two well-known visual recognition tasks: fine-grained image classification and person re-identification.
image-processing  neural-networks  attention  feature-extraction  deep-learning  architecture  constraint-satisfaction  nudge-targets  consider:feature-discovery  consider:representation
september 2017 by Vaguery
[1703.04159] Any-Angle Pathfinding for Multiple Agents Based on SIPP Algorithm
The problem of finding conflict-free trajectories for multiple agents of identical circular shape, operating in shared 2D workspace, is addressed in the paper and decoupled, e.g., prioritized, approach is used to solve this problem. Agents' workspace is tessellated into the square grid on which any-angle moves are allowed, e.g. each agent can move into an arbitrary direction as long as this move follows the straight line segment whose endpoints are tied to the distinct grid elements. A novel any-angle planner based on Safe Interval Path Planning (SIPP) algorithm is proposed to find trajectories for an agent moving amidst dynamic obstacles (other agents) on a grid. This algorithm is then used as part of a prioritized multi-agent planner AA-SIPP(m). On the theoretical, side we show that AA-SIPP(m) is complete under well-defined conditions. On the experimental side, in simulation tests with up to 200 agents involved, we show that our planner finds much better solutions in terms of cost (up to 20%) compared to the planners relying on cardinal moves only.
collective-intelligence  planning  constraint-satisfaction  algorithms  representation  nudge-targets  consider:feature-discovery
september 2017 by Vaguery
[1212.0649] Optimal packings of congruent circles on a square flat torus
We consider packings of congruent circles on a square flat torus, i.e., periodic (w.r.t. a square lattice) planar circle packings, with the maximal circle radius. This problem is interesting due to a practical reason - the problem of "super resolution of images." We have found optimal arrangements for N=6, 7 and 8 circles. Surprisingly, for the case N=7 there are three different optimal arrangements. Our proof is based on a computer enumeration of toroidal irreducible contact graphs.
packing  computational-geometry  optimization  to-write-about  nudge-targets  consider:looking-to-see  consider:feature-discovery  plane-geometry
september 2017 by Vaguery
[1709.01456] Improved Bounds for Drawing Trees on Fixed Points with L-shaped Edges
Let T be an n-node tree of maximum degree 4, and let P be a set of n points in the plane with no two points on the same horizontal or vertical line. It is an open question whether T always has a planar drawing on P such that each edge is drawn as an orthogonal path with one bend (an "L-shaped" edge). By giving new methods for drawing trees, we improve the bounds on the size of the point set P for which such drawings are possible to: O(n1.55) for maximum degree 4 trees; O(n1.22) for maximum degree 3 (binary) trees; and O(n1.142) for perfect binary trees.
Drawing ordered trees with L-shaped edges is harder---we give an example that cannot be done and a bound of O(nlogn) points for L-shaped drawings of ordered caterpillars, which contrasts with the known linear bound for unordered caterpillars.
graph-layout  computational-geometry  algorithms  rather-interesting  representation  visualization  hard-problems  nudge-targets  constraint-satisfaction  consider:feature-discovery
september 2017 by Vaguery
[1704.06456] A Domain Based Approach to Social Relation Recognition
Social relations are the foundation of human daily life. Developing techniques to analyze such relations from visual data bears great potential to build machines that better understand us and are capable of interacting with us at a social level. Previous investigations have remained partial due to the overwhelming diversity and complexity of the topic and consequently have only focused on a handful of social relations. In this paper, we argue that the domain-based theory from social psychology is a great starting point to systematically approach this problem. The theory provides coverage of all aspects of social relations and equally is concrete and predictive about the visual attributes and behaviors defining the relations included in each domain. We provide the first dataset built on this holistic conceptualization of social life that is composed of a hierarchical label space of social domains and social relations. We also contribute the first models to recognize such domains and relations and find superior performance for attribute based features. Beyond the encouraging performance of the attribute based approach, we also find interpretable features that are in accordance with the predictions from social psychology literature. Beyond our findings, we believe that our contributions more tightly interleave visual recognition and social psychology theory that has the potential to complement the theoretical work in the area with empirical and data-driven models of social life.
image-processing  computer-vision  machine-learning  representation  social-psychology  rather-interesting  to-write-about  consider:feature-discovery
september 2017 by Vaguery
Magnetism – The Inner Frame
Magnetism is played by two players on a strip of squares, who take turns placing + and – tokens onto the strip. The only rule is that no two tokens with the same parity can be placed next to each other.
simple-games  game-theory  to-write-about  consider:looking-to-see  nudge-targets  consider:feature-discovery
september 2017 by Vaguery
[1609.00147] Two-connected spanning subgraphs with at most $frac{10}{7}$OPT edges
We present a 107-approximation algorithm for the minimum two-vertex-connected spanning subgraph problem.
graph-theory  nudge-targets  consider:looking-to-see  consider:feature-discovery
august 2017 by Vaguery
Heesch Numbers, Part 2: Polyforms – Isohedral
In the first post in this series, I introduced the concept of a shape’s Heesch number. In brief, if a shape doesn’t tile the plane, its Heesch number is a measure of the maximum number of times you can surround the shape with layers of copies of itself. (Shapes that do tile are defined to have a Heesch number of infinity.) Shapes with positive, finite Heesch numbers are entertaining mathematical curiosities. Far more mysterious—and infuriating—is the fact that we know of examples of Heesch numbers only up to five, and nothing higher. Learning more about shapes with high Heesch numbers could offer insights into deep unsolved problems in tiling theory.
tiling  combinatorics  mathematical-recreations  rather-interesting  number-theory  looking-to-see  nudge-targets  consider:feature-discovery  to-write-about
august 2017 by Vaguery
[1705.00759] Controllability of Conjunctive Boolean Networks with Application to Gene Regulation
A Boolean network is a finite state discrete time dynamical system. At each step, each variable takes a value from a binary set. The value update rule for each variable is a local function which depends only on a selected subset of variables. Boolean networks have been used in modeling gene regulatory networks. We focus in this paper on a special class of Boolean networks, namely the conjunctive Boolean networks (CBNs), whose value update rule is comprised of only logic AND operations. It is known that any trajectory of a Boolean network will enter a periodic orbit. Periodic orbits of a CBN have been completely understood. In this paper, we investigate the orbit-controllability and state-controllability of a CBN: We ask the question of how one can steer a CBN to enter any periodic orbit or to reach any final state, from any initial state. We establish necessary and sufficient conditions for a CBN to be orbit-controllable and state-controllable. Furthermore, explicit control laws are presented along the analysis.
boolean-networks  Kauffmania  engineering-design  emergent-design  rather-interesting  to-write-about  nudge-targets  consider:feature-discovery  dynamical-systems  complexology
august 2017 by Vaguery
Dynamics Robustness of Cascading Systems | bioRxiv
A most important property of biochemical systems is robustness. Static robustness, e.g., homeostasis, is the insensitivity of a state against perturbations, whereas dynamics robustness, e.g., homeorhesis, is the insensitivity of a dynamic process. In contrast to the extensively studied static robustness, dynamics robustness, i.e., how a system creates an invariant temporal profile against perturbations, is little explored despite transient dynamics being crucial for cellular fates and are reported to be robust experimentally. For example, the duration of a stimulus elicits different phenotypic responses, and signaling networks process and encode temporal information. Hence, robustness in time courses will be necessary for functional biochemical networks. Based on dynamical systems theory, we uncovered a general mechanism to achieve dynamics robustness. Using a three-stage linear signaling cascade as an example, we found that the temporal profiles and response duration post-stimulus is robust to perturbations against certain parameters. Then analyzing the linearized model, we elucidated the criteria of how such dynamics robustness emerges in signaling networks. We found that changes in the upstream modules are masked in the cascade, and that the response duration is mainly controlled by the rate-limiting module and organization of the cascade's kinetics. Specifically, we found two necessary conditions for dynamics robustness in signaling cascades: 1) Constraint on the rate-limiting process: The phosphatase activity in the perturbed module is not the slowest. 2) Constraints on the initial conditions: The kinase activity needs to be fast enough such that each module is saturated even with fast phosphatase activity and upstream information is attenuated. We discussed the relevance of such robustness to several biological examples and the validity of the above conditions therein. Given the applicability of dynamics robustness to a variety of systems, it will provide a general basis for how biological systems function dynamically.
robustness  systems-biology  self-organization  complexology  nonlinear-dynamics  emergent-design  to-write-about  nudge-targets  consider:feature-discovery
june 2017 by Vaguery
[math/0608131] Many sets have more sums than differences
Since addition is commutative but subtraction is not, the sumset S+S of a finite set S is predisposed to be smaller than the difference set S-S. In this paper, however, we show that each of the three possibilities (|S+S|>|S-S|, |S+S|=|S-S|, |S+S|<|S-S|) occur for a positive proportion of the subsets of {0, 1, ..., n-1}. We also show that the difference |S+S| - |S-S| can take any integer value, and we show that the expected number of omitted differences is asymptotically 6 while the expected number of missing sums is asymptotically 10. Other data and conjectures on the distribution of these quantities are also given.
number-theory  rather-interesting  to-write-about  experiment  nudge-targets  consider:feature-discovery
june 2017 by Vaguery
[math/0608148] Sets with more sums than differences
Let A be a finite subset of the integers or, more generally, of any abelian group, written additively. The set A has "more sums than differences" if |A+A|>|A-A|. A set with this property is called an MSTD set. This paper gives explicit constructions of families of MSTD sets of integers.
number-theory  enumeration  combinatorics  rather-interesting  to-write-about  nudge-targets  consider:feature-discovery
june 2017 by Vaguery
[1108.4500] Generalized More Sums Than Differences Sets
A More Sums Than Differences (MSTD, or sum-dominant) set is a finite set A⊂ℤ such that |A+A|<|A−A|. Though it was believed that the percentage of subsets of {0,...,n} that are sum-dominant tends to zero, in 2006 Martin and O'Bryant \cite{MO} proved a positive percentage are sum-dominant. We generalize their result to the many different ways of taking sums and differences of a set. We prove that |ϵ1A+...+ϵkA|>|δ1A+...+δkA| a positive percent of the time for all nontrivial choices of ϵj,δj∈{−1,1}. Previous approaches proved the existence of infinitely many such sets given the existence of one; however, no method existed to construct such a set. We develop a new, explicit construction for one such set, and then extend to a positive percentage of sets.
We extend these results further, finding sets that exhibit different behavior as more sums/differences are taken. For example, notation as above we prove that for any m, |ϵ1A+...+ϵkA|−|δ1A+...+δkA|=m a positive percentage of the time. We find the limiting behavior of kA=A+...+A for an arbitrary set A as k→∞ and an upper bound of k for such behavior to settle down. Finally, we say A is k-generational sum-dominant if A, A+A, ...,kA are all sum-dominant. Numerical searches were unable to find even a 2-generational set (heuristics indicate the probability is at most 10−9, and almost surely significantly less). We prove the surprising result that for any k a positive percentage of sets are k-generational, and no set can be k-generational for all k.
number-theory  rather-interesting  to-write-about  enumeration  nudge-targets  consider:feature-discovery
june 2017 by Vaguery
[1705.00241] Dynamic interdependence and competition in multilayer networks
From critical infrastructure, to physiology and the human brain, complex systems rarely occur in isolation. Instead, the functioning of nodes in one system often promotes or suppresses the functioning of nodes in another. Despite advances in structural interdependence, modeling interdependence and other interactions between dynamic systems has proven elusive. Here we define a broadly applicable dynamic dependency link and develop a general framework for interdependent and competitive interactions between general dynamic systems. We apply our framework to studying interdependent and competitive synchronization in multi-layer oscillator networks and cooperative/competitive contagions in an epidemic model. Using a mean-field theory which we verify numerically, we find explosive transitions and rich behavior which is absent in percolation models including hysteresis, multi-stability and chaos. The framework presented here provides a powerful new way to model and understand many of the interacting complex systems which surround us.
dynamical-systems  coupled-oscillators  network-theory  rather-interesting  to-write-about  simulation  consider:simple-examples  nudge-targets  consider:control-theory  consider:feature-discovery
may 2017 by Vaguery
[1611.05321] Bootstrap, Review, Decode: Using Out-of-Domain Textual Data to Improve Image Captioning
We propose a novel way of using out-of-domain textual data to enhance the performance of existing image captioning systems. We evaluate this learning approach on a newly designed model that uses - and improves upon - building blocks from state-of-the-art methods. This model starts from detecting visual concepts present in an image which are then fed to a reviewer-decoder architecture with an attention mechanism. Unlike previous approaches that encode visual concepts using word embeddings, we instead suggest using regional image features which capture more intrinsic information. The main benefit of this architecture is that it synthesizes meaningful thought vectors that capture salient image properties and then applies a soft attentive decoder to decode the thought vectors and generate image captions. We evaluate our model on both Microsoft COCO and Flickr30K datasets and demonstrate that this model combined with our bootstrap learning method can largely improve performance and help the model to generate more accurate and diverse captions.
data-fusion  image-processing  deep-learning  rather-interesting  to-write-about  nudge-targets  consider:feature-discovery
may 2017 by Vaguery
[1607.01196] Drawing Graphs on Few Lines and Few Planes
We investigate the problem of drawing graphs in 2D and 3D such that their edges (or only their vertices) can be covered by few lines or planes. We insist on straight-line edges and crossing-free drawings. This problem has many connections to other challenging graph-drawing problems such as small-area or small-volume drawings, layered or track drawings, and drawing graphs with low visual complexity. While some facts about our problem are implicit in previous work, this is the first treatment of the problem in its full generality. Our contribution is as follows.
We show lower and upper bounds for the numbers of lines and planes needed for covering drawings of graphs in certain graph classes. In some cases our bounds are asymptotically tight; in some cases we are able to determine exact values.
We relate our parameters to standard combinatorial characteristics of graphs (such as the chromatic number, treewidth, maximum degree, or arboricity) and to parameters that have been studied in graph drawing (such as the track number or the number of segments appearing in a drawing).
We pay special attention to planar graphs. For example, we show that there are planar graphs that can be drawn in 3-space on a lot fewer lines than in the plane.
graph-layout  computational-geometry  optimization  graph-theory  topology  rather-interesting  to-write-about  consider:feature-discovery  nudge-targets  consider:classification
may 2017 by Vaguery
[1404.7493] Drawdown: From Practice to Theory and Back Again
Maximum drawdown, the largest cumulative loss from peak to trough, is one of the most widely used indicators of risk in the fund management industry, but one of the least developed in the context of measures of risk. We formalize drawdown risk as Conditional Expected Drawdown (CED), which is the tail mean of maximum drawdown distributions. We show that CED is a degree one positive homogenous risk measure, so that it can be linearly attributed to factors; and convex, so that it can be used in quantitative optimization. We empirically explore the differences in risk attributions based on CED, Expected Shortfall (ES) and volatility. An important feature of CED is its sensitivity to serial correlation. In an empirical study that fits AR(1) models to US Equity and US Bonds, we find substantially higher correlation between the autoregressive parameter and CED than with ES or with volatility.
portfolio-theory  performance-measure  financial-engineering  multiobjective-optimization  consider:feature-discovery  to-write-about  algorithms  representation
may 2017 by Vaguery
[1311.6511] Intransitive Dice
We consider n-sided dice whose face values lie between 1 and n and whose faces sum to n(n+1)/2. For two dice A and B, define A≻B if it is more likely for A to show a higher face than B. Suppose k such dice A1,…,Ak are randomly selected. We conjecture that the probability of ties goes to 0 as n grows. We conjecture and provide some supporting evidence that---contrary to intuition---each of the 2(k2) assignments of ≻ or ≺ to each pair is equally likely asymptotically. For a specific example, suppose we randomly select k dice A1,…,Ak and observe that A1≻A2≻…≻Ak. Then our conjecture asserts that the outcomes Ak≻A1 and A1≺Ak both have probability approaching 1/2 as n→∞.
combinatorics  mathematical-recreations  probability-theory  to-write-about  nudge-targets  consider:engineering-design  consider:feature-discovery
may 2017 by Vaguery
[1505.07363] An Enumeration of the Equivalence Classes of Self-Dual Matrix Codes
As a result of their applications in network coding, space-time coding, and coding for criss-cross errors, matrix codes have garnered significant attention; in various contexts, these codes have also been termed rank-metric codes, space-time codes over finite fields, and array codes. We focus on characterizing matrix codes that are both efficient (have high rate) and effective at error correction (have high minimum rank-distance). It is well known that the inherent trade-off between dimension and minimum distance for a matrix code is reversed for its dual code; specifically, if a matrix code has high dimension and low minimum distance, then its dual code will have low dimension and high minimum distance. With an aim towards finding codes with a perfectly balanced trade-off, we study self-dual matrix codes. In this work, we develop a framework based on double cosets of the matrix-equivalence maps to provide a complete classification of the equivalence classes of self-dual matrix codes, and we employ this method to enumerate the equivalence classes of these codes for small parameters.
information-theory  matrices  combinatorics  rather-interesting  to-write-about  nudge-targets  consider:feature-discovery  consider:rediscovery
may 2017 by Vaguery
[1704.08798] Word Affect Intensities
Words often convey affect -- emotions, feelings, and attitudes. Lexicons of word-affect association have applications in automatic emotion analysis and natural language generation. However, existing lexicons indicate only coarse categories of affect association. Here, for the first time, we create an affect intensity lexicon with real-valued scores of association. We use a technique called best-worst scaling that improves annotation consistency and obtains reliable fine-grained scores. The lexicon includes terms common from both general English and terms specific to social media communications. It has close to 6,000 entries for four basic emotions. We will be adding entries for other affect dimensions shortly.
natural-language-processing  looking-to-see  affect  rather-interesting  to-write-about  consider:feature-discovery
may 2017 by Vaguery
[1703.01143] Why is it hard to beat $O(n^2)$ for Longest Common Weakly Increasing Subsequence?
The Longest Common Weakly Increasing Subsequence problem (LCWIS) is a variant of the classic Longest Common Subsequence problem (LCS). Both problems can be solved with simple quadratic time algorithms. A recent line of research led to a number of matching conditional lower bounds for LCS and other related problems. However, the status of LCWIS remained open.
In this paper we show that LCWIS cannot be solved in strongly subquadratic time unless the Strong Exponential Time Hypothesis (SETH) is false.
The ideas which we developed can also be used to obtain a lower bound based on a safer assumption of NC-SETH, i.e. a version of SETH which talks about NC circuits instead of less expressive CNF formulas.
computational-complexity  robustness  algorithms  looking-to-see  rather-interesting  to-write-about  extreme-values  outliers  hard-problems  feature-construction  nudge-targets  consider:feature-discovery
may 2017 by Vaguery
[1610.01861] Efficient Best-Response Computation for Strategic Network Formation under Attack
Strategic network formation models the uncoordinated creation of a network by selfish agents. Inspired by real world examples, e.g. the Internet, researchers have introduced an abundance of strategic games to study natural phenomena in networks. Most of these games have the conceptual drawback of being computationally intractable. For example, computing a best response strategy or checking whether an equilibrium is reached is NP-hard. Thus, a main challenge in the field is to find models which incorporate many interesting features and to devise efficient algorithms for solving the entailed computational tasks.
We address this challenge by providing an efficient algorithm to compute a best response strategy for a recently introduced model, thereby answering the open question posed by Goyal et al. [WINE'16]. Their promising model focuses on network robustness by considering an adversary who attacks (and kills) nodes in the network and lets this attack spread virus-like to neighboring nodes.
Additionally, we augment their model by introducing a less predictable adversary and show that our algorithm, with minor modifications, can cope with this more complex scenario.
community-formation  network-theory  self-organization  rather-interesting  to-write-about  consider:feature-discovery
april 2017 by Vaguery
[1704.07510] Knotting probability and the scaling behavior of self-avoiding polygons under a topological constraint
We define the knotting probability of a knot K by the probability for a random polygon (RP) or self-avoiding polygon (SAP) with N segments having the knot type K. As a model of circular DNA we introduce the SAP consisting of impenetrable cylindrical segments of unit length in which the radius rex of segments corresponds to the screening length of DNA surrounded by counter ions. For various prime and composite knots we numerically show that a compact formula gives good fitted curves to the data of the knotting probabilities for the cylindrical SAP as a function of segment number N and cylindrical radius rex. It connects the small-N to the large-N regions and even to lattice knots for large values of radius rex such as satisfying 2rex=1/4. We suggest that if radius rex is large, the trefoil knot and its composite knots are dominant among the nontrivial knots in SAPs. We then study topological swelling that the mean-square radius of gyration of the cylindrical SAP with fixed knot is much larger than that of under no topological constraint if radius rex is small and N is large enough. We argue that the finite-size effect is significant in it where the characteristic length of the knotting probability gives the topological scale. We show that for any value of radius rex a three-parameter formula gives a good fitted curve to the plot of the mean-square gyration radius of the cylindrical SAP with a given knot K against segment number N. With the curves we evaluate the effective scaling exponent. We suggest that it increases with respect to the upper limit of N and gradually approaches the scaling exponent of self-avoiding walks even in the case of zero thickness as the upper limit of N becomes infinitely large.
knot-theory  inference  rather-interesting  prediction  probability-theory  nudge-targets  consider:looking-to-see  consider:rediscovery  consider:feature-discovery
april 2017 by Vaguery
[1606.07104] Manifolds' Projective Approximation Using The Moving Least-Squares (MMLS)
In order to avoid the curse of dimensionality, frequently encountered in Big Data analysis, there was a vast development in the field of linear and non-linear dimension reduction techniques in recent years. These techniques (sometimes referred to as manifold learning) assume that the scattered input data is lying on a lower dimensional manifold, thus the high dimensionality problem can be overcome by learning the lower dimensionality behavior. However, in real life applications, data is often very noisy. In this work, we propose a method to approximate a d-dimensional Cm+1 smooth submanifold  residing in ℝn (d<<n) based upon scattered data points (i.e., a data cloud). We assume that the data points are located "near" the noisy lower dimensional manifold and perform a non-linear moving least-squares projection on an approximating manifold. Under some mild assumptions, the resulting approximant is shown to be infinitely smooth and of high approximation order (i.e., O(hm+1), where h is the fill distance and m is the degree of the local polynomial approximation). Furthermore, the method presented here assumes no analytic knowledge of the approximated manifold and the approximation algorithm is linear in the large dimension n.
models  machine-learning  curse-of-dimensionality  compressed-sensing  feature-extraction  nudge-targets  consider:looking-to-see  consider:feature-discovery
april 2017 by Vaguery
[1308.0419] Inverse Procedural Modeling of Facade Layouts
In this paper, we address the following research problem: How can we generate a meaningful split grammar that explains a given facade layout? To evaluate if a grammar is meaningful, we propose a cost function based on the description length and minimize this cost using an approximate dynamic programming framework. Our evaluation indicates that our framework extracts meaningful split grammars that are competitive with those of expert users, while some users and all competing automatic solutions are less successful.
grammar  L-systems  generative-models  image-processing  learning-from-data  machine-learning  inverse-problems  nudge-targets  consider:representation  consider:feature-discovery
april 2017 by Vaguery
[1110.5348] Packing Squares in a Torus
The densest packings of N unit squares in a torus are studied using analytical methods as well as simulated annealing. A rich array of dense packing solutions are found: density-one packings when N is the sum of two square integers; a family of "gapped bricklayer" Bravais lattice solutions with density N/(N+1); and some surprising non-Bravais lattice configurations, including lattices of holes as well as a configuration for N=23 in which not all squares share the same orientation. The entropy of some of these configurations and the frequency and orientation of density-one solutions as N goes to infinity are discussed.
packing  topology  optimization  rather-interesting  simulation  nudge-targets  consider:feature-discovery  consider:looking-to-see
april 2017 by Vaguery
[1312.1793] "Nice" Rational Functions
We consider simple rational functions Rmn(x)=Pm(x)/Qn(x), with Pm and Qn polynomials of degree m and n respectively. We look for "nice" functions, which we define to be ones where as many as possible of the roots, poles, critical points and (possibly) points of inflexion are integer or, at worst, rational.
algebra  number-theory  rather-interesting  constraint-satisfaction  stamp-collecting  nudge-targets  consider:looking-to-see  consider:feature-discovery
april 2017 by Vaguery
[1612.06701] A family of multimagic squares based on large sets of orthogonal arrays
Large set of orthogonal arrays (LOA) were introduced by D. R. Stinson, and it is also used to construct multimagic squares recently. In this paper, multimagic squares based on strong double LOA are further investigated. It is proved that there exists an MS(q2t−1,t) for any prime power q≥2t−1 with t≥3, which provided a new family of multimagic squares.
combinatorics  magic-squares  constraint-satisfaction  mathematical-recreations  number-theory  rather-interesting  nudge-targets  consider:generalizations  consider:looking-to-see  consider:feature-discovery
april 2017 by Vaguery
[1505.02547] The $plambda n$ fractal decomposition: Nontrivial partitions of conserved physical quantities
A mathematical method for constructing fractal curves and surfaces, termed the pλn fractal decomposition, is presented. It allows any function to be split into a finite set of fractal discontinuous functions whose sum is equal everywhere to the original function. Thus, the method is specially suited for constructing families of fractal objects arising from a conserved physical quantity, the decomposition yielding an exact partition of the quantity in question. Most prominent classes of examples are provided by Hamiltonians and partition functions of statistical ensembles: By using this method, any such function can be decomposed in the ordinary sum of a specified number of terms (generally fractal functions), the decomposition being both exact and valid everywhere on the domain of the function.
representation  composition  rather-interesting  to-write-about  nudge-targets  consider:looking-to-see  consider:feature-discovery
april 2017 by Vaguery
[1212.6102] On Curling Numbers of Integer Sequences
Given a finite nonempty sequence S of integers, write it as XY^k, where Y^k is a power of greatest exponent that is a suffix of S: this k is the curling number of S. The Curling Number Conjecture is that if one starts with any initial sequence S, and extends it by repeatedly appending the curling number of the current sequence, the sequence will eventually reach 1. The conjecture remains open. In this paper we discuss the special case when S consists just of 2's and 3's. Even this case remains open, but we determine how far a sequence of n 2's and 3's can extend before reaching a 1, conjecturally for n <= 80. We investigate several related combinatorial problems, such as finding c(n,k), the number of binary sequences of length n and curling number k, and t(n,i), the number of sequences of length n which extend for i steps before reaching a 1. A number of interesting combinatorial problems remain unsolved.
combinatorics  rather-interesting  sequences  open-questions  nudge-targets  consider:looking-to-see  consider:feature-discovery  consider:rediscovery  to-write-about
april 2017 by Vaguery
per page:    204080120160

Copy this bookmark:

description:

tags: