Emergent Tool Use from Multi-Agent Interaction

3 days ago

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

Hugging Face GPT With Clojure - Squid's Blog

3 days ago

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

Integrating Deep Learning With clojure.spec - Squid's Blog

3 days ago

clojure.spec allows you to write specifications for data and use them for validation. It also provides a generative aspect that allows for robust testing as well as an additional way to understand your data through manual inspection. The dual nature of validation and generation is a natural fit for deep learning models that consist of paired discriminator/generator models.

Clojure
clojure.spec
machine-learning
to-understand
to-do
consider:representation
consider:structural-types
3 days ago

Accelerate | Apple Developer Documentation

3 days ago

Make large-scale mathematical computations and image calculations, optimized for high performance and low-energy consumption.

swift
library
to-understand
image-processing
GPU
programming
3 days ago

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

4 days ago

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

Regularization Improves the Robustness of Learned Sequence-to-Expression Models | bioRxiv

4 days ago

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

What Proof Is Best? |

4 days ago

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

Specify a secondary axis — sec_axis • ggplot2

4 days ago

This function is used in conjunction with a position scale to create a secondary axis, positioned opposite of the primary axis. All secondary axes must be based on a one-to-one transformation of the primary axes.

R
dataviz
ggplot2
secondary-x-axis
tricks
4 days ago

[1710.04554] Lattice point visibility on generalized lines of sight

6 days ago

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

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

6 days ago

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

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

6 days ago

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

[1809.02836] Context-Free Transductions with Neural Stacks

6 days ago

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

[1906.01615] Sequential Neural Networks as Automata

6 days ago

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

Does art compute? – Symptoms Of The Universe

6 days ago

As Cory Simon explains so well in his “Voronoi cookies and the post office problem” post, the Voronoi algorithm is an easy-to-understand method in computational geometry, especially in two dimensions: take a point, join it up to its nearest neighbours, and get the perpendicular bisectors of those lines. The intersections of the bisectors define a Voronoi cell. If the points form an ordered mesh on the plane — as, for example, in the context of the atoms on a crystal plane in solid state physics — then the Voronoi cell is called a Wigner-Seitz unit cell. (As an undergrad, I didn’t realise that the Wigner-Seitz unit cells I studied in my solid state lectures were part of the much broader Voronoi class — another example of limiting thinking due to disciplinary boundaries.)

unconventional-computing
generative-art
interdisciplinary
artificial-life
heavily-linked
to-walk-from
6 days ago

High-dimensional Time Series Clustering via Cross-Predictability

6 days ago

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

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

Modeling Minds

8 days ago

Embodied Cognition (EC) is an approach in cognitive science that distinguishes itself from more traditional approaches (such as the computational view on cognition) by both a set of commitments on what cognition is and a set of ideas on how it should be studied and what kind of explanations of cognition are acceptable. While pluralism in science can be beneficial, the breadth and depth of the differences between embodied and non-embodied approaches results in two distinct bodies of research that cannot be easily compared and evaluated side by side. Being still a minority view, the losing side of such a situation is EC.

In this workshop, we focus on the different explanatory methodologies in cognitive science specifically in relation to explaining social cognition. We will examine different ways of conceptualizing the explanatory target phenomena in the social domain and different ways of framing explanations thereof, such as the focus on the social experience, the autonomy of the supra-personal level of explanation or the interdependence between social activity and the embedding of cognitive systems in their shared physical environment.

cognition
extended-cognition
rather-interesting
conference
to-read
to-watch-for-papers
In this workshop, we focus on the different explanatory methodologies in cognitive science specifically in relation to explaining social cognition. We will examine different ways of conceptualizing the explanatory target phenomena in the social domain and different ways of framing explanations thereof, such as the focus on the social experience, the autonomy of the supra-personal level of explanation or the interdependence between social activity and the embedding of cognitive systems in their shared physical environment.

8 days ago

Puzzle 864. 10958, the only hole...

8 days ago

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

The Stanford Natural Language Processing Group

10 days ago

Tregex is a utility for matching patterns in trees, based on tree relationships and regular expression matches on nodes (the name is short for "tree regular expressions"). Tregex comes with Tsurgeon, a tree transformation language. Also included from version 2.0 on is a similar package which operates on dependency graphs (class SemanticGraph, called semgrex.

pattern-matching
library
software-development
algorithms
rather-interesting
consider:in-gp-apps
consider:classification
to-understand
to-complain-about-docs
data-structures
10 days ago

Robustness of the two-sample t-test

10 days ago

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

Running Cargo - Futility Closet

10 days ago

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

asciinema - Record and share your terminal sessions, the right way

10 days ago

asciinema [as-kee-nuh-muh] is a free and open source solution for recording terminal sessions and sharing them on the web. Read about how it works.

collaboration
screencasting
rather-interesting
software
open-source
to-understand
to-try
10 days ago

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

10 days ago

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

[1305.1958] The Dynamically Extended Mind -- A Minimal Modeling Case Study

10 days ago

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

The Stanford Literary Lab’s Narrative | Public Books

10 days ago

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

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

13 days ago

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
13 days ago

Short How-To guides — GROMACS 2019 documentation

13 days ago

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
13 days ago

[1902.07277] A systematic classification of knotoids on the plane and on the sphere

13 days ago

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
13 days ago

[1803.07114] Slipknotting in Random Diagrams

13 days ago

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
13 days ago

[1810.07970] Inglenook Shunting Puzzles

13 days ago

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
13 days ago

[1011.4034] Dense packing crystal structures of physical tetrahedra

13 days ago

We present a method for discovering dense packings of general convex hard particles and apply it to study the dense packing behavior of a one-parameter family of particles with tetrahedral symmetry representing a deformation of the ideal mathematical tetrahedron into a less ideal, physical, tetrahedron and all the way to the sphere. Thus, we also connect the two well studied problems of sphere packing and tetrahedron packing on a single axis. Our numerical results uncover a rich optimal-packing behavior, compared to that of other continuous families of particles previously studied. We present four structures as candidates for the optimal packing at different values of the parameter, providing an atlas of crystal structures which might be observed in systems of nano-particles with tetrahedral symmetry.

packing
granular-materials
optimization
geometry
rather-interesting
to-simulate
consider:looking-to-see
consider:particle-sims
13 days ago

[1803.09607] Murder at the Asylum

13 days ago

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
13 days ago

[1804.03311] A Markov Chain Sampler for Plane Curves

13 days ago

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
13 days ago

Myth & Moor: Dark Beauty

13 days ago

"Where woundedness can be refined into beauty," he adds, "a wonderful transfiguration takes place. For instance, compassion is one of the most beautiful presences a person can bring to the world and most compassion is born from one's own woundedness. When you have felt deep emotional pain and hurt, you are able to imagine what the pain of another is like; their suffering touches you. This is the most decisive and vital threshold in human experience and behavior. The greatest evil and destruction arises when people are unable to feel compassion. The beauty of compassion continues to shelter and save our world. If that beauty were quenched, there would be nothing between us and the end-darkness which would pour in torrents over us."

So please, fellow artists and art lovers, keep seeking out, spreading, and making beauty. Don't stop. We all need you. I need you.

art
advice
worklife
lifelife
So please, fellow artists and art lovers, keep seeking out, spreading, and making beauty. Don't stop. We all need you. I need you.

13 days ago

[math/0509478] Simultaneous Diagonal Flips in Plane Triangulations

14 days ago

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
14 days ago

Facilitating Failure Swap Shops — adrianhoward.com

15 days ago

Which in turn reminded me of one of my favourite ways of celebrating learning from failure — Failure Swap Shop!

Luke Williams came up with the format, and I first saw him facilitate a session at BarCamp Bournemouth about ten years ago. I've run it many times since with clients and at events and it's always been informative and fun!

So — what is a Failure Swap Shop?

teams
software-development
project-management
institutional-learning
culture-building
morale
barcamp
Luke Williams came up with the format, and I first saw him facilitate a session at BarCamp Bournemouth about ten years ago. I've run it many times since with clients and at events and it's always been informative and fun!

So — what is a Failure Swap Shop?

15 days ago

Deriving Reactive from Imperative: An Introduction to Duals · Distillations

17 days ago

While Apple’s Combine framework didn’t take center stage, its implications on our community certainly will for the next decade. We now have a first-party toolkit for functional reactive programming (often abbreviated “FRP”) that packs an intimidating namespace of operators, opaque abstractions, and features even Combine’s open-source counterparts omit like backpressure.

This post aims to unpack those choice adjectives, ‘opaque’ and ‘intimidating,’ that are often lobbed at FRP when folks retreat to its more familiar sibling, imperative programming. We’ll start by contrasting the approaches and covering some history before deriving Combine’s foundational types, Subscriber and Publisher.

via:cdzombak
swift
programming-language
library
declarative-programming
software-development-is-not-programming
This post aims to unpack those choice adjectives, ‘opaque’ and ‘intimidating,’ that are often lobbed at FRP when folks retreat to its more familiar sibling, imperative programming. We’ll start by contrasting the approaches and covering some history before deriving Combine’s foundational types, Subscriber and Publisher.

17 days ago

[2001.09212] PCGRL: Procedural Content Generation via Reinforcement Learning

17 days ago

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

[1804.07150] Improved Bounds for Guarding Plane Graphs with Edges

17 days ago

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

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

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

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

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

17 days ago

[1808.01984] Time-Dependent Shortest Path Queries Among Growing Discs

17 days ago

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

[1809.08898] Rectilinear Shortest Paths Among Transient Obstacles

17 days ago

This paper presents an optimal Θ(nlogn) algorithm for determining time-minimal rectilinear paths among n transient rectilinear obstacles. An obstacle is transient if it exists in the scene only for a specific time interval, i.e., it appears and then disappears at specific times. Given a point robot moving with bounded speed among transient rectilinear obstacles and a pair of points s, d, we determine a time-minimal, obstacle-avoiding path from s to d. The main challenge in solving this problem arises as the robot may be required to wait for an obstacle to disappear, before it can continue moving toward the destination. Our algorithm builds on the continuous Dijkstra paradigm, which simulates propagating a wavefront from the source point. We also solve a query version of this problem. For this, we build a planar subdivision with respect to a fixed source point, so that minimum arrival time to any query point can be reported in O(logn) time, using point location for the query point in this subdivision.

computational-geometry
computational-complexity
planning
rather-interesting
to-understand
representation
wavelets
to-simulate
consider:representation
17 days ago

[2001.11709] Gaussian Random Embeddings of Multigraphs

17 days ago

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

[1809.09979] Approximability of Covering Cells with Line Segments

22 days ago

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

[1809.10737] Plane and Planarity Thresholds for Random Geometric Graphs

22 days ago

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

[1810.09232] On the Minimum Consistent Subset Problem

22 days ago

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

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

22 days ago

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

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

22 days ago

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

[1905.00791] Flip Distance to some Plane Configurations

22 days ago

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

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

22 days ago

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

[1906.11948] Packing Boundary-Anchored Rectangles and Squares

22 days ago

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

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

22 days ago

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

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

23 days ago

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

CiteSeerX — RPG - Heuristics for the Generation of Random Polygons

23 days ago

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

[1706.10193] More Turán-Type Theorems for Triangles in Convex Point Sets

25 days ago

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
25 days ago

[1812.05163] Declination as a Metric to Detect Partisan Gerrymandering

25 days ago

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.

25 days ago

Ondatrópica - I Ron Man - YouTube

26 days ago

Ondatrópica - I Ron Man

via:WCBN
cover-songs
music
world-music
have-liked
26 days ago

For Decades, New York's Chinatown Duped 'Slum Tourists' With Faked Danger and Depravity - Atlas Obscura

26 days ago

It was in one sense a profoundly inauthentic view of life in poor or ethnic neighborhoods, but Heap is more circumspect about what “authenticity” means here. The behavior might have been staged, but the slumming venues were authentic, inasmuch as they were doing what they were set up to do—immersive theater. Chop suey wasn’t “real” Chinese food, but itself became a genuine, distinctive dish. “Some of these venues are creating a new kind of authenticity,” he says. “It’s not like people are transported away to the old country and are getting a glimpse of ‘what really happened.’” Indeed, the boring routine of everyday life, though different uptown and downtown, was what slummers were trying to escape in the first place.

nanohistory
class
tourism
performance
vicarious-precarity
26 days ago

[1611.06135] Large Values of the Clustering Coefficient

26 days ago

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

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

27 days ago

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

[1803.09639] On the multipacking number of grid graphs

27 days ago

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

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

27 days ago

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

[1712.04922] Closing the gap for pseudo-polynomial strip packing

27 days ago

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

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

27 days ago

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

[2001.07790] Investor Experiences and International Capital Flows

27 days ago

We propose a novel explanation for classic international macro puzzles regarding capital flows and portfolio investment, which builds on modern macro-finance models of experience-based belief formation. Individual experiences of past macroeconomic outcomes have been shown to exert a long-lasting influence on beliefs about future realizations, and to explain domestic stock-market investment. We argue that experience effects can explain the tendency of investors to hold an over proportional fraction of their equity wealth in domestic stocks (home bias), to invest in domestic equity markets in periods of domestic crises (retrenchment), and to withdraw capital from foreign equity markets in periods of foreign crises (fickleness). Experience-based learning generates additional implications regarding the strength of these puzzles in times of higher or lower economic activity and depending on the demographic composition of market participants. We test and confirm these predictions in the data.

macroeconomics
finance
globalism
rather-interesting
social-dynamics
investment-panics
systems-thinking
model
economics
27 days ago

[1908.08273] Representing Graphs and Hypergraphs by Touching Polygons in 3D

28 days ago

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

The Unicode Blog: Unicode Maya Hieroglyph Project

29 days ago

The National Endowment for the Humanities (NEH) recently announced their grants for 2020 to support 188 humanities projects across the United States. The Unicode Consortium's project to make Maya texts accessible to both expert and non-expert user communities through creating an annotated digital archive is one of the funded projects. This project will be led by principal investigator, Gabrielle Vail.

unicode
languages
typography
hieroglyphics
to-watch
Mayan-language
29 days ago

allRGB

29 days ago

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
29 days ago

Chocolate Pound Cake Recipe | Trisha Yearwood | Food Network

4 weeks ago

Chocolate Pound Cake

cake
recipe
have-made
good
4 weeks ago

TikZJax

4 weeks ago

TikZ is running entirely in the browser!

LaTeX
web-design
library
whew
typography
rather-interesting
to-try
4 weeks ago

Parens for Pyplot - Squid's Blog

4 weeks ago

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

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

4 weeks ago

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

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

4 weeks ago

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

The Right Stuff - Futility Closet

4 weeks ago

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

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

4 weeks ago

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

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

4 weeks ago

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

[1806.06751] Entropy of hard square lattice gas with $k$ distinct species of particles: coloring problems and vertex models

4 weeks ago

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

[1012.0369] Jammed particulate systems are inherently nonharmonic

4 weeks ago

Jammed particulate systems, such as granular media, colloids, and foams, interact via one-sided forces that are nonzero only when particles overlap. We find that systems with one-sided repulsive interactions possess no linear response regime in the large system limit (N→∞) for all pressures p (or compressions Δϕ), and for all N near jamming onset p→0. We perform simulations on 2D frictionless bidisperse mechanically stable disk packings over a range of packing fractions Δϕ=ϕ−ϕJ above jamming onset ϕJ. We apply perturbations with amplitude δ to the packings along each eigen-direction from the dynamical matrix and determine whether the response of the system evolving at constant energy remains in the original eigenmode of the perturbation. For δ>δc, which we calculate analytically, a single contact breaks and fluctuations abruptly spread to all harmonic modes. As δ increases further all discrete harmonic modes disappear into a continuous frequency band. We find that <δc>∼Δϕ/Nλ, where 1>λ>0.5, and thus jammed particulate systems are inherently nonharmonic with no linear vibrational response regime as N→∞ over the full range of Δϕ, and as Δϕ→0 at any N.

granular-materials
physics!
nonlinear-dynamics
complexology
rather-interesting
simulation
looking-to-see
have-you-tried-thwacking-it?
ah-yes-I-see-you-did
4 weeks ago

Clojure Spec Tips

4 weeks ago

This post includes some practical tips for getting the most out of spec. I'll update it whenever I find out something new, so please feel free to tell me things I don't know.

Clojure
software-development-is-not-programming
clojure.spec
library
reference
to-understand
4 weeks ago

SIM.JS | Discrete Event Simulation in JavaScript

4 weeks ago

SIM.JS is a library for modeling discrete time event systems:

The library provides constructs to create Entities which are the active actors in the system and encapsulates the state and logic of components in a system.

The entities contend for resources, which can be Facilities (services that are requested by entities; supports FIFO, LIFO with preemption and Processor Sharing service disciplines), Buffers (resources that can store finite amount of tokens) and Stores (resources that can store JavaScript objects).

The entities communicate by waiting on Events or by sending Messages.

Statistics recording and analysis is provided by Data Series Statistics (collection of discrete, time-independent observations), Time Series Statistics (collection of discrete, time-dependent observations) and Population Statistics (the behavior of population growth and decline).

SIM.JS also provides a random number generation library to generate seeded random variates from various distributions, including uniform, exponential, normal, gamma, pareto and others.

discrete-event-simulator
library
javascript
to-try
simulation
engineering-design
prediction
optimization
The library provides constructs to create Entities which are the active actors in the system and encapsulates the state and logic of components in a system.

The entities contend for resources, which can be Facilities (services that are requested by entities; supports FIFO, LIFO with preemption and Processor Sharing service disciplines), Buffers (resources that can store finite amount of tokens) and Stores (resources that can store JavaScript objects).

The entities communicate by waiting on Events or by sending Messages.

Statistics recording and analysis is provided by Data Series Statistics (collection of discrete, time-independent observations), Time Series Statistics (collection of discrete, time-dependent observations) and Population Statistics (the behavior of population growth and decline).

SIM.JS also provides a random number generation library to generate seeded random variates from various distributions, including uniform, exponential, normal, gamma, pareto and others.

4 weeks ago

[1501.04472] Local analysis of the history dependence in tetrahedra packings

4 weeks ago

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

Stanford CoreNLP – Natural language software | Stanford CoreNLP

4 weeks ago

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

Copy this bookmark: