Vaguery : to-write-about   1710

 « earlier
Emergent Tool Use from Multi-Agent Interaction
We’ve observed agents discovering progressively more complex tool use while playing a simple game of hide-and-seek. Through training in our new simulated hide-and-seek environment, agents build a series of six distinct strategies and counterstrategies, some of which we did not know our environment supported. The self-supervised emergent complexity in this simple environment further suggests that multi-agent co-adaptation may one day produce extremely complex and intelligent behavior.
agent-based  artificial-life  machine-learning  collective-behavior  looking-to-see  rather-interesting  to-write-about  to-simulate  consider:a-sufficiently-complex-environment
3 days ago by Vaguery
Hugging Face GPT With Clojure - Squid's Blog
You can now interop with ANY python library.

I know. It’s overwhelming. It took a bit for me to come to grips with it too.

Let’s take an example of something that I’ve always wanted to do and have struggled with mightly finding a way to do it in Clojure:
I want to use the latest cutting edge GPT2 code out there to generate text.

Right now, that library is Hugging Face Transformers.

Get ready. We will wrap that sweet hugging face code in Clojure parens!
machine-learning  Clojure  interop  natural-language-processing  rather-interesting  library  to-understand  to-follow-along  to-write-about  consider:scraping-for-data
3 days ago by Vaguery
The King vs. Pawn Game of UI Design – A List Apart
If you want to improve your UI design skills, have you tried looking at chess? I know it sounds contrived, but hear me out. I’m going to take a concept from chess and use it to build a toolkit of UI design strategies. By the end, we’ll have covered color, typography, lighting and shadows, and more.
graphic-design  the-mangle-in-practice  pedagogy  rather-good  isolation-of-concepts  to-write-about  consider:testing  consider:unit-tests-as-lessons  consider:Oulipo
4 days ago by Vaguery
Regularization Improves the Robustness of Learned Sequence-to-Expression Models | bioRxiv
Understanding of the gene regulatory activity of enhancers is a major problem in regulatory biology. The nascent field of sequence-to-expression modelling seeks to create quantitative models of gene expression based on regulatory DNA (cis) and cellular environmental (trans) contexts. All quantitative models are defined partially by numerical parameters, and it is common to fit these parameters to data provided by existing experimental results. However, the relative paucity of experimental data appropriate for this task, and lacunae in our knowledge of all components of the systems, results in problems often being under-specified, which in turn may lead to a situation where wildly different model parameterizations perform similarly well on training data. It may also lead to models being fit to the idiosyncrasies of the training data, without representing the more general process (overfitting).

In other contexts where parameter-fitting is performed, it is common to apply regularization to reduce overfitting. We systematically evaluated the efficacy of three types of regularization in improving the generalizability of trained sequence-to-expression models. The evaluation was performed in two types of cross-validation experiments: one training on D. melanogaster data and predicting on orthologous enhancers from related species, and the other cross-validating between four D. melanogaster neurogenic ectoderm enhancers, which are thought to be under control of the same transcription factors. We show that training with a combination of noise-injection, L1, and L2 regularization can drastically reduce overfitting and improve the generalizability of learned sequence-to-expression models. These results suggest that it may be possible to mitigate the tendency of sequence-to-expression models to overfit available data, thus improving predictive power and potentially resulting in models that provide better insight into underlying biological processes.
bioinformatics  systems-biology  nonlinear-dynamics  machine-learning  regularization  statistics  numerical-methods  heuristics  to-write-about  to-simulate  consider:symbolic-regression  consider:robustness
4 days ago by Vaguery
What Proof Is Best? |
A great illustration of this “Let a hundred proofs bloom” point of view is provided by an article by Stan Wagon called “Fourteen Proofs of a Result About Tiling a Rectangle”. Here’s the result his title refers to (a puzzle posed and solved by Nicolaas de Bruijn): Whenever a rectangle can be cut up into smaller rectangles each of which has at least one integer side, then the big rectangle has at least one integer side too. (Here “at least one integer side” is tantamount to “at least two integer sides”, since the opposite sides of a rectangle always have the same length.)
mathematics  philosophy  solution-spaces  diversity  proof  to-write-about  to-simulate  consider:surprise
4 days ago by Vaguery
[1710.04554] Lattice point visibility on generalized lines of sight
For a fixed b∈ℕ={1,2,3,…} we say that a point (r,s) in the integer lattice ℤ×ℤ is b-visible from the origin if it lies on the graph of a power function f(x)=axb with a∈ℚ and no other integer lattice point lies on this curve (i.e., line of sight) between (0,0) and (r,s). We prove that the proportion of b-visible integer lattice points is given by 1/ζ(b+1), where ζ(s) denotes the Riemann zeta function. We also show that even though the proportion of b-visible lattice points approaches 1 as b approaches infinity, there exist arbitrarily large rectangular arrays of b-invisible lattice points for any fixed b. This work specialized to b=1 recovers original results from the classical lattice point visibility setting where the lines of sight are given by linear functions with rational slope through the origin.
number-theory  have-considered  rather-interesting  to-write-about  to-simulate  consider:visualization  consider:agents-who-see-this-way
6 days ago by Vaguery
[1807.06414] Combining a Context Aware Neural Network with a Denoising Autoencoder for Measuring String Similarities
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
6 days ago by Vaguery
[1812.08434] Graph Neural Networks: A Review of Methods and Applications
Lots of learning tasks require dealing with graph data which contains rich relation information among elements. Modeling physics system, learning molecular fingerprints, predicting protein interface, and classifying diseases require a model to learn from graph inputs. In other domains such as learning from non-structural data like texts and images, reasoning on extracted structures, like the dependency tree of sentences and the scene graph of images, is an important research topic which also needs graph reasoning models. Graph neural networks (GNNs) are connectionist models that capture the dependence of graphs via message passing between the nodes of graphs. Unlike standard neural networks, graph neural networks retain a state that can represent information from its neighborhood with arbitrary depth. Although the primitive GNNs have been found difficult to train for a fixed point, recent advances in network architectures, optimization techniques, and parallel computation have enabled successful learning with them. In recent years, systems based on variants of graph neural networks such as graph convolutional network (GCN), graph attention network (GAT), gated graph neural network (GGNN) have demonstrated ground-breaking performance on many tasks mentioned above. In this survey, we provide a detailed review over existing graph neural network models, systematically categorize the applications, and propose four open problems for future research.
machine-learning  representation  review  rather-interesting  to-write-about  to-simulate  consider:genetic-programming  consider:functional-transformations
6 days ago by Vaguery
[1809.02836] Context-Free Transductions with Neural Stacks
This paper analyzes the behavior of stack-augmented recurrent neural network (RNN) models. Due to the architectural similarity between stack RNNs and pushdown transducers, we train stack RNN models on a number of tasks, including string reversal, context-free language modelling, and cumulative XOR evaluation. Examining the behavior of our networks, we show that stack-augmented RNNs can discover intuitive stack-based strategies for solving our tasks. However, stack RNNs are more difficult to train than classical architectures such as LSTMs. Rather than employ stack-based strategies, more complex networks often find approximate solutions by using the stack as unstructured memory.
neural-networks  artificial-life  representation  time-series  automata  to-write-about  to-simulate  unconventional-computing
6 days ago by Vaguery
[1906.01615] Sequential Neural Networks as Automata
This work attempts to explain the types of computation that neural networks can perform by relating them to automata. We first define what it means for a real-time network with bounded precision to accept a language. A measure of network memory follows from this definition. We then characterize the classes of languages acceptable by various recurrent networks, attention, and convolutional networks. We find that LSTMs function like counter machines and relate convolutional networks to the subregular hierarchy. Overall, this work attempts to increase our understanding and ability to interpret neural networks through the lens of theory. These theoretical insights help explain neural computation, as well as the relationship between neural networks and natural language grammar.
neural-networks  rather-interesting  update-dynamics  representation  via:cshalizi  to-read  to-write-about  to-simulate  automata  unconventional-computation  but-is-it-really?
6 days ago by Vaguery
Puzzle 864. 10958, the only hole...
Brazilian mathematician Inder J. Taneja has found (Jan 2014) a way to render every number from 1 to 11,111 by starting with either of these ordered strings.

1234567869 (increasing 1->9) and 987654321 (decreasing 9->1

applying any of the following:

a) arithmetical operations permitted: addition, subtraction, multiplication, division, and exponentiation.
b) string operation permitted: concatenation.
c) auxiliary symbols permitted: brackets "(" and ")".
puzzles  mathematical-recreations  arithmetic  constraint-satisfaction  to-write-about  nudge-targets  consider:looking-to-see  to-simulate  consider:generalizations
8 days ago by Vaguery
Robustness of the two-sample t-test
It is fairly well known that the t-test is robust to departures from a normal distribution, as long as the actual distribution is symmetric. That is, the test works more or less as advertised as long as the distribution is symmetric like a normal distribution, but it may not work as expected if the distribution is asymmetric.

This post will explore the robustness of the t-test via simulation. How far can you be from a normal distribution and still do OK? Can you have any distribution as long as it’s symmetric? Does a little asymmetry ruin everything? If something does go wrong, how does it go wrong?
statistics  looking-to-see  rather-interesting  algorithms  robustness  to-do  to-write-about  consider:animation
10 days ago by Vaguery
Running Cargo - Futility Closet
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
10 days ago by Vaguery
[PDF] Extended circularity: a new puzzle for extended cognition | Semantic Scholar
Mainstream epistemology has typically taken for granted a traditional picture of the metaphysics of mind, according to which cognitive processes (e.g. memory storage and retrieval) play out entirely within the bounds of the skull and skin. But this simple ‘intracranial’ picture is falling in- creasingly out of step with contemporary thinking in the philosophy of mind and cognitive science. Likewise, though, proponents of active exter- nalist approaches to the mind—e.g. the hypothesis of extended cognitition (HEC)—have proceeded by and large without asking what epistemological ramifications should arise once cognition is understood as criss-crossing the bounds of brain and world. This paper aims to motivate a puzzle that arises only once these two strands of thinking are brought in contact with one another. In particular, we want to first highlight a kind of con- dition of epistemological adequacy that should be accepted by proponents of extended cognition; once this condition is motivated, the remainder of the paper demonstrates how attempts to satisfy this condition seem to inevitably devolve into a novel kind of epistemic circularity. At the end of the day, proponents of extended cognition have a novel epistemological puzzle on their hands.
the-mangle-in-practice  psychology  cognition  individuation  philosophy-of-mind  to-write-about  consider:not-worrying-about-it
10 days ago by Vaguery
[1305.1958] The Dynamically Extended Mind -- A Minimal Modeling Case Study
The extended mind hypothesis has stimulated much interest in cognitive science. However, its core claim, i.e. that the process of cognition can extend beyond the brain via the body and into the environment, has been heavily criticized. A prominent critique of this claim holds that when some part of the world is coupled to a cognitive system this does not necessarily entail that the part is also constitutive of that cognitive system. This critique is known as the "coupling-constitution fallacy". In this paper we respond to this reductionist challenge by using an evolutionary robotics approach to create a minimal model of two acoustically coupled agents. We demonstrate how the interaction process as a whole has properties that cannot be reduced to the contributions of the isolated agents. We also show that the neural dynamics of the coupled agents has formal properties that are inherently impossible for those neural networks in isolation. By keeping the complexity of the model to an absolute minimum, we are able to illustrate how the coupling-constitution fallacy is in fact based on an inadequate understanding of the constitutive role of nonlinear interactions in dynamical systems theory.
the-mangle-in-practice  rather-interesting  philosophy  philosophy-of-science  to-write-about  to-wander-its-citations
10 days ago by Vaguery
The Stanford Literary Lab’s Narrative | Public Books
Experiment is presented here not just as a test of reliable knowledge but as a style of intellectual growth: “By frustrating our expectations, failed experiments ‘estrange’ our natural habits of thought, offering a chance to transcend them.” At moments, the point of experiment seems to become entirely aesthetic. In the book’s introduction, Moretti admits that he set out to write “a scientific essay, composed like a Mahler symphony: discordant registers that barely manage to coexist; a forward movement endlessly diverted; the easiest of melodies, followed by leaps into the unknown.”
This account of the book’s aesthetic achievement is candid, immodest, and accurate. The essays within are unified by a deliberately wandering structure, which keeps its distance both from scientists’ predictable sequences (methods → results → conclusions), and from the thesis-driven template that prevails in the humanities (counter-intuitive claim → evidence → I was right after all). Instead, these essays become stories of progressive disorientation, written in the first-person plural, and arriving at theses that were only dimly foreshadowed.
digital-humanities  literary-criticism  rather-interesting  this-quote  to-write-about  consider:the-creative-system
10 days ago by Vaguery
DR. HERBERT H. TSANG - http://www.herberttsang.org
RNA design algorithm takes an RNA secondary structure description as input and then try to identify an RNA strand that folds into this function-specific target structure. With new advances in biotechnology and synthetic biology, a reliable RNA design algorithm can be crucial steps to create new biochemical components. Our lab is interested in employing various computational intelligence techniques to propose the new paradigm to help with the RNA design problem. Recently, we have designed an algorithm SIMARD, which is based on the simulated annealing paradigm.
structural-biology  polymer-folding  biochemistry  biophysics  simulation  metaheuristics  energy-landscapes  rather-interesting  to-write-about  to-simulate  to-visualize
14 days ago by Vaguery
Short How-To guides — GROMACS 2019 documentation
A number of short guides are presented here to help users getting started with simulations. More detailed tutorials are available for example at the http://www.mdtutorials.com/.
structural-biology  simulation  software  open-source  rather-interesting  to-simulate  to-write-about  consider:looking-to-see
14 days ago by Vaguery
[1902.07277] A systematic classification of knotoids on the plane and on the sphere
In this paper we generate and systematically classify all prime planar knotoids with up to 5 crossings. We also extend the existing list of knotoids in S2 and add all knotoids with 6 crossings.
knot-theory  combinatorics  enumeration  rather-interesting  stamp-collecting  to-understand  to-write-about  to-simulate  consider:classification  consider:representation
14 days ago by Vaguery
[1803.07114] Slipknotting in Random Diagrams
The presence of slipknots in configurations of proteins and DNA has been shown to affect their functionality, or alter it entirely. Historically, polymers are modeled as polygonal chains in space. As an alternative to space curves, we provide a framework for working with subknots inside of knot diagrams via knotoid diagrams. We prove using a pattern theorem for knot diagrams that not only are almost all knot diagrams slipknotted, almost all unknot diagrams are slipknotted. This proves in the random diagram model a conjecture yet unproven in random space curve models. We also discuss conjectures on the enumeration of knotoid diagrams.
knot-theory  combinatorics  sampling  random-walks  structural-biology  rather-interesting  theoretical-biology  to-simulate  to-write-about  consider:representation
14 days ago by Vaguery
[1810.07970] Inglenook Shunting Puzzles
An inglenook puzzle is a classic shunting (switching) puzzle often found on model railway layouts. A collection of wagons sits in a fan of sidings with a limited length headshunt (lead track). The aim of the puzzle is to rearrange the wagons into a desired order (often a randomly chosen order). This article answers the question: When can you be sure this can always be done? The problem of finding a solution in a minimum number of moves is also addressed.
puzzles  mathematical-recreations  combinatorics  rather-interesting  to-write-about  to-simulate  consider:genetic-programming  consider:data-structures
14 days ago by Vaguery
[1803.09607] Murder at the Asylum
I describe a puzzle I wrote for the 2018 MIT Mystery Hunt which introduced new types of people in logic puzzles. I discuss the puzzle itself, the solution, and the mathematics behind it.
puzzles  logic  mathematical-recreations  rather-good  constraint-satisfaction  to-write-about  to-simulate  consider:sampling
14 days ago by Vaguery
[1804.03311] A Markov Chain Sampler for Plane Curves
A plane curve is a knot diagram in which each crossing is replaced by a 4-valent vertex, and so are dual to a subset of planar quadrangulations. The aim of this paper is to introduce a new tool for sampling diagrams via sampling of plane curves. At present the most efficient method for sampling diagrams is rejection sampling, however that method is inefficient at even modest sizes. We introduce Markov chains that sample from the space of plane curves using local moves based on Reidemeister moves. By then mapping vertices on those curves to crossings we produce random knot diagrams. Combining this chain with flat histogram methods we achieve an efficient sampler of plane curves and knot diagrams. By analysing data from this chain we are able to estimate the number of knot diagrams of a given size and also compute knotting probabilities and so investigate their asymptotic behaviour.
knot-theory  graph-theory  rather-interesting  combinatorics  enumeration  sampling  to-simulate  to-understand  to-write-about
14 days ago by Vaguery
[math/0509478] Simultaneous Diagonal Flips in Plane Triangulations
Simultaneous diagonal flips in plane triangulations are investigated. It is proved that every n-vertex triangulation with at least six vertices has a simultaneous flip into a 4-connected triangulation, and that it can be computed in O(n) time. It follows that every triangulation has a simultaneous flip into a Hamiltonian triangulation. This result is used to prove that for any two n-vertex triangulations, there exists a sequence of O(logn) simultaneous flips to transform one into the other. The total number of edges flipped in this sequence is O(n). The maximum size of a simultaneous flip is then studied. It is proved that every triangulation has a simultaneous flip of at least 1/3(n−2) edges. On the other hand, every simultaneous flip has at most n−2 edges, and there exist triangulations with a maximum simultaneous flip of 6/7(n−2) edges.
graph-theory  combinatorics  rewriting-systems  rather-interesting  proof  to-simulate  to-write-about  consider:constraint-satisfaction
15 days ago by Vaguery
[2001.09212] PCGRL: Procedural Content Generation via Reinforcement Learning
We investigate how reinforcement learning can be used to train level-designing agents. This represents a new approach to procedural content generation in games, where level design is framed as a game, and the content generator itself is learned. By seeing the design problem as a sequential task, we can use reinforcement learning to learn how to take the next action so that the expected final level quality is maximized. This approach can be used when few or no examples exist to train from, and the trained generator is very fast. We investigate three different ways of transforming two-dimensional level design problems into Markov decision processes and apply these to three game environments.
machine-learning  transfer-learning  generative-models  content-generation  rather-interesting  to-simulate  to-write-about  consider:feature-discovery
17 days ago by Vaguery
[1808.01984] Time-Dependent Shortest Path Queries Among Growing Discs
The determination of time-dependent collision-free shortest paths has received a fair amount of attention. Here, we study the problem of computing a time-dependent shortest path among growing discs which has been previously studied for the instance where the departure times are fixed. We address a more general setting: For two given points s and d, we wish to determine the function (t) which is the minimum arrival time at d for any departure time t at s. We present a (1+ϵ)-approximation algorithm for computing (t). As part of preprocessing, we execute O(1ϵlog(rc)) shortest path computations for fixed departure times, where r is the maximum speed of the robot and c is the minimum growth rate of the discs. For any query departure time t≥0 from s, we can approximate the minimum arrival time at the destination in O(log(1ϵ)+loglog(rc)) time, within a factor of 1+ϵ of optimal. Since we treat the shortest path computations as black-box functions, for different settings of growing discs, we can plug-in different shortest path algorithms. Thus, the exact time complexity of our algorithm is determined by the running time of the shortest path computations.
computational-complexity  computational-geometry  planning  constraint-satisfaction  optimization  rather-interesting  to-understand  algorithms  to-simulate  to-write-about  consider:robustness
17 days ago by Vaguery
[2001.11709] Gaussian Random Embeddings of Multigraphs
This paper generalizes the Gaussian random walk and Gaussian random polygon models for linear and ring polymers to polymer topologies specified by an arbitrary multigraph $G$. Probability distributions of monomer positions and edge displacements are given explicitly and the spectrum of the graph Laplacian of $G$ is shown to predict the geometry of the configurations. This provides a new perspective on the James-Guth-Flory theory of phantom elastic networks. The model is based on linear algebra motivated by ideas from homology and cohomology theory. It provides a robust theoretical foundation for more detailed models of topological polymers.
structural-biology  probability-theory  random-walks  rather-interesting  to-simulate  constraint-satisfaction  polymers  to-write-about
17 days ago by Vaguery
[1809.09979] Approximability of Covering Cells with Line Segments
In COCOA 2015, Korman et al. studied the following geometric covering problem: given a set S of n line segments in the plane, find a minimum number of line segments such that every cell in the arrangement of the line segments is covered. Here, a line segment s covers a cell f if s is incident to f. The problem was shown to be NP-hard, even if the line segments in S are axis-parallel, and it remains NP-hard when the goal is cover the "rectangular" cells (i.e., cells that are defined by exactly four axis-parallel line segments).
In this paper, we consider the approximability of the problem. We first give a PTAS for the problem when the line segments in S are in any orientation, but we can only select the covering line segments from one orientation. Then, we show that when the goal is to cover the rectangular cells using line segments from both horizontal and vertical line segments, then the problem is APX-hard. We also consider the parameterized complexity of the problem and prove that the problem is FPT when parameterized by the size of an optimal solution. Our FPT algorithm works when the line segments in S have two orientations and the goal is to cover all cells, complementing that of Korman et al. in which the goal is to cover the "rectangular" cells.
covering-problems  computational-complexity  computational-geometry  rather-interesting  optimization  to-simulate  to-write-about
22 days ago by Vaguery
[1809.10737] Plane and Planarity Thresholds for Random Geometric Graphs
A random geometric graph, G(n,r), is formed by choosing n points independently and uniformly at random in a unit square; two points are connected by a straight-line edge if they are at Euclidean distance at most r. For a given constant k, we show that n−k2k−2 is a distance threshold function for G(n,r) to have a connected subgraph on k points. Based on this, we show that n−2/3 is a distance threshold for G(n,r) to be plane, and n−5/8 is a distance threshold to be planar. We also investigate distance thresholds for G(n,r) to have a non-crossing edge, a clique of a given size, and an independent set of a given size.
graph-theory  graph-layout  sampling  probability-theory  looking-to-see  to-write-about  to-simulate  consider:planarity  random-graphs  geometric-graphs
22 days ago by Vaguery
[1810.09232] On the Minimum Consistent Subset Problem
Let P be a set of n colored points in the plane. Introduced by Hart (1968), a consistent subset of P, is a set S⊆P such that for every point p in P∖S, the closest point of p in S has the same color as p. The consistent subset problem is to find a consistent subset of P with minimum cardinality. This problem is known to be NP-complete even for two-colored point sets. Since the initial presentation of this problem, aside from the hardness results, there has not been a significant progress from the algorithmic point of view. In this paper we present the following algorithmic results:
1. The first subexponential-time algorithm for the consistent subset problem.
2. An O(nlogn)-time algorithm that finds a consistent subset of size two in two-colored point sets (if such a subset exists). Towards our proof of this running time we present a deterministic O(nlogn)-time algorithm for computing a variant of the compact Voronoi diagram; this improves the previously claimed expected running time.
3. An O(nlog2n)-time algorithm that finds a minimum consistent subset in two-colored point sets where one color class contains exactly one point; this improves the previous best known O(n2) running time which is due to Wilfong (SoCG 1991).
4. An O(n)-time algorithm for the consistent subset problem on collinear points; this improves the previous best known O(n2) running time.
5. A non-trivial O(n6)-time dynamic programming algorithm for the consistent subset problem on points arranged on two parallel lines.
To obtain these results, we combine tools from planar separators, additively-weighted Voronoi diagrams with respect to convex distance functions, point location in farthest-point Voronoi diagrams, range trees, paraboloid lifting, minimum covering of a circle with arcs, and several geometric transformations.
computational-complexity  computational-geometry  algorithms  combinatorics  plane-geometry  to-simulate  to-write-about  consider:movement  consider:heuristics
22 days ago by Vaguery
[1812.05125] On Graphs whose Eternal Vertex Cover Number and Vertex Cover Number Coincide
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
22 days ago by Vaguery
[1905.00790] Minimum Ply Covering of Points with Disks and Squares
Following the seminal work of Erlebach and van Leeuwen in SODA 2008, we introduce the minimum ply covering problem. Given a set P of points and a set S of geometric objects, both in the plane, our goal is to find a subset S′ of S that covers all points of P while minimizing the maximum number of objects covering any point in the plane (not only points of P). For objects that are unit squares and unit disks, this problem is NP-hard and cannot be approximated by a ratio smaller than 2. We present 2-approximation algorithms for this problem with respect to unit squares and unit disks. Our algorithms run in polynomial time when the optimum objective value is bounded by a constant.
Motivated by channel-assignment in wireless networks, we consider a variant of the problem where the selected unit disks must be 3-colorable, i.e., colored by three colors such that all disks of the same color are pairwise disjoint. We present a polynomial-time algorithm that achieves a 2-approximate solution, i.e., a solution that is 6-colorable.
We also study the weighted version of the problem in dimension one, where P and S are points and weighted intervals on a line, respectively. We present an algorithm that solves this problem in O(n+m+M)-time where n is the number of points, m is the number of intervals, and M is the number of pairs of overlapping intervals. This repairs a solution claimed by Nandy, Pandit, and Roy in CCCG 2017.
computational-geometry  operations-research  rather-interesting  optimization  constraint-satisfaction  to-write-about  to-simulate  consider:looking-to-see  consider:performance-measures
22 days ago by Vaguery
[1905.00791] Flip Distance to some Plane Configurations
We study an old geometric optimization problem in the plane. Given a perfect matching M on a set of n points in the plane, we can transform it to a non-crossing perfect matching by a finite sequence of flip operations. The flip operation removes two crossing edges from M and adds two non-crossing edges. Let f(M) and F(M) denote the minimum and maximum lengths of a flip sequence on M, respectively. It has been proved by Bonnet and Miltzow (2016) that f(M)=O(n2) and by van Leeuwen and Schoone (1980) that F(M)=O(n3). We prove that f(M)=O(nΔ) where Δ is the spread of the point set, which is defined as the ratio between the longest and the shortest pairwise distances. This improves the previous bound if the point set has sublinear spread. For a matching M on n points in convex position we prove that f(M)=n/2−1 and F(M)=(n/22); these bounds are tight.
Any bound on F(⋅) carries over to the bichromatic setting, while this is not necessarily true for f(⋅). Let M′ be a bichromatic matching. The best known upper bound for f(M′) is the same as for F(M′), which is essentially O(n3). We prove that f(M′)≤n−2 for points in convex position, and f(M′)=O(n2) for semi-collinear points.
The flip operation can also be defined on spanning trees. For a spanning tree T on a convex point set we show that f(T)=O(nlogn).
computational-geometry  graph-layout  graph-theory  heuristics  rather-interesting  to-simulate  to-write-about  consider:polygon-sampling
22 days ago by Vaguery
[1905.07124] Variations of largest rectangle recognition amidst a bichromatic point set
Classical separability problem involving multi-color point sets is an important area of study in computational geometry. In this paper, we study different separability problems for bichromatic point set P=P_r\cup P_b on a plane, where Pr and Pb represent the set of n red points and m blue points respectively, and the objective is to compute a monochromatic object of the desired type and of maximum size. We propose in-place algorithms for computing (i) an arbitrarily oriented monochromatic rectangle of maximum size in R^2, (ii) an axis-parallel monochromatic cuboid of maximum size in R^3. The time complexities of the algorithms for problems (i) and (ii) are O(m(m+n)(m\sqrt{n}+m\log m+n \log n)) and O(m^3\sqrt{n}+m^2n\log n), respectively. As a prerequisite, we propose an in-place construction of the classic data structure the k-d tree, which was originally invented by J. L. Bentley in 1975. Our in-place variant of the k-d tree for a set of n points in R^k supports both orthogonal range reporting and counting query using O(1) extra workspace, and these query time complexities are the same as the classical complexities, i.e., O(n^{1-1/k}+\mu) and O(n^{1-1/k}), respectively, where \mu is the output size of the reporting query. The construction time of this data structure is O(n\log n). Both the construction and query algorithms are non-recursive in nature that do not need O(\log n) size recursion stack compared to the previously known construction algorithm for in-place k-d tree and query in it. We believe that this result is of independent interest. We also propose an algorithm for the problem of computing an arbitrarily oriented rectangle of maximum weight among a point set P=P_r \cup P_b, where each point in P_b (resp. P_r) is associated with a negative (resp. positive) real-valued weight that runs in O(m^2(n+m)\log(n+m)) time using O(n) extra space.
computational-complexity  computational-geometry  optimization  sorting  algorithms  heuristics  to-simulate  to-write-about  consider:variants
22 days ago by Vaguery
[1906.11948] Packing Boundary-Anchored Rectangles and Squares
Consider a set P of n points on the boundary of an axis-aligned square Q. We study the boundary-anchored packing problem on P in which the goal is to find a set of interior-disjoint axis-aligned rectangles in Q such that each rectangle is anchored (has a corner at some point in P), each point in P is used to anchor at most one rectangle, and the total area of the rectangles is maximized. Here, a rectangle is anchored at a point p in P if one of its corners coincides with p. In this paper, we show how to solve this problem in time linear in n, provided that the points of P are given in sorted order along the boundary of Q. We also consider the problem for anchoring squares and give an O(n4)-time algorithm when the points in P lie on two opposite sides of Q.
packing  operations-research  computational-geometry  computational-complexity  algorithms  optimization  constraint-satisfaction  rather-interesting  to-write-about  to-simulate  consider:feature-discovery  consider:heuristics
22 days ago by Vaguery
[1907.01617] A Short Proof of the Toughness of Delaunay Triangulations
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
22 days ago by Vaguery
Constructing random polygons | Proceedings of the 9th ACM SIGITE conference on Information technology education
The construction of random polygons has been used in psychological research and for the testing of algorithms. With the increased popularity of client-side vector based graphics in the web browser such as seen in Flash and SVG, as well as the newly introduced <canvas> tag in HTML5.0, the use of random shapes for creation of scenes for animation and interactive art requires the construction of random polygons. A natural question, then, is how to generate random polygons in a way which is computationally efficient (particularly in a resource limited environment such as the web browser). This paper presents a random polygon algorithm (RPA) that generates polygons that are random and representative of the class of all n-gons in O(n2logn) time. Our algorithm differs from other approaches in that the vertices are generated randomly, the algorithm is inclusive (i.e. each polygon has a non-zero probability to be constructed), and it runs efficiently in polynomial time.
probability-theory  sampling  computational-geometry  algorithms  rather-interesting  to-write-about  to-simulate
23 days ago by Vaguery
CiteSeerX — RPG - Heuristics for the Generation of Random Polygons
We consider the problem of randomly generating simple and star-shaped polygons on a given set of points. This problem is of considerable importance in the practical evaluation of algorithms that operate on polygons, where it is necessary to check the correctness and to determine the actual CPU-consumption of an algorithm experimentally. Since no polynomial-time solution for the uniformly random generation of polygons is known, we present and analyze several heuristics. All heuristics described in this paper have been implemented and are part of our RandomPolygonGenerator, RPG. We have tested all heuristics, and report experimental results on their CPU-consumption, their quality, and their characteristics. RPG is publically available via http://www.cosy.sbg.ac.at/~held/projects/rpg/rpg.html. 1 Introduction In this paper 1 we deal with the random generation of simple polygons on a given set of points: Ideally, given a set S = fs 1 ; : : : ; s n g of n points, we would like to generat...
probability-theory  computational-geometry  sampling  rather-interesting  performance-measure  to-simulate  to-write-about
23 days ago by Vaguery
[1706.10193] More Turán-Type Theorems for Triangles in Convex Point Sets
We study the following family of problems: Given a set of n points in convex position, what is the maximum number triangles one can create having these points as vertices while avoiding certain sets of forbidden configurations. As forbidden configurations we consider all 8 ways in which a pair of triangles in such a point set can interact. This leads to 256 extremal Turán-type questions. We give nearly tight (within a logn factor) bounds for 248 of these questions and show that the remaining 8 questions are all asymptotically equivalent to Stein's longstanding tripod packing problem.
combinatorics  enumeration  rather-interesting  plane-geometry  graph-theory  counting  to-simulate  to-write-about  related-to:triangle-hypergraphs
26 days ago by Vaguery
[1812.05163] Declination as a Metric to Detect Partisan Gerrymandering
We explore the Declination, a new metric intended to detect partisan gerrymandering. We consider instances in which each district has equal turnout, the maximum turnout to minimum turnout is bounded, and turnout is unrestricted. For each of these cases, we show exactly which vote-share, seat-share pairs (V,S) have an election outcome with Declination equal to 0. We also show how our analyses can be applied to finding vote-share, seat-share pairs that are possible for nonzero Declination.
Within our analyses, we show that Declination cannot detect all forms of packing and cracking, and we compare the Declination to the Efficiency Gap. We show that these two metrics can behave quite differently, and give explicit examples of that occurring.
statistics  politics  gerrymandering  cultural-engineering  rather-interesting  performance-measure  to-write-about  to-simulate
26 days ago by Vaguery
[1611.06135] Large Values of the Clustering Coefficient
A prominent parameter in the context of network analysis, originally proposed by Watts and Strogatz (Collective dynamics of `small-world' networks, Nature 393 (1998) 440-442), is the clustering coefficient of a graph G. It is defined as the arithmetic mean of the clustering coefficients of its vertices, where the clustering coefficient of a vertex u of G is the relative density m(G[NG(u)])/(dG(u)2) of its neighborhood if dG(u) is at least 2, and 0 otherwise. It is unknown which graphs maximize the clustering coefficient among all connected graphs of given order and size.
We determine the maximum clustering coefficients among all connected regular graphs of a given order, as well as among all connected subcubic graphs of a given order. In both cases, we characterize all extremal graphs. Furthermore, we determine the maximum increase of the clustering coefficient caused by adding a single edge.
graph-theory  network-theory  metrics  a-picture-would-be-useful-about-now  to-write-about  to-illustrate  FFS-make-a-picture
26 days ago by Vaguery
[1803.11511] Length segregation in mixtures of spherocylinders induced by imposed topological defects
We explore length segregation in binary mixtures of spherocylinders of lengths L1 and L2 with the same diameter D which are tangentially confined on a spherical surface of radius R. The orientation of spherocylinders is constrained along an externally imposed direction field on the sphere which is either along the longitude or the latitude lines of the sphere. In both situations, integer orientational defects at the poles are imposed. We show that these topological defects induce a complex segregation picture also depending on the length ratio factor γ=L2/L1 and the total packing fraction η of the spherocylinders. When the binary mixture is aligned along longitudinal lines of the sphere, shorter rods tend to accumulate at the topological defects of the polar caps whereas longer rods occupy central equatorial area of the spherical surface. In the reverse case of latitude ordering, a state can emerge where longer rods are predominantly both in the cap and in the equatorial areas and shorter rods are localized in between. As a reference situation, we consider a defect-free situation in the flat plane and do not find any length segregation there at similar γ and η, hence the segregation is purely induced by the imposed topological defects. It is also revealed that the shorter rods at γ=4 and η≥0.5 act as obstacles to the rotational relaxation of the longer rods when all orientational constraints are released.
granular-materials  mixing  self-organization  rather-interesting  physics!  simulation  looking-to-see  to-write-about  to-simulate  packing
27 days ago by Vaguery
[1803.09639] On the multipacking number of grid graphs
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
27 days ago by Vaguery
[1904.06108] The Dodecahedron as a Voronoi Cell and its (minor) importance for the Kepler conjecture
The regular dodecahedron has a 2% smaller volume than the rhombic dodecahedron which is the Voronoi cell of a fcc packing. From this point of view it seems possible that the dodecahedral aspect which is the core of the so-called dodecahedral conjecture, will play a major part for an elementary proof of the Kepler conjecture. In this paper we will show that the icosahedral configuration caused by dodecahedron leads to tetrahedra with significantly larger volume than the fcc fundamental parallelotope tessellation tetrahedra. Therefore on the basis of a tetrahedral based point of view for sphere packing densities we will demonstrate the minor importance of the dodecahedron as a Voronoi cell for the Kepler conjecture.
packing  solved-problems  rather-interesting  not-quite-solutions  optimization  to-write-about  to-simulate  a-picture-might-be-good
27 days ago by Vaguery
[1712.04922] Closing the gap for pseudo-polynomial strip packing
The set of 2-dimensional packing problems builds an important class of optimization problems and Strip Packing together with 2-dimensional Bin Packing and 2-dimensional Knapsack is one of the most famous of these problems. Given a set of rectangular axis parallel items and a strip with bounded width and infinite height the objective is to find a packing of the items into the strip which minimizes the packing height. We speak of pseudo-polynomial Strip Packing if we consider algorithms with pseudo-polynomial running time with respect to the width of the strip.
It is known that there is no pseudo-polynomial algorithm for Strip Packing with a ratio better than 5/4 unless P=NP. The best algorithm so far has a ratio of (4/3+ε). In this paper, we close this gap between inapproximability result and best known algorithm by presenting an algorithm with approximation ratio (5/4+ε) and thus categorize the problem accurately. The algorithm uses a structural result which states that each optimal solution can be transformed such that it has one of a polynomial number of different forms. The strength of this structural result is that it applies to other problem settings as well for example to Strip Packing with rotations (90 degrees) and Contiguous Moldable Task Scheduling. This fact enabled us to present algorithms with approximation ratio (5/4+ε) for these problems as well.
operations-research  optimization  strip-packing  packing  numerical-methods  mathematical-programming  algorithms  computational-complexity  horse-races  to-write-about  to-simulate  consider:genetic-programming  consider:performance-measures  consider:heuristics
27 days ago by Vaguery
[1802.10038] Improving OCR Accuracy on Early Printed Books by combining Pretraining, Voting, and Active Learning
We combine three methods which significantly improve the OCR accuracy of OCR models trained on early printed books: (1) The pretraining method utilizes the information stored in already existing models trained on a variety of typesets (mixed models) instead of starting the training from scratch. (2) Performing cross fold training on a single set of ground truth data (line images and their transcriptions) with a single OCR engine (OCRopus) produces a committee whose members then vote for the best outcome by also taking the top-N alternatives and their intrinsic confidence values into account. (3) Following the principle of maximal disagreement we select additional training lines which the voters disagree most on, expecting them to offer the highest information gain for a subsequent training (active learning). Evaluations on six early printed books yielded the following results: On average the combination of pretraining and voting improved the character accuracy by 46% when training five folds starting from the same mixed model. This number rose to 53% when using different models for pretraining, underlining the importance of diverse voters. Incorporating active learning improved the obtained results by another 16% on average (evaluated on three of the six books). Overall, the proposed methods lead to an average error rate of 2.5% when training on only 60 lines. Using a substantial ground truth pool of 1,000 lines brought the error rate down even further to less than 1% on average.
OCR  digital-humanities  digitization  text-processing  image-processing  machine-learning  data-cleaning  the-mangle-in-practice  modeling  rather-interesting  to-write-about  to-simulate  consider:stochastic-resonance
27 days ago by Vaguery
[1908.08273] Representing Graphs and Hypergraphs by Touching Polygons in 3D
Contact representations of graphs have a long history. Most research has focused on problems in 2d, but 3d contact representations have also been investigated, mostly concerning fully-dimensional geometric objects such as spheres or cubes. In this paper we study contact representations with convex polygons in 3d. We show that every graph admits such a representation. Since our representations use super-polynomial coordinates, we also construct representations on grids of polynomial size for specific graph classes (bipartite, subcubic). For hypergraphs, we represent their duals, that is, each vertex is represented by a point and each edge by a polygon. We show that even regular and quite small hypergraphs do not admit such representations. On the other hand, the two smallest Steiner triple systems can be represented.
hypergraphs  graph-layout  rather-interesting  to-simulate  to-do  to-write-about  related-to:recent-puzzle
28 days ago by Vaguery
allRGB
The objective of allRGB is simple: To create images with one pixel for every RGB color (16777216); not one color missing, and not one color twice.
Oulipo  art  conceptual-constraints  to-write-about  consider:differing-strategies  consider:grayscale-ones  rather-interesting  via:mathpuzzle.com
4 weeks ago by Vaguery
Parens for Pyplot - Squid's Blog
libpython-clj has opened the door for Clojure to directly interop with Python libraries. That means we can take just about any Python library and directly use it in our Clojure REPL. But what about matplotlib?

Matplotlib.pyplot is a standard fixture in most tutorials and python data science code. How do we interop with a python graphics library?
python  Clojure  interoperability  library  to-use  to-try  to-write-about  consider:ClojureScript
4 weeks ago by Vaguery
[1804.02385] The chromatic number of the plane is at least 5
We present a family of finite unit-distance graphs in the plane that are not 4-colourable, thereby improving the lower bound of the Hadwiger-Nelson problem. The smallest such graph that we have so far discovered has 1581 vertices.
open-questions  coloring-problems  rather-interesting  counterexamples  to-write-about  to-simulate  consider:genetic-programming  consider:density-of-points
4 weeks ago by Vaguery
The Right Stuff - Futility Closet
Take any two rational numbers whose product is 2, and add 2 to each. The results are the legs of a right triangle with rational sides.
plane-geometry  generator  heuristics  rather-interesting  to-write-about  to-simulate  consider:generalizations  consider:genetic-programming
4 weeks ago by Vaguery
[1702.08066] On the Classification and Algorithmic Analysis of Carmichael Numbers
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
[1605.04300] On the Circle Covering Theorem by A. W. Goodman and R. E. Goodman
In 1945, A. W. Goodman and R. E. Goodman proved the following conjecture by P. Erdős: Given a family of (round) disks of radii r1, …, rn in the plane it is always possible to cover them by a disk of radius R=∑ri, provided they cannot be separated into two subfamilies by a straight line disjoint from the disks. In this note we show that essentially the same idea may work for different analogues and generalizations of their result. In particular, we prove the following: Given a family of positive homothetic copies of a fixed convex body K⊂ℝd with homothety coefficients τ1,…,τn>0 it is always possible to cover them by a translate of d+12(∑τi)K, provided they cannot be separated into two subfamilies by a hyperplane disjoint from the homothets.
covering-problems  plane-geometry  rather-interesting  to-simulate  to-write-about  proof  consider:looking-to-see  consider:robustness  consider:feature-discovery
4 weeks ago by Vaguery
[1806.06751] Entropy of hard square lattice gas with $k$ distinct species of particles: coloring problems and vertex models
Coloring the faces of 2-dimensional square lattice with k distinct colors such that no two adjacent faces have the same color is considered by establishing connection between the k coloring problem and a generalized vertex model. Associating the colors with k distinct species of particles with infinite repulsive force between nearest neighbors of the same type and zero chemical potential μ associated with each species, the number of ways [W(k)]N for large N is related to the entropy of the {\it{hard square lattice gas}} at close packing of the lattice, where N is the number of lattice sites. We discuss the evaluation of W(k) using transfer matrix method with non-periodic boundary conditions imposed on at least one dimension and show the characteristic Toeplitz block structure of the transfer matrix. Using this result, we present some analytical calculations for non-periodic models that remain finite in one dimension. The case k=3 is found to approach the exact result obtained by Lieb for the residual entropy of ice with periodic boundary conditions. Finally, we show, by explicit calculation of the contribution of subgraphs and the series expansion of W(k), that the genenralized Pauling type estimate(which is based on mean field approximation) dominates at large values of k. We thus also provide an alternative series expansion for the chromatic polynomial of a regular square graph.
graph-theory  graph-coloring  algorithms  parallel  distributed-processing  cellular-automata  rather-interesting  to-simulate  to-write-about  consider:constraint-satisfaction  consider:rules-variants
4 weeks ago by Vaguery
[1501.04472] Local analysis of the history dependence in tetrahedra packings
The mechanical properties of a granular sample depend frequently on the way the packing was prepared. However, is not well understood which properties of the packing store this information. Here we present an X-ray tomography study of three pairs of tetrahedra packings prepared with three different tapping protocols. The packings in each pair differs in the number of mechanical constraints C imposed on the particles by their contacts, while their bulk volume fraction ϕglobal is approximately the same. We decompose C into the contributions of the three different contact types possible between tetrahedra -- face-to-face (F2F), edge-to-face (E2F), and point contacts -- which each fix a different amount of constraints. We then perform a local analysis of the contact distribution by grouping the particles together according to their individual volume fraction ϕlocal computed from a Voronoi tessellation. We find that in samples which have been tapped sufficiently long the number of F2F contacts becomes an universal function of ϕlocal. In contrast the number of E2F and point contacts varies with the applied tapping protocol. Moreover, we find that the anisotropy of the shape of the Voronoi cells depends on the tapping protocol. This behavior differs from spheres and ellipsoids and posses a significant constraint for any mean-field approach to tetrahedra packings.
granular-materials  packing  physics!  experiment  looking-to-see  rather-interesting  condensed-matter  to-write-about  to-simulate  consider:matter.js  consider:2d
4 weeks ago by Vaguery
Stanford CoreNLP – Natural language software | Stanford CoreNLP
Stanford CoreNLP provides a set of human language technology tools. It can give the base forms of words, their parts of speech, whether they are names of companies, people, etc., normalize dates, times, and numeric quantities, mark up the structure of sentences in terms of phrases and syntactic dependencies, indicate which noun phrases refer to the same entities, indicate sentiment, extract particular or open-class relations between entity mentions, get the quotes people said, etc.
natural-language-processing  library  Clojure  to-understand  to-use  to-write-about  notesapp
4 weeks ago by Vaguery
[1811.03690] Machine Learning Characterization of Structural Defects in Amorphous Packings of Dimers and Ellipses
Structural defects within amorphous packings of symmetric particles can be characterized using a machine learning approach that incorporates structure functions of radial distances and angular arrangement. This yields a scalar field, \emph{softness}, that correlates with the probability that a particle is about to rearrange. However, when particle shapes are elongated, as in the case of dimers and ellipses, we find the standard structure functions produce imprecise softness measurements. Moreover, ellipses exhibit deformation profiles in stark contrast to circular particles. In order to account for effects of orientation and alignment, we introduce new structure functions to recover predictive performance of softness, as well as provide physical insight to local and extended dynamics. We study a model disordered solid, a bidisperse two-dimensional granular pillar, driven by uniaxial compression and composed entirely of monomers, dimers, or ellipses. We demonstrate how the computation of softness via support vector machine extends to dimers and ellipses with the introduction of new orientational structure functions. Then, we highlight the spatial extent of rearrangements and defects, as well as their cross-correlation, for each particle shape. Finally, we demonstrate how an additional machine learning algorithm, recursive feature elimination, provides an avenue to better understand how softness arises from particular structural aspects. We identify the most crucial structure functions in determining softness and discuss their physical implications.
physics  granular-materials  machine-learning  neural-networks  rather-interesting  approximation  feature-extraction  to-simulate  to-write-about  consider:genetic-programming  consider:feature-discovery  consider:re-representation
4 weeks ago by Vaguery
[1805.03963] Monotone Learning with Rectified Wire Networks
We introduce a new neural network model, together with a tractable and monotone online learning algorithm. Our model describes feed-forward networks for classification, with one output node for each class. The only nonlinear operation is rectification using a ReLU function with a bias. However, there is a rectifier on every edge rather than at the nodes of the network. There are also weights, but these are positive, static, and associated with the nodes. Our "rectified wire" networks are able to represent arbitrary Boolean functions. Only the bias parameters, on the edges of the network, are learned. Another departure in our approach, from standard neural networks, is that the loss function is replaced by a constraint. This constraint is simply that the value of the output node associated with the correct class should be zero. Our model has the property that the exact norm-minimizing parameter update, required to correctly classify a training item, is the solution to a quadratic program that can be computed with a few passes through the network. We demonstrate a training algorithm using this update, called sequential deactivation (SDA), on MNIST and some synthetic datasets. Upon adopting a natural choice for the nodal weights, SDA has no hyperparameters other than those describing the network structure. Our experiments explore behavior with respect to network size and depth in a family of sparse expander networks.
machine-learning  neural-networks  representation  algorithms  to-simulate  to-write-about  consider:performance-measures  rather-interesting
4 weeks ago by Vaguery
[1701.00706] Bounds on parameters of minimally non-linear patterns
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
4 weeks ago by Vaguery
[1704.05207] Algorithms for Pattern Containment in 0-1 Matrices
We say a zero-one matrix A avoids another zero-one matrix P if no submatrix of A can be transformed to P by changing some ones to zeros. A fundamental problem is to study the extremal function ex(n,P), the maximum number of nonzero entries in an n×n zero-one matrix A which avoids P. To calculate exact values of ex(n,P) for specific values of n, we need containment algorithms which tell us whether a given n×n matrix A contains a given pattern matrix P. In this paper, we present optimal algorithms to determine when an n×n matrix A contains a given pattern P when P is a column of all ones, an identity matrix, a tuple identity matrix, an L-shaped pattern, or a cross pattern. These algorithms run in Θ(n2) time, which is the lowest possible order a containment algorithm can achieve. When P is a rectangular all-ones matrix, we also obtain an improved running time algorithm, albeit with a higher order.
matrices  constraint-satisfaction  game-theory  rather-interesting  mathematical-recreations  patterns  permutations  to-simulate  to-write-about  consider:feature-discovery  combinatorics
4 weeks ago by Vaguery
[1704.05211] Results on Pattern Avoidance Games
A zero-one matrix A contains another zero-one matrix P if some submatrix of A can be transformed to P by changing some ones to zeros. A avoids P if A does not contain P. The Pattern Avoidance Game is played by two players. Starting with an all-zero matrix, two players take turns changing zeros to ones while keeping A avoiding P. We study the strategies of this game for some patterns P. We also study some generalizations of this game.
crowdsourcing  rather-interesting  game-theory  patterns  permutations  looking-to-see  open-questions  to-simulate  to-write-about  mathematical-recreations  matrices
4 weeks ago by Vaguery
[1911.09792] Minority Voter Distributions and Partisan Gerrymandering
Many people believe that it is disadvantageous for members aligning with a minority party to cluster in cities, as this makes it easier for the majority party to gerrymander district boundaries to diminish the representation of the minority. We examine this effect by exhaustively computing the average representation for every possible 5×5 grid of population placement and district boundaries. We show that, in fact, it is advantageous for the minority to arrange themselves in clusters, as it is positively correlated with representation. We extend this result to more general cases by considering the dual graph of districts, and we also propose and analyze metaheuristic algorithms that allow us to find strong lower bounds for maximum expected representation.
gerrymandering  voting  looking-to-see  simulation  rather-interesting  fairness  optimization  multiobjective-optimization  to-simulate  to-write-about
4 weeks ago by Vaguery
[1705.06774] On Variations of Nim and Chomp
We study two variations of Nim and Chomp which we call Monotonic Nim and Diet Chomp. In Monotonic Nim the moves are the same as in Nim, but the positions are non-decreasing numbers as in Chomp. Diet-Chomp is a variation of Chomp, where the total number of squares removed is limited.
mathematical-recreations  game-theory  games  rather-interesting  to-write-about  to-simulate  out-of-the-box
4 weeks ago by Vaguery
[1605.05601] Alternator Coins
We introduce a new type of coin: \textit{the alternator}. The alternator can pretend to be either a real or a fake coin (which is lighter than a real one). Each time it is put on a balance scale it switches between pretending to be either a real coin or a fake one.
In this paper, we solve the following problem: You are given N coins that look identical, but one of them is the alternator. All real coins weigh the same. You have a balance scale which you can use to find the alternator. What is the smallest number of weighings that guarantees that you will find the alternator?
coin-weighing-problems  mathematical-recreations  puzzles  rather-interesting  out-of-the-box  to-simulate  to-write-about  consider:genetic-programming  combinatorics  optimization
4 weeks ago by Vaguery
[1603.08549] Who Is Guilty?
We discuss a generalization of logic puzzles in which truth-tellers and liars are allowed to deviate from their pattern in case of one particular question: "Are you guilty?"
logic  puzzles  mathematical-recreations  constraint-satisfaction  looking-to-see  generalization  to-write-about  to-simulate
4 weeks ago by Vaguery
[1909.07007] Asymptotics of $d$-Dimensional Visibility
We consider the space [0,n]3, imagined as a three dimensional, axis-aligned grid world partitioned into n3 1×1×1 unit cubes. Each cube is either considered to be empty, in which case a line of sight can pass through it, or obstructing, in which case no line of sight can pass through it. From a given position, some of these obstructing cubes block one's view of other obstructing cubes, leading to the following extremal problem: What is the largest number of obstructing cubes that can be simultaneously visible from the surface of an observer cube, over all possible choices of which cubes of [0,n]3 are obstructing? We construct an example of a configuration in which Ω(n83) obstructing cubes are visible, and generalize this to an example with Ω(nd−1d) visible obstructing hypercubes for dimension d>3. Using Fourier analytic techniques, we prove an O(nd−1dlogn) upper bound in a reduced visibility setting.
visibility-problems  illumination-problems  computational-geometry  rather-interesting  to-simulate  to-write-about  looking-to-see
4 weeks ago by Vaguery
[1808.04304] On Base 3/2 and its Sequences
We discuss properties of integers in base 3/2. We also introduce many new sequences related to base 3/2. Some sequences discuss patterns related to integers in base 3/2. Other sequence are analogues of famous base-10 sequences: we discuss powers of 3 and 2, Look-and-say, and sorted and reverse sorted Fibonaccis. The eventual behavior of sorted and reverse sorted Fibs leads to special Pinocchio and Oihcconip sequences respectively.
number-theory  combinatorics  radix  rather-interesting  mathematical-recreations  to-simulate  to-write-about  consider:irrational-values  representation
4 weeks ago by Vaguery
[1808.06713] Mathematics of a Sudo-Kurve
We investigate a type of a Sudoku variant called Sudo-Kurve, which allows bent rows and columns, and develop a new, yet equivalent, variant we call a Sudo-Cube. We examine the total number of distinct solution grids for this type with or without symmetry. We study other mathematical aspects of this puzzle along with the minimum number of clues needed and the number of ways to place individual symbols.
sudoku  mathematical-recreations  constraint-satisfaction  rather-interesting  puzzles  out-of-the-box  to-write-about  to-simulate  consider:simpler
4 weeks ago by Vaguery
[1809.09676] Chip-Firing and Fractional Bases
We study a particular chip-firing process on an infinite path graph. At any time when there are at least a+b chips at a vertex, a chips fire to the left and b chips fire to the right. We describe the final state of this process when we start with n chips at the origin.
chip-firing  dynamical-systems  number-theory  mathematical-recreations  rather-interesting  to-write-about  to-simulate  combinatorics
4 weeks ago by Vaguery
[1612.04861] Some Counterexamples for Compatible Triangulations
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
4 weeks ago by Vaguery
[1901.09818] Variants of Base 3 over 2
We discuss two different systems of number representations that both can be called 'base 3/2'. We explain how they are connected. Unlike classical fractional extension, these two systems provide a finite representation for integers. We also discuss a connection between these systems and 3-free sequences.
radix  mathematical-recreations  exploding-dots  rather-interesting  representation  number-theory  exploration  to-write-about  to-simulate
4 weeks ago by Vaguery
[1203.3353] Solving Structure with Sparse, Randomly-Oriented X-ray Data
Single-particle imaging experiments of biomolecules at x-ray free-electron lasers (XFELs) require processing of hundreds of thousands (or more) of images that contain very few x-rays. Each low-flux image of the diffraction pattern is produced by a single, randomly oriented particle, such as a protein. We demonstrate the feasibility of collecting data at these extremes, averaging only 2.5 photons per frame, where it seems doubtful there could be information about the state of rotation, let alone the image contrast. This is accomplished with an expectation maximization algorithm that processes the low-flux data in aggregate, and without any prior knowledge of the object or its orientation. The versatility of the method promises, more generally, to redefine what measurement scenarios can provide useful signal in the high-noise regime.
diffraction  inverse-problems  tomography  rather-interesting  algorithms  statistics  probability-theory  inference  to-simulate  to-write-about  optimization  signal-processing
4 weeks ago by Vaguery
[1305.0289] Pessimal packing shapes
We address the question of which convex shapes, when packed as densely as possible under certain restrictions, fill the least space and leave the most empty space. In each different dimension and under each different set of restrictions, this question is expected to have a different answer or perhaps no answer at all. As the problem of identifying global minima in most cases appears to be beyond current reach, in this paper we focus on local minima. We review some known results and prove these new results: in two dimensions, the regular heptagon is a local minimum of the double-lattice packing density, and in three dimensions, the directional derivative (in the sense of Minkowski addition) of the double-lattice packing density at the point in the space of shapes corresponding to the ball is in every direction positive.
packing  computational-geometry  optimization  worst-cases  rather-interesting  to-simulate  to-write-about  consider:convex  consider:monte-carlo
4 weeks ago by Vaguery
[1706.03049] A linear-time algorithm for the maximum-area inscribed triangle in a convex polygon
Given the n vertices of a convex polygon in cyclic order, can the triangle of maximum area inscribed in P be determined by an algorithm with O(n) time complexity? A purported linear-time algorithm by Dobkin and Snyder from 1979 has recently been shown to be incorrect by Keikha, Löffler, Urhausen, and van der Hoog. These authors give an alternative algorithm with O(n log n) time complexity. Here we give an algorithm with linear time complexity.
computational-complexity  computational-geometry  algorithms  rather-interesting  plane-geometry  to-simulate  to-write-about  consider:genetic-programming
4 weeks ago by Vaguery
[1805.06512] The Broken Stick Project
The broken stick problem is the following classical question.
You have a segment [0,1]. You choose two points on this segment at random. They divide the segment into three smaller segments. Show that the probability that the three segments form a triangle is 1/4.
The MIT PRIMES program, together with Art of Problem Solving, organized a high school research project where participants worked on several variations of this problem. Participants were generally high school students who posted ideas and progress to the Art of Problem Solving forums over the course of an entire year, under the supervision of PRIMES mentors. This report summarizes the findings of this CrowdMath project.
crowdsourcing  see-author  open-questions  geometry  probability-theory  rather-interesting  to-write-about  to-simulate  consider:genetic-programming  consider:performance-measures
4 weeks ago by Vaguery
[1107.4030] Three dimensional structure from intensity correlations
We develop the analysis of x-ray intensity correlations from dilute ensembles of identical particles in a number of ways. First, we show that the 3D particle structure can be determined if the particles can be aligned with respect to a single axis having a known angle with respect to the incident beam. Second, we clarify the phase problem in this setting and introduce a data reduction scheme that assesses the integrity of the data even before the particle reconstruction is attempted. Finally, we describe an algorithm that reconstructs intensity and particle density simultaneously, thereby making maximal use of the available constraints.
signal-processing  crystallography  inverse-problems  rather-interesting  diffraction  numerical-methods  to-write-about  to-simulate
4 weeks ago by Vaguery
[1305.1310] Statistical mechanics of the lattice sphere packing problem
We present an efficient Monte Carlo method for the lattice sphere packing problem in d dimensions. We use this method to numerically discover de novo the densest lattice sphere packing in dimensions 9 through 20. Our method goes beyond previous methods not only in exploring higher dimensions but also in shedding light on the statistical mechanics underlying the problem in question. We observe evidence of a phase transition in the thermodynamic limit d→∞. In the dimensions explored in the present work, the results are consistent with a first-order crystallization transition, but leave open the possibility that a glass transition is manifested in higher dimensions.
packing  open-problems  optimization  looking-to-see  sampling  approximation  to-simulate  to-write-about  consider:performance-measures  consider:robustness  consider:relaxations
4 weeks ago by Vaguery
[1305.1961] An Improved Three-Weight Message-Passing Algorithm
We describe how the powerful "Divide and Concur" algorithm for constraint satisfaction can be derived as a special case of a message-passing version of the Alternating Direction Method of Multipliers (ADMM) algorithm for convex optimization, and introduce an improved message-passing algorithm based on ADMM/DC by introducing three distinct weights for messages, with "certain" and "no opinion" weights, as well as the standard weight used in ADMM/DC. The "certain" messages allow our improved algorithm to implement constraint propagation as a special case, while the "no opinion" messages speed convergence for some problems by making the algorithm focus only on active constraints. We describe how our three-weight version of ADMM/DC can give greatly improved performance for non-convex problems such as circle packing and solving large Sudoku puzzles, while retaining the exact performance of ADMM for convex problems. We also describe the advantages of our algorithm compared to other message-passing algorithms based upon belief propagation.
constraint-satisfaction  algorithms  distributed-processing  rather-interesting  to-simulate  to-write-about  consider:sudoku  consider:performance-measures
4 weeks ago by Vaguery
[1310.5924] The symplectic geometry of closed equilateral random walks in 3-space
A closed equilateral random walk in 3-space is a selection of unit length vectors giving the steps of the walk conditioned on the assumption that the sum of the vectors is zero. The sample space of such walks with n edges is the (2n−3)-dimensional Riemannian manifold of equilateral closed polygons in ℝ3. We study closed random walks using the symplectic geometry of the (2n−6)-dimensional quotient of the manifold of polygons by the action of the rotation group SO(3). The basic objects of study are the moment maps on equilateral random polygon space given by the lengths of any (n−3)-tuple of nonintersecting diagonals. The Atiyah-Guillemin-Sternberg theorem shows that the image of such a moment map is a convex polytope in (n−3)-dimensional space, while the Duistermaat-Heckman theorem shows that the pushforward measure on this polytope is Lebesgue measure on ℝn−3. Together, these theorems allow us to define a measure-preserving set of "action-angle" coordinates on the space of closed equilateral polygons. The new coordinate system allows us to make explicit computations of exact expectations for total curvature and for some chord lengths of closed (and confined) equilateral random walks, to give statistical criteria for sampling algorithms on the space of polygons and to prove that the probability that a randomly chosen equilateral hexagon is unknotted is at least 12. We then use our methods to construct a new Markov chain sampling algorithm for equilateral closed polygons, with a simple modification to sample (rooted) confined equilateral closed polygons. We prove rigorously that our algorithm converges geometrically to the standard measure on the space of closed random walks, give a theory of error estimators for Markov chain Monte Carlo integration using our method and analyze the performance of our method. Our methods also apply to open random walks in certain types of confinement, and in general to walks with arbitrary (fixed) edgelengths as well as equilateral walks.
probability-theory  combinatorics  random-walks  sampling  rather-interesting  computational-geometry  looking-to-see  to-simulate  to-write-about  consider:rendering
4 weeks ago by Vaguery
per page:    204080120160

Copy this bookmark: