**Vaguery : to-write-about**
1710

Emergent Tool Use from Multi-Agent Interaction

3 days ago by Vaguery

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

3 days ago by Vaguery

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

3 days ago by Vaguery

The King vs. Pawn Game of UI Design – A List Apart

4 days ago by Vaguery

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

4 days ago by Vaguery

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

4 days ago by Vaguery

What Proof Is Best? |

4 days ago by Vaguery

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

6 days ago by Vaguery

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

6 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
6 days ago by Vaguery

[1812.08434] Graph Neural Networks: A Review of Methods and Applications

6 days ago by Vaguery

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

6 days ago by Vaguery

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

6 days ago by Vaguery

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

8 days ago by Vaguery

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

8 days ago by Vaguery

Robustness of the two-sample t-test

10 days ago by Vaguery

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

10 days ago by Vaguery

Running Cargo - Futility Closet

10 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
10 days ago by Vaguery

[PDF] Extended circularity: a new puzzle for extended cognition | Semantic Scholar

10 days ago by Vaguery

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

10 days ago by Vaguery

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

10 days ago by Vaguery

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

10 days ago by Vaguery

DR. HERBERT H. TSANG - http://www.herberttsang.org

14 days ago by Vaguery

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

14 days ago by Vaguery

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

14 days ago by Vaguery

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

14 days ago by Vaguery

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

14 days ago by Vaguery

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

14 days ago by Vaguery

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

14 days ago by Vaguery

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

15 days ago by Vaguery

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

17 days ago by Vaguery

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

17 days ago by Vaguery

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(rc)) 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(rc)) 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

17 days ago by Vaguery

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

22 days ago by Vaguery

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

22 days ago by Vaguery

[1809.10737] Plane and Planarity Thresholds for Random Geometric Graphs

22 days ago by Vaguery

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

22 days ago by Vaguery

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

22 days ago by Vaguery

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

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

22 days ago by Vaguery

[1905.00790] Minimum Ply Covering of Points with Disks and Squares

22 days ago by Vaguery

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

22 days ago by Vaguery

[1905.00791] Flip Distance to some Plane Configurations

22 days ago by Vaguery

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

22 days ago by Vaguery

[1905.07124] Variations of largest rectangle recognition amidst a bichromatic point set

22 days ago by Vaguery

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

22 days ago by Vaguery

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

22 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
22 days ago by Vaguery

Constructing random polygons | Proceedings of the 9th ACM SIGITE conference on Information technology education

23 days ago by Vaguery

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

23 days ago by Vaguery

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

26 days ago by Vaguery

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

26 days ago by Vaguery

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

26 days ago by Vaguery

[1611.06135] Large Values of the Clustering Coefficient

26 days ago by Vaguery

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

26 days ago by Vaguery

[1803.11511] Length segregation in mixtures of spherocylinders induced by imposed topological defects

27 days ago by Vaguery

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

27 days 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
27 days ago by Vaguery

[1904.06108] The Dodecahedron as a Voronoi Cell and its (minor) importance for the Kepler conjecture

27 days ago by Vaguery

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

27 days ago by Vaguery

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

27 days ago by Vaguery

[1802.10038] Improving OCR Accuracy on Early Printed Books by combining Pretraining, Voting, and Active Learning

27 days ago by Vaguery

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

28 days ago by Vaguery

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

4 weeks ago by Vaguery

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

4 weeks ago by Vaguery

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
Matplotlib.pyplot is a standard fixture in most tutorials and python data science code. How do we interop with a python graphics library?

4 weeks ago by Vaguery

Tanya Khovanova's Math Blog » Blog Archive » My New Favorite Probability Puzzle

4 weeks ago by Vaguery

This is my favorite puzzle in the last issue of the Emissary, proposed by Peter Winkler.

probability-theory
puzzles
to-simulate
to-write-about
rather-interesting
consider:generalizations
4 weeks ago by Vaguery

[1804.02385] The chromatic number of the plane is at least 5

4 weeks ago by Vaguery

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

4 weeks ago by Vaguery

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

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

[1605.04300] On the Circle Covering Theorem by A. W. Goodman and R. E. Goodman

4 weeks ago by Vaguery

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

4 weeks ago by Vaguery

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

4 weeks ago by Vaguery

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

4 weeks ago by Vaguery

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

4 weeks ago by Vaguery

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

4 weeks ago by Vaguery

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

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

4 weeks ago by Vaguery

[1704.05207] Algorithms for Pattern Containment in 0-1 Matrices

4 weeks ago by Vaguery

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

4 weeks ago by Vaguery

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

4 weeks ago by Vaguery

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

4 weeks ago by Vaguery

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

4 weeks ago by Vaguery

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

4 weeks ago by Vaguery

[1603.08549] Who Is Guilty?

4 weeks ago by Vaguery

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

4 weeks ago by Vaguery

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

4 weeks ago by Vaguery

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

4 weeks ago by Vaguery

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

4 weeks ago by Vaguery

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

4 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
4 weeks ago by Vaguery

[1901.09818] Variants of Base 3 over 2

4 weeks ago by Vaguery

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

4 weeks ago by Vaguery

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

4 weeks ago by Vaguery

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

4 weeks ago by Vaguery

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

4 weeks ago by Vaguery

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

4 weeks ago by Vaguery

[1107.4030] Three dimensional structure from intensity correlations

4 weeks ago by Vaguery

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

4 weeks ago by Vaguery

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

4 weeks ago by Vaguery

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

4 weeks ago by Vaguery

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

Copy this bookmark: