**Vaguery + consider:feature-discovery**
272

[1808.06013] Realization and Connectivity of the Graphs of Origami Flat Foldings

13 days ago by Vaguery

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

6 weeks ago by Vaguery

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

7 weeks ago by Vaguery

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

Heesch Numbers — Numberphile

7 weeks ago by Vaguery

Another lovely enumeration problem that wants exploring.

enumeration
tiling
combinatorics
rather-interesting
to-write-about
consider:representation
consider:feature-discovery
to-simulate
7 weeks ago by Vaguery

[1512.01289] Predicting and visualizing psychological attributions with a deep neural network

7 weeks ago by Vaguery

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

7 weeks ago by Vaguery

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

8 weeks ago by Vaguery

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

8 weeks ago by Vaguery

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

8 weeks ago by Vaguery

[1811.09723] No triangle can be cut into seven congruent triangles

8 weeks ago by Vaguery

We give a short and direct proof of the theorem in the title, and prove the theorem for 11 as well as 7.

tiling
constraint-satisfaction
proof
combinatorics
plane-geometry
to-write-about
to-do
consider:genetic-programming
consider:feature-discovery
consider:rediscovery
talk-about:dominoes
8 weeks ago by Vaguery

[1812.07014] Tiling an Equilateral Triangle

8 weeks ago by Vaguery

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

december 2018 by Vaguery

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

december 2018 by Vaguery

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

december 2018 by Vaguery

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

december 2018 by Vaguery

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

december 2018 by Vaguery

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 [3] and [4] (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

december 2018 by Vaguery

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

november 2018 by Vaguery

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

october 2018 by Vaguery

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

october 2018 by Vaguery

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

october 2018 by Vaguery

[1801.08003] Threadable Curves

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

september 2018 by Vaguery

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

august 2018 by Vaguery

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

june 2018 by Vaguery

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

april 2018 by Vaguery

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

.

number-theory
mathematical-recreations
open-questions
to-write-about
consider:feature-discovery
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

march 2018 by Vaguery

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

march 2018 by Vaguery

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

march 2018 by Vaguery

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

march 2018 by Vaguery

[1710.02271] Unsupervised Extraction of Representative Concepts from Scientific Literature

february 2018 by Vaguery

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

february 2018 by Vaguery

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

february 2018 by Vaguery

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

january 2018 by Vaguery

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

november 2017 by Vaguery

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

november 2017 by Vaguery

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

november 2017 by Vaguery

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

november 2017 by Vaguery

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

november 2017 by Vaguery

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

october 2017 by Vaguery

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

october 2017 by Vaguery

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

october 2017 by Vaguery

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

october 2017 by Vaguery

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

october 2017 by Vaguery

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

october 2017 by Vaguery

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

october 2017 by Vaguery

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

october 2017 by Vaguery

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

october 2017 by Vaguery

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

october 2017 by Vaguery

The frog model is a growing system of random walks where a particle is added whenever a new site is visited. A longstanding open question is how often the root is visited on the infinite d-ary tree. We prove the model undergoes a phase transition, finding it recurrent for d=2 and transient for d≥5. Simulations suggest strong recurrence for d=2, weak recurrence for d=3, and transience for d≥4. Additionally, we prove a 0-1 law for all d-ary trees, and we exhibit a graph on which a 0-1 law does not hold.

To prove recurrence when d=2, we construct a recursive distributional equation for the number of visits to the root in a smaller process and show the unique solution must be infinity a.s. The proof of transience when d=5 relies on computer calculations for the transition probabilities of a large Markov chain. We also include the proof for d≥6, which uses similar techniques but does not require computer assistance.

probability-theory
graph-theory
random-walks
dynamical-systems
rather-interesting
to-understand
to-write-about
consider:feature-discovery
consider:classification
To prove recurrence when d=2, we construct a recursive distributional equation for the number of visits to the root in a smaller process and show the unique solution must be infinity a.s. The proof of transience when d=5 relies on computer calculations for the transition probabilities of a large Markov chain. We also include the proof for d≥6, which uses similar techniques but does not require computer assistance.

october 2017 by Vaguery

[1608.08087] Equisectional equivalence of triangles

october 2017 by Vaguery

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

september 2017 by Vaguery

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

september 2017 by Vaguery

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

september 2017 by Vaguery

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

september 2017 by Vaguery

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

september 2017 by Vaguery

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

september 2017 by Vaguery

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

september 2017 by Vaguery

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

september 2017 by Vaguery

[1704.06456] A Domain Based Approach to Social Relation Recognition

september 2017 by Vaguery

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

september 2017 by Vaguery

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

august 2017 by Vaguery

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

august 2017 by Vaguery

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

august 2017 by Vaguery

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

june 2017 by Vaguery

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

june 2017 by Vaguery

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

june 2017 by Vaguery

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

june 2017 by Vaguery

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

june 2017 by Vaguery

[1705.00241] Dynamic interdependence and competition in multilayer networks

may 2017 by Vaguery

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

may 2017 by Vaguery

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

may 2017 by Vaguery

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

may 2017 by Vaguery

[1404.7493] Drawdown: From Practice to Theory and Back Again

may 2017 by Vaguery

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

may 2017 by Vaguery

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

may 2017 by Vaguery

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

may 2017 by Vaguery

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?

may 2017 by Vaguery

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

may 2017 by Vaguery

[1610.01861] Efficient Best-Response Computation for Strategic Network Formation under Attack

april 2017 by Vaguery

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

april 2017 by Vaguery

[1704.07510] Knotting probability and the scaling behavior of self-avoiding polygons under a topological constraint

april 2017 by Vaguery

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)

april 2017 by Vaguery

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

april 2017 by Vaguery

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

april 2017 by Vaguery

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

april 2017 by Vaguery

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

april 2017 by Vaguery

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

april 2017 by Vaguery

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

april 2017 by Vaguery

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

**related tags**

Copy this bookmark: