**Vaguery : feature-construction**
271

[1807.06414] Combining a Context Aware Neural Network with a Denoising Autoencoder for Measuring String Similarities

9 days ago by Vaguery

Measuring similarities between strings is central for many established and fast growing research areas including information retrieval, biology, and natural language processing. The traditional approach for string similarity measurements is to define a metric over a word space that quantifies and sums up the differences between characters in two strings. The state-of-the-art in the area has, surprisingly, not evolved much during the last few decades. The majority of the metrics are based on a simple comparison between character and character distributions without consideration for the context of the words. This paper proposes a string metric that encompasses similarities between strings based on (1) the character similarities between the words including. Non-Standard and standard spellings of the same words, and (2) the context of the words. Our proposal is a neural network composed of a denoising autoencoder and what we call a context encoder specifically designed to find similarities between the words based on their context. The experimental results show that the resulting metrics succeeds in 85.4\% of the cases in finding the correct version of a non-standard spelling among the closest words, compared to 63.2\% with the established Normalised-Levenshtein distance. Besides, we show that words used in similar context are with our approach calculated to be similar than words with different contexts, which is a desirable property missing in established string metrics.

feature-construction
machine-learning
clustering
natural-language-processing
rather-interesting
to-simulate
to-write-about
consider:feature-discovery
9 days ago by Vaguery

High-dimensional Time Series Clustering via Cross-Predictability

9 days ago by Vaguery

The key to time series clustering is how to characterize the similarity between any two time series. In this paper, we explore a new similarity metric called “cross-predictability”: the degree to which a future value in each time series is predicted by past values of the others. However, it is challenging to estimate such cross-predictability among time series in the high-dimensional regime, where the number of time series is much larger than the length of each time series. We address this challenge with a sparsity assumption: only time series in the same cluster have significant cross-predictability with each other. We demonstrate that this approach is computationally attractive, and provide a theoretical proof that the proposed algorithm will identify the correct clustering structure with high probability under certain conditions. To the best of our knowledge, this is the first practical high-dimensional time series clustering algorithm with a provable guarantee. We evaluate with experiments on both synthetic data and real-world data, and results indicate that our method can achieve more than 80% clustering accuracy on real-world data, which is 20% higher than the state-of-art baselines.

performance-networks
clustering
time-series
yeah-I-probably-shoulda-published-in-1999
machine-learning
feature-construction
ah-well
9 days ago by Vaguery

Running Cargo - Futility Closet

13 days ago by Vaguery

This passage is from Rudyard Kipling’s 1910 story “Brother Square-Toes.” What’s notable about the bolded section?

feature-construction
rather-interesting
digital-humanities
to-write-about
consider:looking-to-see
13 days ago by Vaguery

[1804.07150] Improved Bounds for Guarding Plane Graphs with Edges

20 days ago by Vaguery

An "edge guard set" of a plane graph G is a subset Γ of edges of G such that each face of G is incident to an endpoint of an edge in Γ. Such a set is said to guard G. We improve the known upper bounds on the number of edges required to guard any n-vertex embedded planar graph G:

1- We present a simple inductive proof for a theorem of Everett and Rivera-Campo (1997) that G can be guarded with at most 2n5 edges, then extend this approach with a deeper analysis to yield an improved bound of 3n8 edges for any plane graph.

2- We prove that there exists an edge guard set of G with at most n3+α9 edges, where α is the number of quadrilateral faces in G. This improves the previous bound of n3+α by Bose, Kirkpatrick, and Li (2003). Moreover, if there is no short path between any two quadrilateral faces in G, we show that n3 edges suffice, removing the dependence on α.

graph-theory
computational-complexity
computational-geometry
algorithms
feature-construction
rather-interesting
to-understand
to-simulate
1- We present a simple inductive proof for a theorem of Everett and Rivera-Campo (1997) that G can be guarded with at most 2n5 edges, then extend this approach with a deeper analysis to yield an improved bound of 3n8 edges for any plane graph.

2- We prove that there exists an edge guard set of G with at most n3+α9 edges, where α is the number of quadrilateral faces in G. This improves the previous bound of n3+α by Bose, Kirkpatrick, and Li (2003). Moreover, if there is no short path between any two quadrilateral faces in G, we show that n3 edges suffice, removing the dependence on α.

20 days ago by Vaguery

[1812.05125] On Graphs whose Eternal Vertex Cover Number and Vertex Cover Number Coincide

25 days ago by Vaguery

The eternal vertex cover problem is a variant of the classical vertex cover problem where a set of guards on the vertices have to be dynamically reconfigured from one vertex cover to another in every round of an attacker-defender game. The minimum number of guards required to protect a graph G from an infinite sequence of attacks is the eternal vertex cover number of G, denoted by evc(G). It is known that, given a graph G and an integer k, checking whether evc(G)≤k is NP-hard. However, it is unknown whether this problem is in NP or not. Precise value of eternal vertex cover number is known only for certain very basic graph classes like trees, cycles and grids.

For any graph G, it is known that mvc(G)≤evc(G)≤2mvc(G), where mvc(G) is the minimum vertex cover number of G. Though a characterization is known for graphs for which evc(G)=2mvc(G), a characterization of graphs for which evc(G)=mvc(G) remained open. Here, we achieve such a characterization for a class of graphs that includes chordal graphs and internally triangulated planar graphs. For some graph classes including biconnected chordal graphs, our characterization leads to a polynomial time algorithm to precisely determine evc(G) and to determine a safe strategy of guard movement in each round of the game with evc(G) guards.

The characterization also leads to NP-completeness results for the eternal vertex cover problem for some graph classes including biconnected internally triangulated planar graphs. To the best of our knowledge, these are the first NP-completeness results known for the problem for any graph class.

graph-theory
feature-construction
game-theory
rather-interesting
combinatorics
to-simulate
to-write-about
consider:rediscovery
consider:robustness
For any graph G, it is known that mvc(G)≤evc(G)≤2mvc(G), where mvc(G) is the minimum vertex cover number of G. Though a characterization is known for graphs for which evc(G)=2mvc(G), a characterization of graphs for which evc(G)=mvc(G) remained open. Here, we achieve such a characterization for a class of graphs that includes chordal graphs and internally triangulated planar graphs. For some graph classes including biconnected chordal graphs, our characterization leads to a polynomial time algorithm to precisely determine evc(G) and to determine a safe strategy of guard movement in each round of the game with evc(G) guards.

The characterization also leads to NP-completeness results for the eternal vertex cover problem for some graph classes including biconnected internally triangulated planar graphs. To the best of our knowledge, these are the first NP-completeness results known for the problem for any graph class.

25 days ago by Vaguery

[1907.01617] A Short Proof of the Toughness of Delaunay Triangulations

25 days ago by Vaguery

We present a self-contained short proof of the seminal result of Dillencourt (SoCG 1987 and DCG 1990) that Delaunay triangulations, of planar point sets in general position, are 1-tough. An important implication of this result is that Delaunay triangulations have perfect matchings. Another implication of our result is a proof of the conjecture of Aichholzer et al. (2010) that at least n points are required to block any n-vertex Delaunay triangulation

computational-geometry
computational-complexity
rather-interesting
algorithms
hard-problems
feature-construction
to-simulate
to-write-about
consider:hardness-features
25 days ago by Vaguery

[1803.09639] On the multipacking number of grid graphs

4 weeks ago by Vaguery

In 2001, Erwin introduced broadcast domination in graphs. It is a variant of classical domination where selected vertices may have different domination powers. The minimum cost of a dominating broadcast in a graph G is denoted γb(G). The dual of this problem is called multipacking: a multipacking is a set M of vertices such that for any vertex v and any positive integer r, the ball of radius r around v contains at most r vertices of M . The maximum size of a multipacking in a graph G is denoted mp(G). Naturally mp(G) ≤γb(G). Earlier results by Farber and by Lubiw show that broadcast and multipacking numbers are equal for strongly chordal graphs. In this paper, we show that all large grids (height at least 4 and width at least 7), which are far from being chordal, have their broadcast and multipacking numbers equal.

graph-theory
feature-construction
rather-interesting
dynamical-systems
to-simulate
to-write-about
consider:generalizations
consider:prediction
4 weeks ago by Vaguery

[1702.08066] On the Classification and Algorithmic Analysis of Carmichael Numbers

4 weeks ago by Vaguery

In this paper, we study the properties of Carmichael numbers, false positives to several primality tests. We provide a classification for Carmichael numbers with a proportion of Fermat witnesses of less than 50%, based on if the smallest prime factor is greater than a determined lower bound. In addition, we conduct a Monte Carlo simulation as part of a probabilistic algorithm to detect if a given composite number is Carmichael. We modify this highly accurate algorithm with a deterministic primality test to create a novel, more efficient algorithm that differentiates between Carmichael numbers and prime numbers.

number-theory
primes
rather-interesting
feature-construction
classification
tricky-cases
edge-cases
algorithms
performance-measure
to-simulate
to-write-about
consider:classification
computational-complexity
4 weeks ago by Vaguery

[1701.00706] Bounds on parameters of minimally non-linear patterns

5 weeks ago by Vaguery

Let ex(n,P) be the maximum possible number of ones in any 0-1 matrix of dimensions n×n that avoids P. Matrix P is called minimally non-linear if ex(n,P)=ω(n) but ex(n,P′)=O(n) for every strict subpattern P′ of P. We prove that the ratio between the length and width of any minimally non-linear 0-1 matrix is at most 4, and that a minimally non-linear 0-1 matrix with k rows has at most 5k−3 ones. We also obtain an upper bound on the number of minimally non-linear 0-1 matrices with k rows.

In addition, we prove corresponding bounds for minimally non-linear ordered graphs. The minimal non-linearity that we investigate for ordered graphs is for the extremal function ex<(n,G), which is the maximum possible number of edges in any ordered graph on n vertices with no ordered subgraph isomorphic to G.

matrices
pattern-avoiding
pattern-matching
combinatorics
rather-interesting
constraint-satisfaction
looking-to-see
enumeration
feature-construction
to-simulate
to-write-about
In addition, we prove corresponding bounds for minimally non-linear ordered graphs. The minimal non-linearity that we investigate for ordered graphs is for the extremal function ex<(n,G), which is the maximum possible number of edges in any ordered graph on n vertices with no ordered subgraph isomorphic to G.

5 weeks ago by Vaguery

[1612.04861] Some Counterexamples for Compatible Triangulations

5 weeks ago by Vaguery

We consider the conjecture by Aichholzer, Aurenhammer, Hurtado, and Krasser that any two points sets with the same cardinality and the same size convex hull can be triangulated in the "same" way, more precisely via \emph{compatible triangulations}. We show counterexamples to various strengthened versions of this conjecture.

computational-geometry
equivalence
triangulation
algorithms
rather-interesting
feature-construction
graph-theory
to-simulate
to-write-about
5 weeks ago by Vaguery

[1806.03333] The rainbow-spectrum of RNA secondary structures

6 weeks ago by Vaguery

In this paper we analyze the length-spectrum of rainbows in RNA secondary structures. A rainbow in a secondary structure is a maximal arc with respect to the partial order induced by nesting. We show that there is a significant gap in this length-spectrum. We shall prove that there asymptotically almost surely exists a unique longest rainbow of length at least n−O(n1/2) and that with high probability any other rainbow has finite length. We show that the distribution of the length of the longest rainbow converges to a discrete limit law and that, for finite k, the distribution of rainbows of length k, becomes for large n a negative binomial distribution. We then put the results of this paper into context, comparing the analytical results with those observed in RNA minimum free energy structures, biological RNA structures and relate our findings to the sparsification of folding algorithms.

structural-biology
RNA-folding
hey-I-know-this-guy
molecular-design
simulation
rather-interesting
feature-construction
to-write-about
to-simulate
consider:extreme-cases
consider:feature-discovery
6 weeks ago by Vaguery

[1910.10288] Location-Relative Attention Mechanisms For Robust Long-Form Speech Synthesis

6 weeks ago by Vaguery

Despite the ability to produce human-level speech for in-domain text, attention-based end-to-end text-to-speech (TTS) systems suffer from text alignment failures that increase in frequency for out-of-domain text. We show that these failures can be addressed using simple location-relative attention mechanisms that do away with content-based query/key comparisons. We compare two families of attention mechanisms: location-relative GMM-based mechanisms and additive energy-based mechanisms. We suggest simple modifications to GMM-based attention that allow it to align quickly and consistently during training, and introduce a new location-relative attention mechanism to the additive energy-based family, called Dynamic Convolution Attention (DCA). We compare the various mechanisms in terms of alignment speed and consistency during training, naturalness, and ability to generalize to long utterances, and conclude that GMM attention and DCA can generalize to very long utterances, while preserving naturalness for shorter, in-domain utterances.

speech-synthesis
natural-language-processing
neural-networks
recurrent-networks
algorithms
feature-construction
rather-interesting
to-write-about
to-simulate
6 weeks ago by Vaguery

[1611.01090] General and Fractional Hypertree Decompositions: Hard and Easy Cases

6 weeks ago by Vaguery

Hypertree decompositions, as well as the more powerful generalized hypertree decompositions (GHDs), and the yet more general fractional hypertree decompositions (FHD) are hypergraph decomposition methods successfully used for answering conjunctive queries and for the solution of constraint satisfaction problems. Every hypergraph H has a width relative to each of these decomposition methods: its hypertree width hw(H), its generalized hypertree width ghw(H), and its fractional hypertree width fhw(H), respectively.

It is known that hw(H) <= k can be checked in polynomial time for fixed k, while checking ghw(H) <= k is NP-complete for any k greater than or equal to 3. The complexity of checking fhw(H) <= k for a fixed k has been open for more than a decade.

We settle this open problem by showing that checking fhw(H) <= k is NP-complete, even for k=2. The same construction allows us to prove also the NP-completeness of checking ghw(H) <= k for k=2. After proving these hardness results, we identify meaningful restrictions, for which checking for bounded ghw or fhw becomes tractable.

constraint-satisfaction
hypergraphs
representation
rather-interesting
computational-complexity
algorithms
feature-construction
to-understand
to-write-about
consider:simulation
consider:feature-discovery
It is known that hw(H) <= k can be checked in polynomial time for fixed k, while checking ghw(H) <= k is NP-complete for any k greater than or equal to 3. The complexity of checking fhw(H) <= k for a fixed k has been open for more than a decade.

We settle this open problem by showing that checking fhw(H) <= k is NP-complete, even for k=2. The same construction allows us to prove also the NP-completeness of checking ghw(H) <= k for k=2. After proving these hardness results, we identify meaningful restrictions, for which checking for bounded ghw or fhw becomes tractable.

6 weeks ago by Vaguery

[1601.00670] Variational Inference: A Review for Statisticians

6 weeks ago by Vaguery

One of the core problems of modern statistics is to approximate difficult-to-compute probability densities. This problem is especially important in Bayesian statistics, which frames all inference about unknown quantities as a calculation involving the posterior density. In this paper, we review variational inference (VI), a method from machine learning that approximates probability densities through optimization. VI has been used in many applications and tends to be faster than classical methods, such as Markov chain Monte Carlo sampling. The idea behind VI is to first posit a family of densities and then to find the member of that family which is close to the target. Closeness is measured by Kullback-Leibler divergence. We review the ideas behind mean-field variational inference, discuss the special case of VI applied to exponential family models, present a full example with a Bayesian mixture of Gaussians, and derive a variant that uses stochastic optimization to scale up to massive data. We discuss modern research in VI and highlight important open problems. VI is powerful, but it is not yet well understood. Our hope in writing this paper is to catalyze statistical research on this class of algorithms.

machine-learning
statistics
feature-construction
to-understand
algorithms
6 weeks ago by Vaguery

[1905.13195] Modeling Uncertainty by Learning a Hierarchy of Deep Neural Connections

8 weeks ago by Vaguery

Modeling uncertainty in deep neural networks, despite recent important advances, is still an open problem. Bayesian neural networks are a powerful solution, where the prior over network weights is a design choice, often a normal distribution or other distribution encouraging sparsity. However, this prior is agnostic to the generative process of the input data, which might lead to unwarranted generalization for out-of-distribution tested data. We suggest the presence of a confounder for the relation between the input data and the discriminative function given the target label. We propose an approach for modeling this confounder by sharing neural connectivity patterns between the generative and discriminative networks. This approach leads to a new deep architecture, where networks are sampled from the posterior of local causal structures, and coupled into a compact hierarchy. We demonstrate that sampling networks from this hierarchy, proportionally to their posterior, is efficient and enables estimating various types of uncertainties. Empirical evaluations of our method demonstrate significant improvement compared to state-of-the-art calibration and out-of-distribution detection methods.

machine-learning
statistics
meta-modeling
feature-construction
model-interrogation
neural-networks
to-write-about
to-simulate
8 weeks ago by Vaguery

[1812.02987] Time Series Featurization via Topological Data Analysis

november 2019 by Vaguery

We develop a novel algorithm for feature extraction in time series data by leveraging tools from topological data analysis. Our algorithm provides a simple, efficient way to successfully harness topological features of the attractor of the underlying dynamical system for an observed time series. The proposed methodology relies on the persistent landscapes and silhouette of the Rips complex obtained after a de-noising step based on principal components applied to a time-delayed embedding of a noisy, discrete time series sample. We analyze the stability properties of the proposed approach and show that the resulting TDA-based features are robust to sampling noise. Experiments on synthetic and real-world data demonstrate the effectiveness of our approach. We expect our method to provide new insights on feature extraction from granular, noisy time series data.

time-series
feature-construction
feature-extraction
topology
statistics
heuristics
numerical-methods
to-understand
to-simulate
november 2019 by Vaguery

[1304.1909] Network Farthest-Point Diagrams

november 2019 by Vaguery

Consider the continuum of points along the edges of a network, i.e., an undirected graph with positive edge weights. We measure distance between these points in terms of the shortest path distance along the network, known as the network distance. Within this metric space, we study farthest points.

We introduce network farthest-point diagrams, which capture how the farthest points---and the distance to them---change as we traverse the network. We preprocess a network G such that, when given a query point q on G, we can quickly determine the farthest point(s) from q in G as well as the farthest distance from q in G. Furthermore, we introduce a data structure supporting queries for the parts of the network that are farther away from q than some threshold R > 0, where R is part of the query.

We also introduce the minimum eccentricity feed-link problem defined as follows. Given a network G with geometric edge weights and a point p that is not on G, connect p to a point q on G with a straight line segment pq, called a feed-link, such that the largest network distance from p to any point in the resulting network is minimized. We solve the minimum eccentricity feed-link problem using eccentricity diagrams. In addition, we provide a data structure for the query version, where the network G is fixed and a query consists of the point p.

network-theory
computational-geometry
feature-construction
rather-interesting
optimization
to-simulate
to-write-about
We introduce network farthest-point diagrams, which capture how the farthest points---and the distance to them---change as we traverse the network. We preprocess a network G such that, when given a query point q on G, we can quickly determine the farthest point(s) from q in G as well as the farthest distance from q in G. Furthermore, we introduce a data structure supporting queries for the parts of the network that are farther away from q than some threshold R > 0, where R is part of the query.

We also introduce the minimum eccentricity feed-link problem defined as follows. Given a network G with geometric edge weights and a point p that is not on G, connect p to a point q on G with a straight line segment pq, called a feed-link, such that the largest network distance from p to any point in the resulting network is minimized. We solve the minimum eccentricity feed-link problem using eccentricity diagrams. In addition, we provide a data structure for the query version, where the network G is fixed and a query consists of the point p.

november 2019 by Vaguery

[1605.06386] $k$-core percolation on complex networks: Comparing random, localized and targeted attacks

november 2019 by Vaguery

The type of malicious attack inflicting on networks greatly influences their stability under ordinary percolation in which a node fails when it becomes disconnected from the giant component. Here we study its generalization, k-core percolation, in which a node fails when it loses connection to a threshold k number of neighbors. We study and compare analytically and by numerical simulations of k-core percolation the stability of networks under random attacks (RA), localized attacks (LA) and targeted attacks (TA), respectively. By mapping a network under LA or TA into an equivalent network under RA, we find that in both single and interdependent networks, TA exerts the greatest damage to the core structure of a network. We also find that for Erdős-Rényi (ER) networks, LA and RA exert equal damage to the core structure whereas for scale-free (SF) networks, LA exerts much more damage than RA does to the core structure.

network-theory
robustness
mechanism-design
small-world
social-networks
security
dynamics
planning
to-simulate
to-write-about
feature-construction
looking-to-see
consider:online-learning
november 2019 by Vaguery

[1804.02098] The evolution of the structure of ABC-minimal trees

october 2019 by Vaguery

The atom-bond connectivity (ABC) index is a degree-based molecular descriptor that found diverse chemical applications. Characterizing trees with minimum ABC-index remained an elusive open problem even after serious attempts and is considered by some as one of the most intriguing open problems in mathematical chemistry. In this paper, we describe the exact structure of the extremal trees with sufficiently many vertices and we show how their structure evolves when the number of vertices grows. An interesting fact is that their radius is at most~5 and that all vertices except for one have degree at most 54. In fact, all but at most O(1) vertices have degree 1, 2, 4, or 53. Let $\gamma_n = \min\{\abc(T) : T \text{ is a tree of order } n\}$. It is shown that γn=1365153‾‾‾√(1+2655‾‾‾√+156106‾‾‾‾√)n+O(1)≈0.67737178n+O(1).

theoretical-chemistry
graph-theory
algorithms
combinatorics
computational-complexity
rather-interesting
to-understand
feature-construction
to-write-about
to-simulate
october 2019 by Vaguery

[1510.00850] Maximum Likelihood Latent Space Embedding of Logistic Random Dot Product Graphs

september 2019 by Vaguery

A latent space model for a family of random graphs assigns real-valued vectors to nodes of the graph such that edge probabilities are determined by latent positions. Latent space models provide a natural statistical framework for graph visualizing and clustering. A latent space model of particular interest is the Random Dot Product Graph (RDPG), which can be fit using an efficient spectral method; however, this method is based on a heuristic that can fail, even in simple cases. Here, we consider a closely related latent space model, the Logistic RDPG, which uses a logistic link function to map from latent positions to edge likelihoods. Over this model, we show that asymptotically exact maximum likelihood inference of latent position vectors can be achieved using an efficient spectral method. Our method involves computing top eigenvectors of a normalized adjacency matrix and scaling eigenvectors using a regression step. The novel regression scaling step is an essential part of the proposed method. In simulations, we show that our proposed method is more accurate and more robust than common practices. We also show the effectiveness of our approach over standard real networks of the karate club and political blogs.

clustering
feature-construction
rather-interesting
spectra
graph-theory
metrics
to-understand
to-write-about
consider:program-trace-comparisons
september 2019 by Vaguery

[1809.02942] Cellular automata as convolutional neural networks

september 2019 by Vaguery

Deep learning techniques have recently demonstrated broad success in predicting complex dynamical systems ranging from turbulence to human speech, motivating broader questions about how neural networks encode and represent dynamical rules. We explore this problem in the context of cellular automata (CA), simple dynamical systems that are intrinsically discrete and thus difficult to analyze using standard tools from dynamical systems theory. We show that any CA may readily be represented using a convolutional neural network with a network-in-network architecture. This motivates our development of a general convolutional multilayer perceptron architecture, which we find can learn the dynamical rules for arbitrary CA when given videos of the CA as training data. In the limit of large network widths, we find that training dynamics are strongly stereotyped across replicates, and that common patterns emerge in the structure of networks trained on different CA rulesets. We train ensembles of networks on randomly-sampled CA, and we probe how the trained networks internally represent the CA rules using an information-theoretic technique based on distributions of layer activation patterns. We find that CA with simpler rule tables produce trained networks with hierarchical structure and layer specialization, while more complex CA tend to produce shallower representations---illustrating how the underlying complexity of the CA's rules influences the specificity of these internal representations. Our results suggest how the entropy of a physical process can affect its representation when learned by neural networks.

cellular-automata
dynamical-systems
rather-interesting
to-write-about
to-simulate
machine-learning
representation
feature-construction
information-theory
consider:NN-complexity-as-constructed-features
september 2019 by Vaguery

[1908.11681] Refinement of Metrics: Erdős Number, a Case Study

september 2019 by Vaguery

We introduce a concept called refinement and develop two different ways of refining metrics. By applying these methods we produce several refinements of the shortest-path distance on the collaboration graph and hence a couple new versions of the Erdős number.

what-gets-measured-gets-fudged
rather-interesting
to-write-about
social-networks
citation-networks
feature-construction
group-theory
define-your-terms
september 2019 by Vaguery

The Connect-The-Dots family of puzzles

september 2019 by Vaguery

In this paper we introduce several innovative variants on the classic Connect-The-Dots puzzle. We study the underlying geometric principles and investigate methods for the automatic generation of high-quality puzzles from line drawings.

Specifically, we introduce three new variants of the classic Connect-The-Dots puzzle. These new variants use different rules for drawing connections, and have several advantages: no need for printed numbers in the puzzle (which look ugly in the final drawing), and perhaps more challenging "game play", making the puzzles suitable for different age groups. We study the rules of all four variants in the family, and design principles describing what makes a good puzzle. We identify general principles that apply across the different variants, as well as specific implementations of those principles in the different variants. We make these mathematically precise in the form of criteria a puzzle should satisfy.

Furthermore, we investigate methods for the automatic generation of puzzles from a plane graph that describes the input drawing. We show that the problem of generating a good puzzle --one satisfying the mentioned criteria-- is computationally hard, and present several heuristic algorithms.

Using our implementation for generating puzzles, we evaluate the quality of the resulting puzzles with respect to two parameters: one for similarity to the original line drawing, and one for ambiguity; i.e. what is the visual accuracy needed to solve the puzzle.

image-processing
feature-construction
algorithms
rather-interesting
optimization
performance-measure
consider:looking-to-see
consider:representation
Specifically, we introduce three new variants of the classic Connect-The-Dots puzzle. These new variants use different rules for drawing connections, and have several advantages: no need for printed numbers in the puzzle (which look ugly in the final drawing), and perhaps more challenging "game play", making the puzzles suitable for different age groups. We study the rules of all four variants in the family, and design principles describing what makes a good puzzle. We identify general principles that apply across the different variants, as well as specific implementations of those principles in the different variants. We make these mathematically precise in the form of criteria a puzzle should satisfy.

Furthermore, we investigate methods for the automatic generation of puzzles from a plane graph that describes the input drawing. We show that the problem of generating a good puzzle --one satisfying the mentioned criteria-- is computationally hard, and present several heuristic algorithms.

Using our implementation for generating puzzles, we evaluate the quality of the resulting puzzles with respect to two parameters: one for similarity to the original line drawing, and one for ambiguity; i.e. what is the visual accuracy needed to solve the puzzle.

september 2019 by Vaguery

[1403.0362] Determining pure discrete spectrum for some self-affine tilings

september 2019 by Vaguery

By the algorithm implemented in the paper [2] by Akiyama-Lee and some of its predecessors, we have examined the pure discreteness of the spectrum for all irreducible Pisot substitutions of trace less than or equal to 2, and some cases of planar tilings generated by boundary substitutions due to the paper [17] by Kenyon.

aperiodic-tiling
feature-construction
plane-geometry
tiling
rather-interesting
spectra
to-understand
to-simulate
algorithms
september 2019 by Vaguery

[math-ph/0212015] Combinatorial problems of (quasi-)crystallography

september 2019 by Vaguery

Several combinatorial problems of (quasi-)crystallography are reviewed with special emphasis on a unified approach, valid for both crystals and quasicrystals. In particular, we consider planar sublattices, similarity sublattices, coincidence sublattices, their module counterparts, and central and averaged shelling. The corresponding counting functions are encapsulated in Dirichlet series generating functions, with explicit results for the triangular lattice and the twelvefold symmetric shield tiling. Other combinatorial properties are briefly summarised.

plane-geometry
tiling
aperiodic-tiling
rather-interesting
feature-construction
condensed-matter
to-write-about
to-simulate
september 2019 by Vaguery

[1806.00579] Dilated floor functions having nonnegative commutator I. Positive and mixed sign dilations

september 2019 by Vaguery

In this paper and its sequel we classify the set S of all real parameter pairs (α,β) such that the dilated floor functions fα(x)=⌊αx⌋ and fβ(x)=⌊βx⌋ have a nonnegative commutator, i.e. [fα,fβ](x)=⌊α⌊βx⌋⌋−⌊β⌊αx⌋⌋≥0 for all real x. The relation [fα,fβ]≥0 induces a preorder on the set of non-zero dilation factors α,β, which extends the divisibility partial order on positive integers. This paper treats the cases where at least one of the dilation parameters α or β is nonnegative. The analysis of the positive dilations case is related to the theory of Beatty sequences and to the Diophantine Frobenius problem in two generators.

number-theory
constraint-satisfaction
algebra
rather-interesting
elliptic-curves
feature-construction
to-write-about
to-understand
september 2019 by Vaguery

[1909.00917] New Stick Number Bounds from Random Sampling of Confined Polygons

september 2019 by Vaguery

The stick number of a knot is the minimum number of segments needed to build a polygonal version of the knot. Despite its elementary definition and relevance to physical knots, the stick number is poorly understood: for most knots we only know bounds on the stick number. We adopt a Monte Carlo approach to finding better bounds, producing very large ensembles of random polygons in tight confinement to look for new examples of knots constructed from few segments. We generated a total of 220 billion random polygons, yielding either the exact stick number or an improved upper bound for more than 40% of the knots with 10 or fewer crossings for which the stick number was not previously known. We summarize the current state of the art in Appendix A, which gives the best known bounds on stick number for all knots up to 10 crossings.

knot-theory
computational-geometry
rather-interesting
feature-construction
constraint-satisfaction
open-questions
to-write-about
to-understand
to-simulate
september 2019 by Vaguery

[1908.07647] Line and Plane Cover Numbers Revisited

august 2019 by Vaguery

A measure for the visual complexity of a straight-line crossing-free drawing of a graph is the minimum number of lines needed to cover all vertices. For a given graph G, the minimum such number (over all drawings in dimension d∈{2,3}) is called the \emph{d-dimensional weak line cover number} and denoted by π1d(G). In 3D, the minimum number of \emph{planes} needed to cover all vertices of~G is denoted by π23(G). When edges are also required to be covered, the corresponding numbers ρ1d(G) and ρ23(G) are called the \emph{(strong) line cover number} and the \emph{(strong) plane cover number}.

Computing any of these cover numbers -- except π12(G) -- is known to be NP-hard. The complexity of computing π12(G) was posed as an open problem by Chaplick et al. [WADS 2017]. We show that it is NP-hard to decide, for a given planar graph~G, whether π12(G)=2. We further show that the universal stacked triangulation of depth~d, Gd, has π12(Gd)=d+1. Concerning~3D, we show that any n-vertex graph~G with ρ23(G)=2 has at most 5n−19 edges, which is tight.

graph-layout
optimization
algorithms
computational-complexity
computational-geometry
rather-interesting
to-simulate
feature-construction
Computing any of these cover numbers -- except π12(G) -- is known to be NP-hard. The complexity of computing π12(G) was posed as an open problem by Chaplick et al. [WADS 2017]. We show that it is NP-hard to decide, for a given planar graph~G, whether π12(G)=2. We further show that the universal stacked triangulation of depth~d, Gd, has π12(Gd)=d+1. Concerning~3D, we show that any n-vertex graph~G with ρ23(G)=2 has at most 5n−19 edges, which is tight.

august 2019 by Vaguery

[1907.03902] Uncertainty and causal emergence in complex networks

august 2019 by Vaguery

The connectivity of a network conveys information about the dependencies between nodes. We show that this information can be analyzed by measuring the uncertainty (and certainty) contained in paths along nodes and links in a network. Specifically, we derive from first principles a measure known as effective information and describe its behavior in common network models. Networks with higher effective information contain more information within the dependencies between nodes. We show how subgraphs of nodes can be grouped into macro-nodes, reducing the size of a network while increasing its effective information, a phenomenon known as causal emergence. We find that causal emergence is common in simulated and real networks across biological, social, informational, and technological domains. Ultimately, these results show that the emergence of higher scales in networks can be directly assessed, and that these higher scales offer a way to create certainty out of uncertainty.

network-theory
rather-interesting
robustness
looking-to-see
to-write-about
to-understand
feature-construction
consider:causal-gp-dynamics
august 2019 by Vaguery

[1410.5115] Remarks on the the circumcenter of mass

august 2019 by Vaguery

Suppose that to every non-degenerate simplex Delta in n-dimensional Euclidean space a `center' C(Delta) is assigned so that the following assumptions hold: (i) The map that assigns C(Delta) to Delta commutes with similarities and is invariant under the permutations of the vertices of the simplex; (ii) The map that assigns Vol(Delta) C(Delta) to Delta is polynomial in the coordinates of the vertices of the simplex. Then C(Delta) is an affine combination of the center of mass and the circumcenter of Delta (with the coefficients independent of the simplex). The motivation for this theorem comes from the recent study of the circumcenter of mass of simplicial polytopes by the authors and by A. Akopyan.

plane-geometry
construction
algorithms
feature-construction
statistics
nudge-targets
consider:looking-to-see
august 2019 by Vaguery

[1809.09561] Evaluating stochastic seeding strategies in networks

july 2019 by Vaguery

When trying to maximize the adoption of a behavior in a population connected by a social network, it is common to strategize about where in the network to seed the behavior, often with an element of randomness. Selecting seeds uniformly at random is a basic but compelling strategy in that it distributes seeds broadly throughout the network. A more sophisticated stochastic strategy, one-hop targeting, is to select random network neighbors of random individuals; this exploits a version of the friendship paradox, whereby the friend of a random individual is expected to have more friends than a random individual, with the hope that seeding a behavior at more connected individuals leads to more adoption. Many seeding strategies have been proposed, but empirical evaluations have demanded large field experiments designed specifically for this purpose and have yielded relatively imprecise comparisons of strategies. Here we show how stochastic seeding strategies can be evaluated more efficiently in such experiments, how they can be evaluated "off-policy" using existing data arising from experiments designed for other purposes, and how to design more efficient experiments. In particular, we consider contrasts between stochastic seeding strategies and analyze nonparametric estimators adapted from policy evaluation and importance sampling. We use simulations on real networks to show that the proposed estimators and designs can dramatically increase precision while yielding valid inference. We then apply our proposed estimators to two field experiments, one that assigned households to an intensive marketing intervention and one that assigned students to an anti-bullying intervention.

social-networks
feature-construction
rather-interesting
social-engineering
network-theory
to-understand
to-write-about
epidemiology
cultural-dynamics
to-simulate
july 2019 by Vaguery

[1805.04038] Packing and domination parameters in digraphs

july 2019 by Vaguery

Given a digraph D=(V,A), a set B⊂V is a packing set in D if there are no arcs joining vertices of B and for any two vertices x,y∈B the sets of in-neighbors of x and y are disjoint. The set S is a dominating set (an open dominating set) in D if every vertex not in S (in V) has an in-neighbor in S. Moreover, a dominating set S is called a total dominating set if the subgraph induced by S has no isolated vertices. The packing sets of maximum cardinality and the (total, open) dominating sets of minimum cardinality in digraphs are studied in this article. We prove that the two optimal sets concerning packing and domination achieve the same value for directed trees, and give some applications of it. We also show analogous equalities for all connected contrafunctional digraphs, and characterize all such digraphs D for which such equalities are satisfied. Moreover, sharp bounds on the maximum and the minimum cardinalities of packing and dominating sets, respectively, are given for digraphs. Finally, we present solutions for two open problems, concerning total and open dominating sets of minimum cardinality, pointed out in [Australas. J. Combin. 39 (2007), 283--292].

graph-theory
feature-construction
combinatorics
consider:looking-to-see
consider:extreme-values
to-simulate
july 2019 by Vaguery

[1305.5752] Symmetry detection of auxetic behaviour in 2D frameworks

july 2019 by Vaguery

A symmetry-extended Maxwell treatment of the net mobility of periodic bar-and-joint frameworks is used to derive a sufficient condition for auxetic behaviour of a 2D material. The type of auxetic behaviour that can be detected by symmetry has Poisson's ratio -1, with equal expansion/contraction in all directions, and is here termed equiauxetic. A framework may have a symmetry-detectable equiauxetic mechanism if it belongs to a plane group that includes rotational axes of order n = 6, 4, or 3. If the reducible representation for the net mobility contains mechanisms that preserve full rotational symmetry (A modes), these are equiauxetic. In addition, for n = 6, mechanisms that halve rotational symmetry (B modes) are also equiauxetic.

materials-science
kinematics
statics
graph-theory
rather-interesting
feature-construction
symmetry
physics!
simulation
to-write-about
to-simulate
july 2019 by Vaguery

[1903.06778] Matrix scaling limits in finitely many iterations

july 2019 by Vaguery

The alternate row and column scaling algorithm applied to a positive n×n matrix A converges to a doubly stochastic matrix S(A), sometimes called the \emph{Sinkhorn limit} of A. For every positive integer n, a two parameter family of row but not column stochastic n×n positive matrices is constructed that become doubly stochastic after exactly one column scaling.

matrices
feature-construction
open-questions
number-theory
rather-interesting
to-write-about
to-simulate
consider:looking-to-see
july 2019 by Vaguery

[1903.08056] On the general position problem on Kneser graphs

july 2019 by Vaguery

In a graph G, a geodesic between two vertices x and y is a shortest path connecting x to y. A subset S of the vertices of G is in general position if no vertex of S lies on any geodesic between two other vertices of S. The size of a largest set of vertices in general position is the general position number that we denote by gp(G). Recently, Ghorbani et al, proved that for any k if n≥k3−k2+2k−2, then gp(Knn,k)=(n−1k−1), where Knn,k denotes the Kneser graph. We improve on their result and show that the same conclusion holds for n≥2k+2 and this bound is best possible. Our main tools are a result on cross-intersecting families and a slight generalization of Bollobás's inequality on intersecting set pair systems.

combinatorics
graph-theory
feature-construction
rather-interesting
algorithms
to-write-about
july 2019 by Vaguery

[1811.06678] The Potential of Learned Index Structures for Index Compression

july 2019 by Vaguery

Inverted indexes are vital in providing fast key-word-based search. For every term in the document collection, a list of identifiers of documents in which the term appears is stored, along with auxiliary information such as term frequency, and position offsets. While very effective, inverted indexes have large memory requirements for web-sized collections. Recently, the concept of learned index structures was introduced, where machine learned models replace common index structures such as B-tree-indexes, hash-indexes, and bloom-filters. These learned index structures require less memory, and can be computationally much faster than their traditional counterparts. In this paper, we consider whether such models may be applied to conjunctive Boolean querying. First, we investigate how a learned model can replace document postings of an inverted index, and then evaluate the compromises such an approach might have. Second, we evaluate the potential gains that can be achieved in terms of memory requirements. Our work shows that learned models have great potential in inverted indexing, and this direction seems to be a promising area for future research.

indexing
machine-learning
approximation
summarization
feature-construction
rather-interesting
compression
to-write-about
july 2019 by Vaguery

[1808.07409] The domino shuffling height process and its hydrodynamic limit

june 2019 by Vaguery

The famous domino shuffling algorithm was invented to generate the domino tilings of the Aztec Diamond. Using the domino height function, we view the domino shuffling procedure as a discrete-time random height process on the plane. The hydrodynamic limit from an arbitrary continuous profile is deduced to be the unique viscosity solution of a Hamilton-Jacobi equation ut+H(ux)=0, where the determinant of the Hessian of H is negative everywhere. The proof involves interpolation of the discrete process and analysis of the limiting semigroup of the evolution. In order to identify the limit, we use the theories of dimer models as well as Hamilton-Jacobi equations.

It seems that our result is the first example in d>1 where such a full hydrodynamic limit with a nonconvex Hamiltonian can be obtained for a discrete system. We also define the shuffling height process for more general periodic dimer models, where we expect similar results to hold.

combinatorics
graph-theory
feature-construction
rather-interesting
dynamical-systems
domino-tiling
to-understand
It seems that our result is the first example in d>1 where such a full hydrodynamic limit with a nonconvex Hamiltonian can be obtained for a discrete system. We also define the shuffling height process for more general periodic dimer models, where we expect similar results to hold.

june 2019 by Vaguery

[1701.04788] Width-$k$ Generalizations of Classical Permutation Statistics

may 2019 by Vaguery

We introduce new natural generalizations of the classical descent and inversion statistics for permutations, called width-k descents and width-k inversions. These variations induce generalizations of the excedance and major statistics, providing a framework in which the most well-known equidistributivity results for classical statistics are paralleled. We explore additional relationships among the statistics providing specific formulas in certain special cases. Moreover, we explore the behavior of these width-k statistics in the context of pattern avoidance.

permutations
combinatorics
feature-construction
rather-interesting
to-understand
patterns
to-simulate
to-write-about
may 2019 by Vaguery

Descriptions of the Characteristic Sequence of an Irrational | Canadian Mathematical Bulletin | Cambridge Core

april 2019 by Vaguery

We make some observations on the various descriptions of the characteristic sequence of α which have appeared in the literature. We then refine one of these descriptions in order to obtain a very simple derivation of an arithmetic expression for [nα] which appears in A. S. Fraenkel, J. Levitt, and M. Shimshoni [17]. Some concluding remarks give conditions on n which are equivalent to fn = 1.

irrational-numbers
number-theory
continued-fractions
representation
mathematical-recreations
feature-construction
april 2019 by Vaguery

[math/0003039] Hard Tiling Problems with Simple Tiles

april 2019 by Vaguery

It is well-known that the question of whether a given finite region can be tiled with a given set of tiles is NP-complete. We show that the same is true for the right tromino and square tetromino on the square lattice, or for the right tromino alone. In the process, we show that Monotone 1-in-3 Satisfiability is NP-complete for planar cubic graphs. In higher dimensions, we show NP-completeness for the domino and straight tromino for general regions on the cubic lattice, and for simply-connected regions on the four-dimensional hypercubic lattice.

tiling
domino-tiling
combinatorics
rather-interesting
emergence
proofs
to-simulate
feature-construction
consider:classification
april 2019 by Vaguery

[1611.02323] An Efficient Quasi-physical Quasi-human Algorithm for Packing Equal Circles in a Circular Container

march 2019 by Vaguery

This paper addresses the equal circle packing problem, and proposes an efficient Quasi-physical Quasi-human (QPQH) algorithm. QPQH is based on a modified Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm which we call the local BFGS and a new basin hopping strategy based on a Chinese idiom: alternate tension with relaxation. Starting from a random initial layout, we apply the local BFGS algorithm to reach a local minimum layout. The local BFGS algorithm fully utilizes the neighborhood information of each circle to considerably speed up the running time of the gradient descent process, and the efficiency is very apparent for large scale instances. When yielding a local minimum layout, the new basin-hopping strategy is to shrink the container size to different extent to generate several new layouts. Experimental results indicate that the new basin-hopping strategy is very efficient, especially for a type of layout with comparatively dense packing in the center and comparatively sparse packing around the boundary of the container. We test QPQH on the instances of n = 1,2,...,320, and obtain 66 new layouts which have smaller container sizes than the current best-known results reported in literature.

packing-problems
computational-geometry
algorithms
heuristics
rather-interesting
feature-construction
nudge-targets
consider:looking-to-see
to-write-about
to-simulate
march 2019 by Vaguery

[1805.02222] A Computer Approach to Determine the Densest Translative Tetrahedron Packings

march 2019 by Vaguery

In 1900, as a part of his 18th problem, Hilbert proposed the question to determine the densest congruent (or translative) packings of a given solid, such as the unit ball or the regular tetrahedron of unit edges. Up to now, our knowledge about this problem is still very limited, excepting the ball case. It is conjectured that, for some particular solids such as tetrahedra, cuboctahedra and octahedra, their maximal translative packing densities and their maximal lattice packing densities are identical. To attack this conjecture, this paper suggests a computer approach to determine the maximal local translative packing density of a given polytope, by studying associated color graphs and applying optimization. In particular, all the tetrahedral case, the cuboctahedral case and the octahedral case of the conjecture have been reduced into finite numbers of manageable optimization problems.

packing
open-questions
geometry
looking-to-see
representation
feature-construction
to-write-about
march 2019 by Vaguery

[1208.4836] The sensual Apollonian circle packing

march 2019 by Vaguery

The curvatures of the circles in integral Apollonian circle packings, named for Apollonius of Perga (262-190 BC), form an infinite collection of integers whose Diophantine properties have recently seen a surge in interest. Here, we give a new description of Apollonian circle packings built upon the study of the collection of bases of Z[i]^2, inspired by, and intimately related to, the `sensual quadratic form' of Conway.

number-theory
packing
plane-geometry
Conway-stuff
rather-interesting
feature-construction
performance-measure
consider:quantifying-variants
march 2019 by Vaguery

[1707.07231] Badly approximable numbers over imaginary quadratic fields

march 2019 by Vaguery

We recall the notion of nearest integer continued fractions over the Euclidean imaginary quadratic fields K and characterize the "badly approximable" numbers, (z such that there is a C(z)>0 with |z−p/q|≥C/|q|2 for all p/q∈K), by boundedness of the partial quotients in the continued fraction expansion of z. Applying this algorithm to "tagged" indefinite integral binary Hermitian forms demonstrates the existence of entire circles in ℂ whose points are badly approximable over K, with effective constants.

By other methods (the Dani correspondence), we prove the existence of circles of badly approximable numbers over any imaginary quadratic field, with loss of effectivity. Among these badly approximable numbers are algebraic numbers of every even degree over ℚ, which we characterize. All of the examples we consider are associated with cocompact Fuchsian subgroups of the Bianchi groups SL2(), where is the ring of integers in an imaginary quadratic field.

number-theory
continued-fractions
approximation
rather-interesting
feature-construction
to-understand
quadratic-numbers
By other methods (the Dani correspondence), we prove the existence of circles of badly approximable numbers over any imaginary quadratic field, with loss of effectivity. Among these badly approximable numbers are algebraic numbers of every even degree over ℚ, which we characterize. All of the examples we consider are associated with cocompact Fuchsian subgroups of the Bianchi groups SL2(), where is the ring of integers in an imaginary quadratic field.

march 2019 by Vaguery

[1811.01735] A homogeneous polynomial associated with general hypergraphs and its applications

march 2019 by Vaguery

In this paper, we define a homogeneous polynomial for a general hypergraph, and establish a remarkable connection between clique number and the homogeneous polynomial of a general hypergraph. For a general hypergraph, we explore some inequality relations among spectral radius, clique number and the homogeneous polynomial. We also give lower and upper bounds on the spectral radius in terms of the clique number.

hypergraphs
graph-theory
set-theory
feature-construction
rather-interesting
algorithms
to-understand
march 2019 by Vaguery

[1706.06083] Towards Deep Learning Models Resistant to Adversarial Attacks

march 2019 by Vaguery

Recent work has demonstrated that neural networks are vulnerable to adversarial examples, i.e., inputs that are almost indistinguishable from natural data and yet classified incorrectly by the network. In fact, some of the latest findings suggest that the existence of adversarial attacks may be an inherent weakness of deep learning models. To address this problem, we study the adversarial robustness of neural networks through the lens of robust optimization. This approach provides us with a broad and unifying view on much of the prior work on this topic. Its principled nature also enables us to identify methods for both training and attacking neural networks that are reliable and, in a certain sense, universal. In particular, they specify a concrete security guarantee that would protect against any adversary. These methods let us train networks with significantly improved resistance to a wide range of adversarial attacks. They also suggest the notion of security against a first-order adversary as a natural and broad security guarantee. We believe that robustness against such well-defined classes of adversaries is an important stepping stone towards fully resistant deep learning models.

machine-learning
adversarial-learning
coevolution
generalization
optical-illusions
feature-extraction
feature-construction
neural-networks
rather-interesting
to-write-about
march 2019 by Vaguery

[1812.08101] Efficient Representation and Counting of Antipower Factors in Words

march 2019 by Vaguery

A k-antipower (for k≥2) is a concatenation of k pairwise distinct words of the same length. The study of antipower factors of a word was initiated by Fici et al. (ICALP 2016) and first algorithms for computing antipower factors were presented by Badkobeh et al. (Inf. Process. Lett., 2018). We address two open problems posed by Badkobeh et al. Our main results are algorithms for counting and reporting factors of a word which are k-antipowers. They work in (nklogk) time and (nklogk+C) time, respectively, where C is the number of reported factors. For k=o(n/logn‾‾‾‾‾‾‾√), this improves the time complexity of (n2/k) of the solution by Badkobeh et al. Our main algorithmic tools are runs and gapped repeats. We also present an improved data structure that checks, for a given factor of a word and an integer k, if the factor is a k-antipower.

strings
combinatorics
algorithms
patterns
feature-construction
rather-interesting
nudge-targets
march 2019 by Vaguery

[PDF] Fourier Analysis and Phylogenetic Trees

february 2019 by Vaguery

Abstract. We give an overview of phylogenetic invariants: a technique for reconstructing evolutionary family trees from DNA sequence data. This method is useful in practice and is based on a number of simple ideas from elementary group theory, probability, linear algebra, and commutative algebra.

representation
rather-interesting
not-the-approach-I-expected
phylogenetics
cladistics
feature-construction
to-understand
february 2019 by Vaguery

[1701.05999] Conflict-Free Coloring of Planar Graphs

february 2019 by Vaguery

A conflict-free k-coloring of a graph assigns one of k different colors to some of the vertices such that, for every vertex v, there is a color that is assigned to exactly one vertex among v and v's neighbors. Such colorings have applications in wireless networking, robotics, and geometry, and are well-studied in graph theory. Here we study the natural problem of the conflict-free chromatic number chi_CF(G) (the smallest k for which conflict-free k-colorings exist). We provide results both for closed neighborhoods N[v], for which a vertex v is a member of its neighborhood, and for open neighborhoods N(v), for which vertex v is not a member of its neighborhood.

For closed neighborhoods, we prove the conflict-free variant of the famous Hadwiger Conjecture: If an arbitrary graph G does not contain K_{k+1} as a minor, then chi_CF(G) <= k. For planar graphs, we obtain a tight worst-case bound: three colors are sometimes necessary and always sufficient. We also give a complete characterization of the computational complexity of conflict-free coloring. Deciding whether chi_CF(G)<= 1 is NP-complete for planar graphs G, but polynomial for outerplanar graphs. Furthermore, deciding whether chi_CF(G)<= 2 is NP-complete for planar graphs G, but always true for outerplanar graphs. For the bicriteria problem of minimizing the number of colored vertices subject to a given bound k on the number of colors, we give a full algorithmic characterization in terms of complexity and approximation for outerplanar and planar graphs.

For open neighborhoods, we show that every planar bipartite graph has a conflict-free coloring with at most four colors; on the other hand, we prove that for k in {1,2,3}, it is NP-complete to decide whether a planar bipartite graph has a conflict-free k-coloring. Moreover, we establish that any general} planar graph has a conflict-free coloring with at most eight colors.

graph-theory
rather-interesting
feature-construction
network-theory
algorithms
computational-complexity
For closed neighborhoods, we prove the conflict-free variant of the famous Hadwiger Conjecture: If an arbitrary graph G does not contain K_{k+1} as a minor, then chi_CF(G) <= k. For planar graphs, we obtain a tight worst-case bound: three colors are sometimes necessary and always sufficient. We also give a complete characterization of the computational complexity of conflict-free coloring. Deciding whether chi_CF(G)<= 1 is NP-complete for planar graphs G, but polynomial for outerplanar graphs. Furthermore, deciding whether chi_CF(G)<= 2 is NP-complete for planar graphs G, but always true for outerplanar graphs. For the bicriteria problem of minimizing the number of colored vertices subject to a given bound k on the number of colors, we give a full algorithmic characterization in terms of complexity and approximation for outerplanar and planar graphs.

For open neighborhoods, we show that every planar bipartite graph has a conflict-free coloring with at most four colors; on the other hand, we prove that for k in {1,2,3}, it is NP-complete to decide whether a planar bipartite graph has a conflict-free k-coloring. Moreover, we establish that any general} planar graph has a conflict-free coloring with at most eight colors.

february 2019 by Vaguery

Divisor function - Wikipedia

february 2019 by Vaguery

In mathematics, and specifically in number theory, a divisor function is an arithmetic function related to the divisors of an integer. When referred to as the divisor function, it counts the number of divisors of an integer (including 1 and the number itself). It appears in a number of remarkable identities, including relationships on the Riemann zeta function and the Eisenstein series of modular forms. Divisor functions were studied by Ramanujan, who gave a number of important congruences and identities; these are treated separately in the article Ramanujan's sum.

number-theory
feature-construction
mathematical-recreations
GP-benchmarks
to-write-about
february 2019 by Vaguery

[1902.01023] Enhanced Hierarchical Music Structure Annotations via Feature Level Similarity Fusion

february 2019 by Vaguery

We describe a novel pipeline to automatically discover hierarchies of repeated sections in musical audio. The proposed method uses similarity network fusion (SNF) to combine different frame-level features into clean affinity matrices, which are then used as input to spectral clustering. While prior spectral clustering approaches to music structure analysis have pre-processed affinity matrices with heuristics specifically designed for this task, we show that the SNF approach directly yields segmentations which agree better with human annotators, as measured by the ``L-measure'' metric for hierarchical annotations. Furthermore, the SNF approach immediately supports arbitrarily many input features, allowing us to simultaneously discover structure encoded in timbral, harmonic, and rhythmic representations without any changes to the base algorithm.

classification
clustering
music
feature-construction
rather-interesting
indexing
to-write-about
performance-measure
february 2019 by Vaguery

[1812.01382] A new Bound for the Maker-Breaker Triangle Game

february 2019 by Vaguery

The triangle game introduced by Chvátal and Erdős (1978) is one of the most famous combinatorial games. For n,q∈ℕ, the (n,q)-triangle game is played by two players, called Maker and Breaker, on the complete graph Kn. Alternately Maker claims one edge and thereafter Breaker claims q edges of the graph. Maker wins the game if he can claim all three edges of a triangle, otherwise Breaker wins. Chvátal and Erdős (1978) proved that for q<2n+2‾‾‾‾‾‾√−5/2≈1.414n‾√ Maker has a winning strategy, and for q≥2n‾√ Breaker has a winning strategy. Since then, the problem of finding the exact leading constant for the threshold bias of the triangle game has been one of the famous open problems in combinatorial game theory. In fact, the constant is not known for any graph with a cycle and we do not even know if such a constant exists. Balogh and Samotij (2011) slightly improved the Chvátal-Erdős constant for Breaker's winning strategy from 2 to 1.935 with a randomized approach. Since then no progress was made. In this work, we present a new deterministic strategy for Breaker's win whenever n is sufficiently large and q≥(8/3+o(1))n‾‾‾‾‾‾‾‾‾‾‾‾√≈1.633n‾√, significantly reducing the gap towards the lower bound. In previous strategies Breaker chooses his edges such that one node is part of the last edge chosen by Maker, whereas the remaining node is chosen more or less arbitrarily. In contrast, we introduce a suitable potential function on the set of nodes. This allows Breaker to pick edges that connect the most `dangerous' nodes. The total potential of the game may still increase, even for several turns, but finally Breaker's strategy prevents the total potential of the game from exceeding a critical level and leads to Breaker's win.

combinatorics
game-theory
rather-interesting
feature-construction
open-questions
nudge-targets
consider:looking-to-see
february 2019 by Vaguery

[1901.10861] A Simple Explanation for the Existence of Adversarial Examples with Small Hamming Distance

february 2019 by Vaguery

The existence of adversarial examples in which an imperceptible change in the input can fool well trained neural networks was experimentally discovered by Szegedy et al in 2013, who called them "Intriguing properties of neural networks". Since then, this topic had become one of the hottest research areas within machine learning, but the ease with which we can switch between any two decisions in targeted attacks is still far from being understood, and in particular it is not clear which parameters determine the number of input coordinates we have to change in order to mislead the network. In this paper we develop a simple mathematical framework which enables us to think about this baffling phenomenon from a fresh perspective, turning it into a natural consequence of the geometry of ℝn with the L0 (Hamming) metric, which can be quantitatively analyzed. In particular, we explain why we should expect to find targeted adversarial examples with Hamming distance of roughly m in arbitrarily deep neural networks which are designed to distinguish between m input classes.

machine-learning
robustness
adversarial-examples
rather-interesting
good-explanations
to-write-about
computational-vs-systems
generalization
feature-construction
saliency
february 2019 by Vaguery

[1808.06091] Clock theorems for triangulated surfaces

february 2019 by Vaguery

We investigate triangulations of the two-dimensional sphere and torus with the faces properly colored white and black. We focus on matchings between white triangles and incident vertices. On the torus our objects are perfect pairings, whereas on the sphere this is only true after removing one triangle and its vertices. In the latter case, such matchings (first studied by Tutte) extend the notion of state in Kauffman's formal knot theory and we show that his Clock Theorem, in its form due to Gilmer and Litherland, also extends: the set of matchings naturally forms a distributive lattice. Here the role of state transposition is played by a simple local operation about black triangles. By contrast, on the torus, the analogous state transition graph is usually disconnected: some of its components still form distributive lattices with global maxima and minima, while other components contain directed cycles and are without local extrema.

combinatorics
graph-theory
topology
rather-interesting
feature-construction
february 2019 by Vaguery

A nice proof for the Law of Cosines | Continuous Everywhere but Differentiable Nowhere

february 2019 by Vaguery

And I kinda told them what to do… Meh. I was jumping way ahead to get to the formula. We weren’t savoring the thinking to get to the formula. Now we are.

That being said, I ran across something quite beautiful. A stunning proof of the Law of Cosines (at least for acute triangles) on the site trigonography.

geometry
pedagogy
visualization
rather-interesting
visual-proof
feature-construction
explanation
consider:the-mangle
That being said, I ran across something quite beautiful. A stunning proof of the Law of Cosines (at least for acute triangles) on the site trigonography.

february 2019 by Vaguery

[1706.05423] Weighted counting of integer points in a subspace

february 2019 by Vaguery

Given complex numbers w1,…,wn, we define the weight w(X) of a set X of non-negative integer n-vectors as the sum of wx11⋯wxnn over all vectors (x1,…,xn) in X. We present an algorithm, which for a set X of 0-1 vectors defined by a system of homogeneous linear equations with at most r variables per equation and at most c equations per variable, computes w(X) within relative error ϵ>0 in (rc)O(lnn−lnϵ) time provided |wj|≤β(rc√)−1 for an absolute constant β>0 and all j=1,…,n. A similar algorithm is constructed for computing the weight of a set of non-negative integer vectors satisfying linear constraints and the weight of a linear code over 𝔽p. Applications include counting weighted perfect matchings in hypergraphs, counting weighted graph homomorphisms, computing weight enumerators of linear codes with sparse code generating matrices, computing the partition function of the ferromagnetic Potts model at low temperatures and computing the hard-core model at large fugacity on biregular bipartite graphs.

representation
combinatorics
rather-interesting
graph-theory
feature-construction
indirect-representations
to-understand
february 2019 by Vaguery

[1808.06423] What Stands-in for a Missing Tool? A Prototypical Grounded Knowledge-based Approach to Tool Substitution

february 2019 by Vaguery

When a robot is operating in a dynamic environment, it cannot be assumed that a tool required to solve a given task will always be available. In case of a missing tool, an ideal response would be to find a substitute to complete the task. In this paper, we present a proof of concept of a grounded knowledge-based approach to tool substitution. In order to validate the suitability of a substitute, we conducted experiments involving 22 substitution scenarios. The substitutes computed by the proposed approach were validated on the basis of the experts' choices for each scenario. Our evaluation showed, in 20 out of 22 scenarios (91%), the approach identified the same substitutes as experts.

artificial-intelligence
feature-construction
learning-from-data
rather-interesting
to-write-about
consider:looking-to-see
february 2019 by Vaguery

[1602.06093] Self-organisation in cellular automata with coalescent particles: qualitative and quantitative approaches

february 2019 by Vaguery

This article introduces new tools to study self-organisation in a family of simple cellular automata which contain some particle-like objects with good collision properties (coalescence) in their time evolution. We draw an initial configuration at random according to some initial σ-ergodic measure μ, and use the limit measure to descrbe the asymptotic behaviour of the automata. We first take a qualitative approach, i.e. we obtain information on the limit measure(s). We prove that only particles moving in one particular direction can persist asymptotically. This provides some previously unknown information on the limit measures of various deterministic and probabilistic cellular automata: 3 and 4-cyclic cellular automata (introduced in [Fis90b]), one-sided captive cellular automata (introduced in [The04]), N. Fat{è}s' candidate to solve the density classification problem [Fat13], self stabilization process toward a discrete line [RR15]... In a second time we restrict our study to to a subclass, the gliders cellular automata. For this class we show quantitative results, consisting in the asymptotic law of some parameters: the entry times (generalising [KFD11]), the density of particles and the rate of convergence to the limit measure.

cellular-automata
self-organization
feature-extraction
feature-construction
define-your-terms
information-theory
nonlinear-dynamics
to-understand
february 2019 by Vaguery

[1812.05225] Finding the origin of noise transients in LIGO data with machine learning

january 2019 by Vaguery

Quality improvement of interferometric data collected by gravitational-wave detectors such as Advanced LIGO and Virgo is mission critical for the success of gravitational-wave astrophysics. Gravitational-wave detectors are sensitive to a variety of disturbances of non-astrophysical origin with characteristic frequencies in the instrument band of sensitivity. Removing non-astrophysical artifacts that corrupt the data stream is crucial for increasing the number and statistical significance of gravitational-wave detections and enabling refined astrophysical interpretations of the data. Machine learning has proved to be a powerful tool for analysis of massive quantities of complex data in astronomy and related fields of study. We present two machine learning methods, based on random forest and genetic programming algorithms, that can be used to determine the origin of non-astrophysical transients in the LIGO detectors. We use two classes of transients with known instrumental origin that were identified during the first observing run of Advanced LIGO to show that the algorithms can successfully identify the origin of non-astrophysical transients in real interferometric data and thus assist in the mitigation of instrumental and environmental disturbances in gravitational-wave searches. While the data sets described in this paper are specific to LIGO, and the exact procedures employed were unique to the same, the random forest and genetic programming code bases and means by which they were applied as a dual machine learning approach are completely portable to any number of instruments in which noise is believed to be generated through mechanical couplings, the source of which is not yet discovered.

genetic-programming
hey-I-know-this-guy
astrophysics
data-analysis
data-mining
to-understand
feature-construction
classification
january 2019 by Vaguery

[1812.06162] An Empirical Model of Large-Batch Training

january 2019 by Vaguery

In an increasing number of domains it has been demonstrated that deep learning models can be trained using relatively large batch sizes without sacrificing data efficiency. However the limits of this massive data parallelism seem to differ from domain to domain, ranging from batches of tens of thousands in ImageNet to batches of millions in RL agents that play the game Dota 2. To our knowledge there is limited conceptual understanding of why these limits to batch size differ or how we might choose the correct batch size in a new domain. In this paper, we demonstrate that a simple and easy-to-measure statistic called the gradient noise scale predicts the largest useful batch size across many domains and applications, including a number of supervised learning datasets (MNIST, SVHN, CIFAR-10, ImageNet, Billion Word), reinforcement learning domains (Atari and Dota), and even generative model training (autoencoders on SVHN). We find that the noise scale increases as the loss decreases over a training run and depends on the model size primarily through improved model performance. Our empirically-motivated theory also describes the tradeoff between compute-efficiency and time-efficiency, and provides a rough model of the benefits of adaptive batch-size training.

machine-learning
algorithms
fitness-landscapes
feature-construction
hardness
to-write-about
january 2019 by Vaguery

How AI Training Scales

january 2019 by Vaguery

We’ve discovered that the gradient noise scale, a simple statistical metric, predicts the parallelizability of neural network training on a wide range of tasks. Since complex tasks tend to have noisier gradients, increasingly large batch sizes are likely to become useful in the future, removing one potential limit to further growth of AI systems. More broadly, these results show that neural network training need not be considered a mysterious art, but can be rigorized and systematized.

stochastic-systems
machine-learning
problem-solving
feature-construction
rather-interesting
to-write-about
consider:nongradient-methods
consider:lexicase
consider:data-balancing
january 2019 by Vaguery

Tanya Khovanova's Math Blog » Blog Archive » 3-Symmetric Permutations

january 2019 by Vaguery

I want to study patterns inside permutations. Consider a permutation of size 4: 1432. Today I am excited by ordered subset of size 3 inside this permutation. For example, I can drop the last number and look at 143. The ordering in 143 is the same as in 132, or, as a mathematician would say, 143 is order-isomorphic to 132. In my example of 1432, I have four subsets depending on which number I remove: 432 is order-isomorphic to 321, while 132, 142 and 143 are all order-isomorphic to 132.

The density of a pattern 123 in the permutation 1432 is the ratio of subsets of size 3 that are order-isomorphic to 123 to all subsets of size 3. As I already calculated, the density of 123 in 1432 is zero, while the density of 321 is 1/4, and the density of 132 is 3/4.

permutations
feature-construction
combinatorics
mathematical-recreations
conjecture
to-write-about
The density of a pattern 123 in the permutation 1432 is the ratio of subsets of size 3 that are order-isomorphic to 123 to all subsets of size 3. As I already calculated, the density of 123 in 1432 is zero, while the density of 321 is 1/4, and the density of 132 is 3/4.

january 2019 by Vaguery

Tanya Khovanova's Math Blog » Blog Archive » 3-Symmetric Graphs

january 2019 by Vaguery

In my previous post I described 3-symmetric permutations. Now I want to define 3-symmetric graphs.

A reminder: a k-symmetric permutation is such that the densities of all permutations of size k in it are the same. In particular a 2-symmetric permutation has the same number of inversions and non-inversions. How do we translate this to graphs? I call a graph 2-symmetric if it has the same number of edges as non-edges. 2-symmetric graphs are easy to construct, but they only exist if the number of vertices, n, is such that n choose 2 is even. The simplest non-trivial examples are graphs with 4 vertices and three edges.

graph-theory
feature-construction
rather-interesting
mathematical-recreations
A reminder: a k-symmetric permutation is such that the densities of all permutations of size k in it are the same. In particular a 2-symmetric permutation has the same number of inversions and non-inversions. How do we translate this to graphs? I call a graph 2-symmetric if it has the same number of edges as non-edges. 2-symmetric graphs are easy to construct, but they only exist if the number of vertices, n, is such that n choose 2 is even. The simplest non-trivial examples are graphs with 4 vertices and three edges.

january 2019 by Vaguery

[1808.00722] On the Harborth constant of $C_3 oplus C_{3n}$

december 2018 by Vaguery

For a finite abelian group (G,+,0) the Harborth constant 𝗀(G) is the smallest integer k such that each squarefree sequence over G of length k, equivalently each subset of G of cardinality at least k, has a subsequence of length exp(G) whose sum is 0. In this paper, it is established that 𝗀(G)=3n+3 for prime n≠3 and 𝗀(C3⊕C9)=13.

group-theory
combinatorics
algorithms
rather-interesting
feature-construction
to-understand
to-write-about
an-example-would-be-useful-about-now
december 2018 by Vaguery

CTK Insights » Blog Archive It Never Stops with Pythagoras - CTK Insights

december 2018 by Vaguery

In the previous blog I described a discovery of Hirotaka Ebisui and an observation by Thanos Kalogerakis, both concerning what's known as Vecten's configuration. Vecten's configuration is a generalization of the famous Bride's Chair that underlies Euclid I.47, generally identified as the proof of the Pythagorean Theorem, although by now there are hundreds of them. In response to the previous post, Long Huynh Huu has expanded the two results, with the tools from linear algebra. To cut that introduction short, earlier today I was informed by Thanos Kalogerakis of a post by Carlos Hugo Olivera Días at the Peru Geometrico facebook group that adds another (and most fundamental at that) link to the just described chain of discoveries.

plane-geometry
mathematical-recreations
rather-interesting
discovery
feature-construction
to-write-about
december 2018 by Vaguery

[1706.06571] The Distribution of Knots in the Petaluma Model

december 2018 by Vaguery

The representation of knots by petal diagrams (Adams et al. 2012) naturally defines a sequence of distributions on the set of knots. In this article we establish some basic properties of this randomized knot model. We prove that in the random n-petal model the probability of obtaining every specific knot type decays to zero as n, the number of petals, grows. In addition we improve the bounds relating the crossing number and the petal number of a knot. This implies that the n-petal model represents at least exponentially many distinct knots.

Past approaches to showing, in some random models, that individual knot types occur with vanishing probability, rely on the prevalence of localized connect summands as the complexity of the knot increases. However this phenomenon is not clear in other models, including petal diagrams, random grid diagrams, and uniform random polygons. Thus we provide a new approach to investigate this question.

knot-theory
representation
rather-interesting
to-write-about
topology
feature-construction
Past approaches to showing, in some random models, that individual knot types occur with vanishing probability, rely on the prevalence of localized connect summands as the complexity of the knot increases. However this phenomenon is not clear in other models, including petal diagrams, random grid diagrams, and uniform random polygons. Thus we provide a new approach to investigate this question.

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

[1701.06377] Counting Arithmetical Structures on Paths and Cycles

december 2018 by Vaguery

Let G be a finite, simple, connected graph. An arithmetical structure on G is a pair of positive integer vectors d,r such that (diag(d)−A)r=0, where A is the adjacency matrix of G. We investigate the combinatorics of arithmetical structures on path and cycle graphs, as well as the associated critical groups (the cokernels of the matrices (diag(d)−A)). For paths, we prove that arithmetical structures are enumerated by the Catalan numbers, and we obtain refined enumeration results related to ballot sequences. For cycles, we prove that arithmetical structures are enumerated by the binomial coefficients (2n−1n−1), and we obtain refined enumeration results related to multisets. In addition, we determine the critical groups for all arithmetical structures on paths and cycles.

graph-theory
combinatorics
enumeration
counting
to-understand
matrices
feature-construction
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

Democracy as an information system — Crooked Timber

december 2018 by Vaguery

Democracy is an information system.

That’s the starting place of our new paper: “Common-Knowledge Attacks on Democracy.” In it, we look at democracy through the lens of information security, trying to understand the current waves of Internet disinformation attacks. Specifically, we wanted to explain why the same disinformation campaigns that act as a stabilizing influence in Russia are destabilizing in the United States.

The answer revolves around the different ways autocracies and democracies work as information systems. We start by differentiating between two types of knowledge that societies use in their political systems. The first is common political knowledge, which is the body of information that people in a society broadly agree on. People agree on who the rulers are and what their claim to legitimacy is. People agree broadly on how their government works, even if they don’t like it. In a democracy, people agree about how elections work: how districts are created and defined, how candidates are chosen, and that their votes count—even if only roughly and imperfectly.

social-norms
democracy
cultural-dynamics
propaganda
public-policy
political-economy
rather-interesting
epidemiology
feature-construction
discriminators
fascism
signaling
That’s the starting place of our new paper: “Common-Knowledge Attacks on Democracy.” In it, we look at democracy through the lens of information security, trying to understand the current waves of Internet disinformation attacks. Specifically, we wanted to explain why the same disinformation campaigns that act as a stabilizing influence in Russia are destabilizing in the United States.

The answer revolves around the different ways autocracies and democracies work as information systems. We start by differentiating between two types of knowledge that societies use in their political systems. The first is common political knowledge, which is the body of information that people in a society broadly agree on. People agree on who the rulers are and what their claim to legitimacy is. People agree broadly on how their government works, even if they don’t like it. In a democracy, people agree about how elections work: how districts are created and defined, how candidates are chosen, and that their votes count—even if only roughly and imperfectly.

december 2018 by Vaguery

[1706.07900] Tree-Residue Vertex-Breaking: a new tool for proving hardness

december 2018 by Vaguery

In this paper, we introduce a new problem called Tree-Residue Vertex-Breaking (TRVB): given a multigraph $G$ some of whose vertices are marked "breakable," is it possible to convert $G$ into a tree via a sequence of "vertex-breaking" operations (replacing a degree-$k$ breakable vertex by $k$ degree-$1$ vertices, disconnecting the $k$ incident edges)?

We characterize the computational complexity of TRVB with any combination of the following additional constraints: $G$ must be planar, $G$ must be a simple graph, the degree of every breakable vertex must belong to an allowed list $B$, and the degree of every unbreakable vertex must belong to an allowed list $U$. The two results which we expect to be most generally applicable are that (1) TRVB is polynomially solvable when breakable vertices are restricted to have degree at most $3$; and (2) for any $k \ge 4$, TRVB is NP-complete when the given multigraph is restricted to be planar and to consist entirely of degree-$k$ breakable vertices. To demonstrate the use of TRVB, we give a simple proof of the known result that Hamiltonicity in max-degree-$3$ square grid graphs is NP-hard.

We also demonstrate a connection between TRVB and the Hypergraph Spanning Tree problem. This connection allows us to show that the Hypergraph Spanning Tree problem in $k$-uniform $2$-regular hypergraphs is NP-complete for any $k \ge 4$, even when the incidence graph of the hypergraph is planar.

feature-construction
graph-theory
computational-complexity
rather-interesting
explanation
to-write-about
We characterize the computational complexity of TRVB with any combination of the following additional constraints: $G$ must be planar, $G$ must be a simple graph, the degree of every breakable vertex must belong to an allowed list $B$, and the degree of every unbreakable vertex must belong to an allowed list $U$. The two results which we expect to be most generally applicable are that (1) TRVB is polynomially solvable when breakable vertices are restricted to have degree at most $3$; and (2) for any $k \ge 4$, TRVB is NP-complete when the given multigraph is restricted to be planar and to consist entirely of degree-$k$ breakable vertices. To demonstrate the use of TRVB, we give a simple proof of the known result that Hamiltonicity in max-degree-$3$ square grid graphs is NP-hard.

We also demonstrate a connection between TRVB and the Hypergraph Spanning Tree problem. This connection allows us to show that the Hypergraph Spanning Tree problem in $k$-uniform $2$-regular hypergraphs is NP-complete for any $k \ge 4$, even when the incidence graph of the hypergraph is planar.

december 2018 by Vaguery

[1803.09473] code2vec: Learning Distributed Representations of Code

december 2018 by Vaguery

We present a neural model for representing snippets of code as continuous distributed vectors ("code embeddings"). The main idea is to represent a code snippet as a single fixed-length code vector, which can be used to predict semantic properties of the snippet. This is performed by decomposing code to a collection of paths in its abstract syntax tree, and learning the atomic representation of each path simultaneously with learning how to aggregate a set of them. We demonstrate the effectiveness of our approach by using it to predict a method's name from the vector representation of its body. We evaluate our approach by training a model on a dataset of 14M methods. We show that code vectors trained on this dataset can predict method names from files that were completely unobserved during training. Furthermore, we show that our model learns useful method name vectors that capture semantic similarities, combinations, and analogies. Comparing previous techniques over the same data set, our approach obtains a relative improvement of over 75%, being the first to successfully predict method names based on a large, cross-project, corpus. Our trained model, visualizations and vector similarities are available as an interactive online demo at this http URL. The code, data, and trained models are available at this https URL.

representation
genetic-programming
(it-ain't)
deep-learning
neural-networks
feature-construction
to-write-about
discrete-and-continuous-sittin-in-a-tree
december 2018 by Vaguery

[1812.01717] Towards Accurate Generative Models of Video: A New Metric & Challenges

december 2018 by Vaguery

Recent advances in deep generative models have lead to remarkable progress in synthesizing high quality images. Following their successful application in image processing and representation learning, an important next step is to consider videos. Learning generative models of video is a much harder task, requiring a model to capture the temporal dynamics of a scene, in addition to the visual presentation of objects. Although recent attempts at formulating generative models of video have had some success, current progress is hampered by (1) the lack of qualitative metrics that consider visual quality, temporal coherence, and diversity of samples, and (2) the wide gap between purely synthetic video datasets and challenging real-world datasets in terms of complexity. To this extent we propose Fréchet Video Distance (FVD), a new metric for generative models of video based on FID, and StarCraft 2 Videos (SCV), a collection of progressively harder datasets that challenge the capabilities of the current iteration of generative models for video. We conduct a large-scale human study, which confirms that FVD correlates well with qualitative human judgment of generated videos, and provide initial benchmark results on SCV.

metrics
Frechet-distance
generative-models
representation
rather-interesting
video
feature-construction
to-write-about
december 2018 by Vaguery

Fréchet distance - Wikipedia

november 2018 by Vaguery

In mathematics, the Fréchet distance is a measure of similarity between curves that takes into account the location and ordering of the points along the curves. It is named after Maurice Fréchet.

measurement
metrics
data-analysis
feature-construction
distance
computational-geometry
to-consider
ReQ
november 2018 by Vaguery

Tanya Khovanova's Math Blog » Blog Archive » Shapes of Symbols in Latin Squares

november 2018 by Vaguery

John likes finding interesting ways to remember which shape is which. You can find his and Alex’s suggestions in the paper which Alex submitted to the arxiv.

Oops! While I was writing this essay, arxiv rejected the paper.

latin-squares
combinatorics
constraint-satisfaction
feature-construction
rather-interesting
dammit
Oops! While I was writing this essay, arxiv rejected the paper.

november 2018 by Vaguery

Ecological theory provides insights about evolutionary computation [PeerJ Preprints]

november 2018 by Vaguery

Evolutionary algorithms often incorporate ecological concepts to help maintain diverse populations and drive continued innovation. However, while there is strong evidence for the value of ecological dynamics, a lack of overarching theoretical framework renders the precise mechanisms behind these results unclear. These gaps in our understanding make it challenging to predict which approaches will be most appropriate for a given problem. Biologists have been developing ecological theory for decades, but the resulting body of work has yet to be translated into an evolutionary computation context. This paper lays the groundwork for such a translation by applying ecological theory to three different selection mechanisms in evolutionary computation: fitness sharing, lexicase selection, and Eco-EA. First, we use ecological ideas to establish a framework that clarifies how these selection schemes are alike and how they differ. We then build upon this framework by using metrics from ecology to gather empirical data about the underlying differences in the population dynamics that these approaches produce. Specifically, we measure interaction networks and phylogenetic diversity within the population to explore long-term stable coexistence. Notably, we find that selection methods affect phylogenetic diversity differently than phenotypic diversity. These results can inform parameter selection, choice of selection scheme, and the development of new selection schemes.

evolutionary-algorithms
selection
looking-to-see
rather-interesting
hey-I-know-these-folks
artificial-life
feature-construction
community-formation
november 2018 by Vaguery

[1810.10577] Cops and Robbers on Toroidal Chess Graphs

november 2018 by Vaguery

We investigate multiple variants of the game Cops and Robbers. Playing it on an n×n toroidal chess graph, the game is varied by defining moves for cops and robbers differently, always mimicking moves of certain chess pieces. In these cases, the cop number is completely determined.

graph-theory
games
rather-interesting
mathematical-recreations
feature-construction
to-write-about
to-simulate
nudge-targets
consider:classification
november 2018 by Vaguery

[1302.1883] Mesh patterns with superfluous mesh

november 2018 by Vaguery

Mesh patterns are a generalization of classical permutation patterns that encompass classical, bivincular, Bruhat-restricted patterns, and some barred patterns. In this paper, we describe all mesh patterns whose avoidance is coincident with classical avoidance, in a sense declaring that the additional data of a mesh was unnecessary for these patterns. We also describe the permutations having the fewest superfluous meshes, and the permutations having the most, enumerating the superfluous meshes in each case.

permutations
combinatorics
representation
to-write-about
mathematical-recreations
pattern-discovery
feature-construction
november 2018 by Vaguery

[1608.06931] Prolific permutations and permuted packings: downsets containing many large patterns

november 2018 by Vaguery

A permutation of n letters is k-prolific if each (n-k)-subset of the letters in its one-line notation forms a unique pattern. We present a complete characterization of k-prolific permutations for each k, proving that k-prolific permutations of m letters exist for every m \ge k^2/2+2k+1, and that none exist of smaller size. Key to these results is a natural bijection between k-prolific permutations and certain "permuted" packings of diamonds.

combinatorics
permutations
representation
tiling
to-understand
enumeration
optimization
packing
feature-construction
november 2018 by Vaguery

[1704.05494] The pinnacle set of a permutation

november 2018 by Vaguery

Peak sets of a permutation record the indices of its peaks. These sets have been studied in a variety of contexts, including recent work by Billey, Burdzy, and Sagan, which enumerated permutations with prescribed peak sets. In this article, we look at a natural analogue of the peak set of a permutation, instead recording the values of the peaks. We define the "pinnacle set" of a permutation w to be the set {w(i) : i is a peak of w}. Although peak sets and pinnacle sets mark the same phenomenon, these objects differ in notable ways. In the work below, we characterize admissible pinnacle sets and study various enumerative questions related to these objects.

combinatorics
permutations
representation
to-understand
feature-construction
to-write-about
november 2018 by Vaguery

Copy this bookmark: