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


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


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

Right now, that library is Hugging Face Transformers.


Get ready. We will wrap that sweet hugging face code in Clojure parens!
machine-learning  Clojure  interop  natural-language-processing  rather-interesting  library  to-understand  to-follow-along  to-write-about  consider:scraping-for-data 
3 days ago
Integrating Deep Learning With clojure.spec - Squid's Blog
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
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
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
Understanding of the gene regulatory activity of enhancers is a major problem in regulatory biology. The nascent field of sequence-to-expression modelling seeks to create quantitative models of gene expression based on regulatory DNA (cis) and cellular environmental (trans) contexts. All quantitative models are defined partially by numerical parameters, and it is common to fit these parameters to data provided by existing experimental results. However, the relative paucity of experimental data appropriate for this task, and lacunae in our knowledge of all components of the systems, results in problems often being under-specified, which in turn may lead to a situation where wildly different model parameterizations perform similarly well on training data. It may also lead to models being fit to the idiosyncrasies of the training data, without representing the more general process (overfitting).

In other contexts where parameter-fitting is performed, it is common to apply regularization to reduce overfitting. We systematically evaluated the efficacy of three types of regularization in improving the generalizability of trained sequence-to-expression models. The evaluation was performed in two types of cross-validation experiments: one training on D. melanogaster data and predicting on orthologous enhancers from related species, and the other cross-validating between four D. melanogaster neurogenic ectoderm enhancers, which are thought to be under control of the same transcription factors. We show that training with a combination of noise-injection, L1, and L2 regularization can drastically reduce overfitting and improve the generalizability of learned sequence-to-expression models. These results suggest that it may be possible to mitigate the tendency of sequence-to-expression models to overfit available data, thus improving predictive power and potentially resulting in models that provide better insight into underlying biological processes.
bioinformatics  systems-biology  nonlinear-dynamics  machine-learning  regularization  statistics  numerical-methods  heuristics  to-write-about  to-simulate  consider:symbolic-regression  consider:robustness 
4 days ago
What Proof Is Best? |
A great illustration of this “Let a hundred proofs bloom” point of view is provided by an article by Stan Wagon called “Fourteen Proofs of a Result About Tiling a Rectangle”. Here’s the result his title refers to (a puzzle posed and solved by Nicolaas de Bruijn): Whenever a rectangle can be cut up into smaller rectangles each of which has at least one integer side, then the big rectangle has at least one integer side too. (Here “at least one integer side” is tantamount to “at least two integer sides”, since the opposite sides of a rectangle always have the same length.)
mathematics  philosophy  solution-spaces  diversity  proof  to-write-about  to-simulate  consider:surprise 
4 days ago
Specify a secondary axis — sec_axis • ggplot2
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
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
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
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
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
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
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
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
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 
8 days ago
Puzzle 864. 10958, the only hole...
Brazilian mathematician Inder J. Taneja has found (Jan 2014) a way to render every number from 1 to 11,111 by starting with either of these ordered strings.

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

applying any of the following:

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

This post will explore the robustness of the t-test via simulation. How far can you be from a normal distribution and still do OK? Can you have any distribution as long as it’s symmetric? Does a little asymmetry ruin everything? If something does go wrong, how does it go wrong?
statistics  looking-to-see  rather-interesting  algorithms  robustness  to-do  to-write-about  consider:animation 
10 days ago
Running Cargo - Futility Closet
This passage is from Rudyard Kipling’s 1910 story “Brother Square-Toes.” What’s notable about the bolded section?
feature-construction  rather-interesting  digital-humanities  to-write-about  consider:looking-to-see 
10 days ago
asciinema - Record and share your terminal sessions, the right way
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
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
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
Experiment is presented here not just as a test of reliable knowledge but as a style of intellectual growth: “By frustrating our expectations, failed experiments ‘estrange’ our natural habits of thought, offering a chance to transcend them.” At moments, the point of experiment seems to become entirely aesthetic. In the book’s introduction, Moretti admits that he set out to write “a scientific essay, composed like a Mahler symphony: discordant registers that barely manage to coexist; a forward movement endlessly diverted; the easiest of melodies, followed by leaps into the unknown.”
This account of the book’s aesthetic achievement is candid, immodest, and accurate. The essays within are unified by a deliberately wandering structure, which keeps its distance both from scientists’ predictable sequences (methods → results → conclusions), and from the thesis-driven template that prevails in the humanities (counter-intuitive claim → evidence → I was right after all). Instead, these essays become stories of progressive disorientation, written in the first-person plural, and arriving at theses that were only dimly foreshadowed.
digital-humanities  literary-criticism  rather-interesting  this-quote  to-write-about  consider:the-creative-system 
10 days ago
DR. HERBERT H. TSANG - http://www.herberttsang.org
RNA design algorithm takes an RNA secondary structure description as input and then try to identify an RNA strand that folds into this function-specific target structure. With new advances in biotechnology and synthetic biology, a reliable RNA design algorithm can be crucial steps to create new biochemical components. Our lab is interested in employing various computational intelligence techniques to propose the new paradigm to help with the RNA design problem. Recently, we have designed an algorithm SIMARD, which is based on the simulated annealing paradigm.
structural-biology  polymer-folding  biochemistry  biophysics  simulation  metaheuristics  energy-landscapes  rather-interesting  to-write-about  to-simulate  to-visualize 
13 days ago
Short How-To guides — GROMACS 2019 documentation
A number of short guides are presented here to help users getting started with simulations. More detailed tutorials are available for example at the http://www.mdtutorials.com/.
structural-biology  simulation  software  open-source  rather-interesting  to-simulate  to-write-about  consider:looking-to-see 
13 days ago
[1902.07277] A systematic classification of knotoids on the plane and on the sphere
In this paper we generate and systematically classify all prime planar knotoids with up to 5 crossings. We also extend the existing list of knotoids in S2 and add all knotoids with 6 crossings.
knot-theory  combinatorics  enumeration  rather-interesting  stamp-collecting  to-understand  to-write-about  to-simulate  consider:classification  consider:representation 
13 days ago
[1803.07114] Slipknotting in Random Diagrams
The presence of slipknots in configurations of proteins and DNA has been shown to affect their functionality, or alter it entirely. Historically, polymers are modeled as polygonal chains in space. As an alternative to space curves, we provide a framework for working with subknots inside of knot diagrams via knotoid diagrams. We prove using a pattern theorem for knot diagrams that not only are almost all knot diagrams slipknotted, almost all unknot diagrams are slipknotted. This proves in the random diagram model a conjecture yet unproven in random space curve models. We also discuss conjectures on the enumeration of knotoid diagrams.
knot-theory  combinatorics  sampling  random-walks  structural-biology  rather-interesting  theoretical-biology  to-simulate  to-write-about  consider:representation 
13 days ago
[1810.07970] Inglenook Shunting Puzzles
An inglenook puzzle is a classic shunting (switching) puzzle often found on model railway layouts. A collection of wagons sits in a fan of sidings with a limited length headshunt (lead track). The aim of the puzzle is to rearrange the wagons into a desired order (often a randomly chosen order). This article answers the question: When can you be sure this can always be done? The problem of finding a solution in a minimum number of moves is also addressed.
puzzles  mathematical-recreations  combinatorics  rather-interesting  to-write-about  to-simulate  consider:genetic-programming  consider:data-structures 
13 days ago
[1011.4034] Dense packing crystal structures of physical tetrahedra
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
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
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
"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 
13 days ago
[math/0509478] Simultaneous Diagonal Flips in Plane Triangulations
Simultaneous diagonal flips in plane triangulations are investigated. It is proved that every n-vertex triangulation with at least six vertices has a simultaneous flip into a 4-connected triangulation, and that it can be computed in O(n) time. It follows that every triangulation has a simultaneous flip into a Hamiltonian triangulation. This result is used to prove that for any two n-vertex triangulations, there exists a sequence of O(logn) simultaneous flips to transform one into the other. The total number of edges flipped in this sequence is O(n). The maximum size of a simultaneous flip is then studied. It is proved that every triangulation has a simultaneous flip of at least 1/3(n−2) edges. On the other hand, every simultaneous flip has at most n−2 edges, and there exist triangulations with a maximum simultaneous flip of 6/7(n−2) edges.
graph-theory  combinatorics  rewriting-systems  rather-interesting  proof  to-simulate  to-write-about  consider:constraint-satisfaction 
14 days ago
Facilitating Failure Swap Shops — adrianhoward.com
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 
15 days ago
Deriving Reactive from Imperative: An Introduction to Duals · Distillations
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 
17 days ago
[2001.09212] PCGRL: Procedural Content Generation via Reinforcement Learning
We investigate how reinforcement learning can be used to train level-designing agents. This represents a new approach to procedural content generation in games, where level design is framed as a game, and the content generator itself is learned. By seeing the design problem as a sequential task, we can use reinforcement learning to learn how to take the next action so that the expected final level quality is maximized. This approach can be used when few or no examples exist to train from, and the trained generator is very fast. We investigate three different ways of transforming two-dimensional level design problems into Markov decision processes and apply these to three game environments.
machine-learning  transfer-learning  generative-models  content-generation  rather-interesting  to-simulate  to-write-about  consider:feature-discovery 
17 days ago
[1804.07150] Improved Bounds for Guarding Plane Graphs with Edges
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 
17 days ago
[1808.01984] Time-Dependent Shortest Path Queries Among Growing Discs
The determination of time-dependent collision-free shortest paths has received a fair amount of attention. Here, we study the problem of computing a time-dependent shortest path among growing discs which has been previously studied for the instance where the departure times are fixed. We address a more general setting: For two given points s and d, we wish to determine the function (t) which is the minimum arrival time at d for any departure time t at s. We present a (1+ϵ)-approximation algorithm for computing (t). As part of preprocessing, we execute O(1ϵlog(rc)) shortest path computations for fixed departure times, where r is the maximum speed of the robot and c is the minimum growth rate of the discs. For any query departure time t≥0 from s, we can approximate the minimum arrival time at the destination in O(log(1ϵ)+loglog(rc)) time, within a factor of 1+ϵ of optimal. Since we treat the shortest path computations as black-box functions, for different settings of growing discs, we can plug-in different shortest path algorithms. Thus, the exact time complexity of our algorithm is determined by the running time of the shortest path computations.
computational-complexity  computational-geometry  planning  constraint-satisfaction  optimization  rather-interesting  to-understand  algorithms  to-simulate  to-write-about  consider:robustness 
17 days ago
[1809.08898] Rectilinear Shortest Paths Among Transient Obstacles
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
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
In COCOA 2015, Korman et al. studied the following geometric covering problem: given a set S of n line segments in the plane, find a minimum number of line segments such that every cell in the arrangement of the line segments is covered. Here, a line segment s covers a cell f if s is incident to f. The problem was shown to be NP-hard, even if the line segments in S are axis-parallel, and it remains NP-hard when the goal is cover the "rectangular" cells (i.e., cells that are defined by exactly four axis-parallel line segments).
In this paper, we consider the approximability of the problem. We first give a PTAS for the problem when the line segments in S are in any orientation, but we can only select the covering line segments from one orientation. Then, we show that when the goal is to cover the rectangular cells using line segments from both horizontal and vertical line segments, then the problem is APX-hard. We also consider the parameterized complexity of the problem and prove that the problem is FPT when parameterized by the size of an optimal solution. Our FPT algorithm works when the line segments in S have two orientations and the goal is to cover all cells, complementing that of Korman et al. in which the goal is to cover the "rectangular" cells.
covering-problems  computational-complexity  computational-geometry  rather-interesting  optimization  to-simulate  to-write-about 
22 days ago
[1809.10737] Plane and Planarity Thresholds for Random Geometric Graphs
A random geometric graph, G(n,r), is formed by choosing n points independently and uniformly at random in a unit square; two points are connected by a straight-line edge if they are at Euclidean distance at most r. For a given constant k, we show that n−k2k−2 is a distance threshold function for G(n,r) to have a connected subgraph on k points. Based on this, we show that n−2/3 is a distance threshold for G(n,r) to be plane, and n−5/8 is a distance threshold to be planar. We also investigate distance thresholds for G(n,r) to have a non-crossing edge, a clique of a given size, and an independent set of a given size.
graph-theory  graph-layout  sampling  probability-theory  looking-to-see  to-write-about  to-simulate  consider:planarity  random-graphs  geometric-graphs 
22 days ago
[1810.09232] On the Minimum Consistent Subset Problem
Let P be a set of n colored points in the plane. Introduced by Hart (1968), a consistent subset of P, is a set S⊆P such that for every point p in P∖S, the closest point of p in S has the same color as p. The consistent subset problem is to find a consistent subset of P with minimum cardinality. This problem is known to be NP-complete even for two-colored point sets. Since the initial presentation of this problem, aside from the hardness results, there has not been a significant progress from the algorithmic point of view. In this paper we present the following algorithmic results:
1. The first subexponential-time algorithm for the consistent subset problem.
2. An O(nlogn)-time algorithm that finds a consistent subset of size two in two-colored point sets (if such a subset exists). Towards our proof of this running time we present a deterministic O(nlogn)-time algorithm for computing a variant of the compact Voronoi diagram; this improves the previously claimed expected running time.
3. An O(nlog2n)-time algorithm that finds a minimum consistent subset in two-colored point sets where one color class contains exactly one point; this improves the previous best known O(n2) running time which is due to Wilfong (SoCG 1991).
4. An O(n)-time algorithm for the consistent subset problem on collinear points; this improves the previous best known O(n2) running time.
5. A non-trivial O(n6)-time dynamic programming algorithm for the consistent subset problem on points arranged on two parallel lines.
To obtain these results, we combine tools from planar separators, additively-weighted Voronoi diagrams with respect to convex distance functions, point location in farthest-point Voronoi diagrams, range trees, paraboloid lifting, minimum covering of a circle with arcs, and several geometric transformations.
computational-complexity  computational-geometry  algorithms  combinatorics  plane-geometry  to-simulate  to-write-about  consider:movement  consider:heuristics 
22 days ago
[1812.05125] On Graphs whose Eternal Vertex Cover Number and Vertex Cover Number Coincide
The eternal vertex cover problem is a variant of the classical vertex cover problem where a set of guards on the vertices have to be dynamically reconfigured from one vertex cover to another in every round of an attacker-defender game. The minimum number of guards required to protect a graph G from an infinite sequence of attacks is the eternal vertex cover number of G, denoted by evc(G). It is known that, given a graph G and an integer k, checking whether evc(G)≤k is NP-hard. However, it is unknown whether this problem is in NP or not. Precise value of eternal vertex cover number is known only for certain very basic graph classes like trees, cycles and grids.
For any graph G, it is known that mvc(G)≤evc(G)≤2mvc(G), where mvc(G) is the minimum vertex cover number of G. Though a characterization is known for graphs for which evc(G)=2mvc(G), a characterization of graphs for which evc(G)=mvc(G) remained open. Here, we achieve such a characterization for a class of graphs that includes chordal graphs and internally triangulated planar graphs. For some graph classes including biconnected chordal graphs, our characterization leads to a polynomial time algorithm to precisely determine evc(G) and to determine a safe strategy of guard movement in each round of the game with evc(G) guards.
The characterization also leads to NP-completeness results for the eternal vertex cover problem for some graph classes including biconnected internally triangulated planar graphs. To the best of our knowledge, these are the first NP-completeness results known for the problem for any graph class.
graph-theory  feature-construction  game-theory  rather-interesting  combinatorics  to-simulate  to-write-about  consider:rediscovery  consider:robustness 
22 days ago
[1905.00790] Minimum Ply Covering of Points with Disks and Squares
Following the seminal work of Erlebach and van Leeuwen in SODA 2008, we introduce the minimum ply covering problem. Given a set P of points and a set S of geometric objects, both in the plane, our goal is to find a subset S′ of S that covers all points of P while minimizing the maximum number of objects covering any point in the plane (not only points of P). For objects that are unit squares and unit disks, this problem is NP-hard and cannot be approximated by a ratio smaller than 2. We present 2-approximation algorithms for this problem with respect to unit squares and unit disks. Our algorithms run in polynomial time when the optimum objective value is bounded by a constant.
Motivated by channel-assignment in wireless networks, we consider a variant of the problem where the selected unit disks must be 3-colorable, i.e., colored by three colors such that all disks of the same color are pairwise disjoint. We present a polynomial-time algorithm that achieves a 2-approximate solution, i.e., a solution that is 6-colorable.
We also study the weighted version of the problem in dimension one, where P and S are points and weighted intervals on a line, respectively. We present an algorithm that solves this problem in O(n+m+M)-time where n is the number of points, m is the number of intervals, and M is the number of pairs of overlapping intervals. This repairs a solution claimed by Nandy, Pandit, and Roy in CCCG 2017.
computational-geometry  operations-research  rather-interesting  optimization  constraint-satisfaction  to-write-about  to-simulate  consider:looking-to-see  consider:performance-measures 
22 days ago
[1905.00791] Flip Distance to some Plane Configurations
We study an old geometric optimization problem in the plane. Given a perfect matching M on a set of n points in the plane, we can transform it to a non-crossing perfect matching by a finite sequence of flip operations. The flip operation removes two crossing edges from M and adds two non-crossing edges. Let f(M) and F(M) denote the minimum and maximum lengths of a flip sequence on M, respectively. It has been proved by Bonnet and Miltzow (2016) that f(M)=O(n2) and by van Leeuwen and Schoone (1980) that F(M)=O(n3). We prove that f(M)=O(nΔ) where Δ is the spread of the point set, which is defined as the ratio between the longest and the shortest pairwise distances. This improves the previous bound if the point set has sublinear spread. For a matching M on n points in convex position we prove that f(M)=n/2−1 and F(M)=(n/22); these bounds are tight.
Any bound on F(⋅) carries over to the bichromatic setting, while this is not necessarily true for f(⋅). Let M′ be a bichromatic matching. The best known upper bound for f(M′) is the same as for F(M′), which is essentially O(n3). We prove that f(M′)≤n−2 for points in convex position, and f(M′)=O(n2) for semi-collinear points.
The flip operation can also be defined on spanning trees. For a spanning tree T on a convex point set we show that f(T)=O(nlogn).
computational-geometry  graph-layout  graph-theory  heuristics  rather-interesting  to-simulate  to-write-about  consider:polygon-sampling 
22 days ago
[1905.07124] Variations of largest rectangle recognition amidst a bichromatic point set
Classical separability problem involving multi-color point sets is an important area of study in computational geometry. In this paper, we study different separability problems for bichromatic point set P=P_r\cup P_b on a plane, where Pr and Pb represent the set of n red points and m blue points respectively, and the objective is to compute a monochromatic object of the desired type and of maximum size. We propose in-place algorithms for computing (i) an arbitrarily oriented monochromatic rectangle of maximum size in R^2, (ii) an axis-parallel monochromatic cuboid of maximum size in R^3. The time complexities of the algorithms for problems (i) and (ii) are O(m(m+n)(m\sqrt{n}+m\log m+n \log n)) and O(m^3\sqrt{n}+m^2n\log n), respectively. As a prerequisite, we propose an in-place construction of the classic data structure the k-d tree, which was originally invented by J. L. Bentley in 1975. Our in-place variant of the k-d tree for a set of n points in R^k supports both orthogonal range reporting and counting query using O(1) extra workspace, and these query time complexities are the same as the classical complexities, i.e., O(n^{1-1/k}+\mu) and O(n^{1-1/k}), respectively, where \mu is the output size of the reporting query. The construction time of this data structure is O(n\log n). Both the construction and query algorithms are non-recursive in nature that do not need O(\log n) size recursion stack compared to the previously known construction algorithm for in-place k-d tree and query in it. We believe that this result is of independent interest. We also propose an algorithm for the problem of computing an arbitrarily oriented rectangle of maximum weight among a point set P=P_r \cup P_b, where each point in P_b (resp. P_r) is associated with a negative (resp. positive) real-valued weight that runs in O(m^2(n+m)\log(n+m)) time using O(n) extra space.
computational-complexity  computational-geometry  optimization  sorting  algorithms  heuristics  to-simulate  to-write-about  consider:variants 
22 days ago
[1906.11948] Packing Boundary-Anchored Rectangles and Squares
Consider a set P of n points on the boundary of an axis-aligned square Q. We study the boundary-anchored packing problem on P in which the goal is to find a set of interior-disjoint axis-aligned rectangles in Q such that each rectangle is anchored (has a corner at some point in P), each point in P is used to anchor at most one rectangle, and the total area of the rectangles is maximized. Here, a rectangle is anchored at a point p in P if one of its corners coincides with p. In this paper, we show how to solve this problem in time linear in n, provided that the points of P are given in sorted order along the boundary of Q. We also consider the problem for anchoring squares and give an O(n4)-time algorithm when the points in P lie on two opposite sides of Q.
packing  operations-research  computational-geometry  computational-complexity  algorithms  optimization  constraint-satisfaction  rather-interesting  to-write-about  to-simulate  consider:feature-discovery  consider:heuristics 
22 days ago
[1907.01617] A Short Proof of the Toughness of Delaunay Triangulations
We present a self-contained short proof of the seminal result of Dillencourt (SoCG 1987 and DCG 1990) that Delaunay triangulations, of planar point sets in general position, are 1-tough. An important implication of this result is that Delaunay triangulations have perfect matchings. Another implication of our result is a proof of the conjecture of Aichholzer et al. (2010) that at least n points are required to block any n-vertex Delaunay triangulation
computational-geometry  computational-complexity  rather-interesting  algorithms  hard-problems  feature-construction  to-simulate  to-write-about  consider:hardness-features 
22 days ago
Constructing random polygons | Proceedings of the 9th ACM SIGITE conference on Information technology education
The construction of random polygons has been used in psychological research and for the testing of algorithms. With the increased popularity of client-side vector based graphics in the web browser such as seen in Flash and SVG, as well as the newly introduced <canvas> tag in HTML5.0, the use of random shapes for creation of scenes for animation and interactive art requires the construction of random polygons. A natural question, then, is how to generate random polygons in a way which is computationally efficient (particularly in a resource limited environment such as the web browser). This paper presents a random polygon algorithm (RPA) that generates polygons that are random and representative of the class of all n-gons in O(n2logn) time. Our algorithm differs from other approaches in that the vertices are generated randomly, the algorithm is inclusive (i.e. each polygon has a non-zero probability to be constructed), and it runs efficiently in polynomial time.
probability-theory  sampling  computational-geometry  algorithms  rather-interesting  to-write-about  to-simulate 
23 days ago
CiteSeerX — RPG - Heuristics for the Generation of Random Polygons
We consider the problem of randomly generating simple and star-shaped polygons on a given set of points. This problem is of considerable importance in the practical evaluation of algorithms that operate on polygons, where it is necessary to check the correctness and to determine the actual CPU-consumption of an algorithm experimentally. Since no polynomial-time solution for the uniformly random generation of polygons is known, we present and analyze several heuristics. All heuristics described in this paper have been implemented and are part of our RandomPolygonGenerator, RPG. We have tested all heuristics, and report experimental results on their CPU-consumption, their quality, and their characteristics. RPG is publically available via http://www.cosy.sbg.ac.at/~held/projects/rpg/rpg.html. 1 Introduction In this paper 1 we deal with the random generation of simple polygons on a given set of points: Ideally, given a set S = fs 1 ; : : : ; s n g of n points, we would like to generat...
probability-theory  computational-geometry  sampling  rather-interesting  performance-measure  to-simulate  to-write-about 
23 days ago
[1706.10193] More Turán-Type Theorems for Triangles in Convex Point Sets
We study the following family of problems: Given a set of n points in convex position, what is the maximum number triangles one can create having these points as vertices while avoiding certain sets of forbidden configurations. As forbidden configurations we consider all 8 ways in which a pair of triangles in such a point set can interact. This leads to 256 extremal Turán-type questions. We give nearly tight (within a logn factor) bounds for 248 of these questions and show that the remaining 8 questions are all asymptotically equivalent to Stein's longstanding tripod packing problem.
combinatorics  enumeration  rather-interesting  plane-geometry  graph-theory  counting  to-simulate  to-write-about  related-to:triangle-hypergraphs 
25 days ago
[1812.05163] Declination as a Metric to Detect Partisan Gerrymandering
We explore the Declination, a new metric intended to detect partisan gerrymandering. We consider instances in which each district has equal turnout, the maximum turnout to minimum turnout is bounded, and turnout is unrestricted. For each of these cases, we show exactly which vote-share, seat-share pairs (V,S) have an election outcome with Declination equal to 0. We also show how our analyses can be applied to finding vote-share, seat-share pairs that are possible for nonzero Declination.
Within our analyses, we show that Declination cannot detect all forms of packing and cracking, and we compare the Declination to the Efficiency Gap. We show that these two metrics can behave quite differently, and give explicit examples of that occurring.
statistics  politics  gerrymandering  cultural-engineering  rather-interesting  performance-measure  to-write-about  to-simulate 
25 days ago
For Decades, New York's Chinatown Duped 'Slum Tourists' With Faked Danger and Depravity - Atlas Obscura
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
A prominent parameter in the context of network analysis, originally proposed by Watts and Strogatz (Collective dynamics of `small-world' networks, Nature 393 (1998) 440-442), is the clustering coefficient of a graph G. It is defined as the arithmetic mean of the clustering coefficients of its vertices, where the clustering coefficient of a vertex u of G is the relative density m(G[NG(u)])/(dG(u)2) of its neighborhood if dG(u) is at least 2, and 0 otherwise. It is unknown which graphs maximize the clustering coefficient among all connected graphs of given order and size.
We determine the maximum clustering coefficients among all connected regular graphs of a given order, as well as among all connected subcubic graphs of a given order. In both cases, we characterize all extremal graphs. Furthermore, we determine the maximum increase of the clustering coefficient caused by adding a single edge.
graph-theory  network-theory  metrics  a-picture-would-be-useful-about-now  to-write-about  to-illustrate  FFS-make-a-picture 
26 days ago
[1803.11511] Length segregation in mixtures of spherocylinders induced by imposed topological defects
We explore length segregation in binary mixtures of spherocylinders of lengths L1 and L2 with the same diameter D which are tangentially confined on a spherical surface of radius R. The orientation of spherocylinders is constrained along an externally imposed direction field on the sphere which is either along the longitude or the latitude lines of the sphere. In both situations, integer orientational defects at the poles are imposed. We show that these topological defects induce a complex segregation picture also depending on the length ratio factor γ=L2/L1 and the total packing fraction η of the spherocylinders. When the binary mixture is aligned along longitudinal lines of the sphere, shorter rods tend to accumulate at the topological defects of the polar caps whereas longer rods occupy central equatorial area of the spherical surface. In the reverse case of latitude ordering, a state can emerge where longer rods are predominantly both in the cap and in the equatorial areas and shorter rods are localized in between. As a reference situation, we consider a defect-free situation in the flat plane and do not find any length segregation there at similar γ and η, hence the segregation is purely induced by the imposed topological defects. It is also revealed that the shorter rods at γ=4 and η≥0.5 act as obstacles to the rotational relaxation of the longer rods when all orientational constraints are released.
granular-materials  mixing  self-organization  rather-interesting  physics!  simulation  looking-to-see  to-write-about  to-simulate  packing 
27 days ago
[1803.09639] On the multipacking number of grid graphs
In 2001, Erwin introduced broadcast domination in graphs. It is a variant of classical domination where selected vertices may have different domination powers. The minimum cost of a dominating broadcast in a graph G is denoted γb(G). The dual of this problem is called multipacking: a multipacking is a set M of vertices such that for any vertex v and any positive integer r, the ball of radius r around v contains at most r vertices of M . The maximum size of a multipacking in a graph G is denoted mp(G). Naturally mp(G) ≤γb(G). Earlier results by Farber and by Lubiw show that broadcast and multipacking numbers are equal for strongly chordal graphs. In this paper, we show that all large grids (height at least 4 and width at least 7), which are far from being chordal, have their broadcast and multipacking numbers equal.
graph-theory  feature-construction  rather-interesting  dynamical-systems  to-simulate  to-write-about  consider:generalizations  consider:prediction 
27 days ago
[1904.06108] The Dodecahedron as a Voronoi Cell and its (minor) importance for the Kepler conjecture
The regular dodecahedron has a 2% smaller volume than the rhombic dodecahedron which is the Voronoi cell of a fcc packing. From this point of view it seems possible that the dodecahedral aspect which is the core of the so-called dodecahedral conjecture, will play a major part for an elementary proof of the Kepler conjecture. In this paper we will show that the icosahedral configuration caused by dodecahedron leads to tetrahedra with significantly larger volume than the fcc fundamental parallelotope tessellation tetrahedra. Therefore on the basis of a tetrahedral based point of view for sphere packing densities we will demonstrate the minor importance of the dodecahedron as a Voronoi cell for the Kepler conjecture.
packing  solved-problems  rather-interesting  not-quite-solutions  optimization  to-write-about  to-simulate  a-picture-might-be-good 
27 days ago
[1712.04922] Closing the gap for pseudo-polynomial strip packing
The set of 2-dimensional packing problems builds an important class of optimization problems and Strip Packing together with 2-dimensional Bin Packing and 2-dimensional Knapsack is one of the most famous of these problems. Given a set of rectangular axis parallel items and a strip with bounded width and infinite height the objective is to find a packing of the items into the strip which minimizes the packing height. We speak of pseudo-polynomial Strip Packing if we consider algorithms with pseudo-polynomial running time with respect to the width of the strip.
It is known that there is no pseudo-polynomial algorithm for Strip Packing with a ratio better than 5/4 unless P=NP. The best algorithm so far has a ratio of (4/3+ε). In this paper, we close this gap between inapproximability result and best known algorithm by presenting an algorithm with approximation ratio (5/4+ε) and thus categorize the problem accurately. The algorithm uses a structural result which states that each optimal solution can be transformed such that it has one of a polynomial number of different forms. The strength of this structural result is that it applies to other problem settings as well for example to Strip Packing with rotations (90 degrees) and Contiguous Moldable Task Scheduling. This fact enabled us to present algorithms with approximation ratio (5/4+ε) for these problems as well.
operations-research  optimization  strip-packing  packing  numerical-methods  mathematical-programming  algorithms  computational-complexity  horse-races  to-write-about  to-simulate  consider:genetic-programming  consider:performance-measures  consider:heuristics 
27 days ago
[1802.10038] Improving OCR Accuracy on Early Printed Books by combining Pretraining, Voting, and Active Learning
We combine three methods which significantly improve the OCR accuracy of OCR models trained on early printed books: (1) The pretraining method utilizes the information stored in already existing models trained on a variety of typesets (mixed models) instead of starting the training from scratch. (2) Performing cross fold training on a single set of ground truth data (line images and their transcriptions) with a single OCR engine (OCRopus) produces a committee whose members then vote for the best outcome by also taking the top-N alternatives and their intrinsic confidence values into account. (3) Following the principle of maximal disagreement we select additional training lines which the voters disagree most on, expecting them to offer the highest information gain for a subsequent training (active learning). Evaluations on six early printed books yielded the following results: On average the combination of pretraining and voting improved the character accuracy by 46% when training five folds starting from the same mixed model. This number rose to 53% when using different models for pretraining, underlining the importance of diverse voters. Incorporating active learning improved the obtained results by another 16% on average (evaluated on three of the six books). Overall, the proposed methods lead to an average error rate of 2.5% when training on only 60 lines. Using a substantial ground truth pool of 1,000 lines brought the error rate down even further to less than 1% on average.
OCR  digital-humanities  digitization  text-processing  image-processing  machine-learning  data-cleaning  the-mangle-in-practice  modeling  rather-interesting  to-write-about  to-simulate  consider:stochastic-resonance 
27 days ago
[2001.07790] Investor Experiences and International Capital Flows
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
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
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
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
TikZJax
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
libpython-clj has opened the door for Clojure to directly interop with Python libraries. That means we can take just about any Python library and directly use it in our Clojure REPL. But what about matplotlib?

Matplotlib.pyplot is a standard fixture in most tutorials and python data science code. How do we interop with a python graphics library?
python  Clojure  interoperability  library  to-use  to-try  to-write-about  consider:ClojureScript 
4 weeks ago
[1804.02385] The chromatic number of the plane is at least 5
We present a family of finite unit-distance graphs in the plane that are not 4-colourable, thereby improving the lower bound of the Hadwiger-Nelson problem. The smallest such graph that we have so far discovered has 1581 vertices.
open-questions  coloring-problems  rather-interesting  counterexamples  to-write-about  to-simulate  consider:genetic-programming  consider:density-of-points 
4 weeks ago
The Right Stuff - Futility Closet
Take any two rational numbers whose product is 2, and add 2 to each. The results are the legs of a right triangle with rational sides.
plane-geometry  generator  heuristics  rather-interesting  to-write-about  to-simulate  consider:generalizations  consider:genetic-programming 
4 weeks ago
[1702.08066] On the Classification and Algorithmic Analysis of Carmichael Numbers
In this paper, we study the properties of Carmichael numbers, false positives to several primality tests. We provide a classification for Carmichael numbers with a proportion of Fermat witnesses of less than 50%, based on if the smallest prime factor is greater than a determined lower bound. In addition, we conduct a Monte Carlo simulation as part of a probabilistic algorithm to detect if a given composite number is Carmichael. We modify this highly accurate algorithm with a deterministic primality test to create a novel, more efficient algorithm that differentiates between Carmichael numbers and prime numbers.
number-theory  primes  rather-interesting  feature-construction  classification  tricky-cases  edge-cases  algorithms  performance-measure  to-simulate  to-write-about  consider:classification  computational-complexity 
4 weeks ago
[1605.04300] On the Circle Covering Theorem by A. W. Goodman and R. E. Goodman
In 1945, A. W. Goodman and R. E. Goodman proved the following conjecture by P. Erdős: Given a family of (round) disks of radii r1, …, rn in the plane it is always possible to cover them by a disk of radius R=∑ri, provided they cannot be separated into two subfamilies by a straight line disjoint from the disks. In this note we show that essentially the same idea may work for different analogues and generalizations of their result. In particular, we prove the following: Given a family of positive homothetic copies of a fixed convex body K⊂ℝd with homothety coefficients τ1,…,τn>0 it is always possible to cover them by a translate of d+12(∑τi)K, provided they cannot be separated into two subfamilies by a hyperplane disjoint from the homothets.
covering-problems  plane-geometry  rather-interesting  to-simulate  to-write-about  proof  consider:looking-to-see  consider:robustness  consider:feature-discovery 
4 weeks ago
[1806.06751] Entropy of hard square lattice gas with $k$ distinct species of particles: coloring problems and vertex models
Coloring the faces of 2-dimensional square lattice with k distinct colors such that no two adjacent faces have the same color is considered by establishing connection between the k coloring problem and a generalized vertex model. Associating the colors with k distinct species of particles with infinite repulsive force between nearest neighbors of the same type and zero chemical potential μ associated with each species, the number of ways [W(k)]N for large N is related to the entropy of the {\it{hard square lattice gas}} at close packing of the lattice, where N is the number of lattice sites. We discuss the evaluation of W(k) using transfer matrix method with non-periodic boundary conditions imposed on at least one dimension and show the characteristic Toeplitz block structure of the transfer matrix. Using this result, we present some analytical calculations for non-periodic models that remain finite in one dimension. The case k=3 is found to approach the exact result obtained by Lieb for the residual entropy of ice with periodic boundary conditions. Finally, we show, by explicit calculation of the contribution of subgraphs and the series expansion of W(k), that the genenralized Pauling type estimate(which is based on mean field approximation) dominates at large values of k. We thus also provide an alternative series expansion for the chromatic polynomial of a regular square graph.
graph-theory  graph-coloring  algorithms  parallel  distributed-processing  cellular-automata  rather-interesting  to-simulate  to-write-about  consider:constraint-satisfaction  consider:rules-variants 
4 weeks ago
[1012.0369] Jammed particulate systems are inherently nonharmonic
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
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
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 
4 weeks ago
[1501.04472] Local analysis of the history dependence in tetrahedra packings
The mechanical properties of a granular sample depend frequently on the way the packing was prepared. However, is not well understood which properties of the packing store this information. Here we present an X-ray tomography study of three pairs of tetrahedra packings prepared with three different tapping protocols. The packings in each pair differs in the number of mechanical constraints C imposed on the particles by their contacts, while their bulk volume fraction ϕglobal is approximately the same. We decompose C into the contributions of the three different contact types possible between tetrahedra -- face-to-face (F2F), edge-to-face (E2F), and point contacts -- which each fix a different amount of constraints. We then perform a local analysis of the contact distribution by grouping the particles together according to their individual volume fraction ϕlocal computed from a Voronoi tessellation. We find that in samples which have been tapped sufficiently long the number of F2F contacts becomes an universal function of ϕlocal. In contrast the number of E2F and point contacts varies with the applied tapping protocol. Moreover, we find that the anisotropy of the shape of the Voronoi cells depends on the tapping protocol. This behavior differs from spheres and ellipsoids and posses a significant constraint for any mean-field approach to tetrahedra packings.
granular-materials  packing  physics!  experiment  looking-to-see  rather-interesting  condensed-matter  to-write-about  to-simulate  consider:matter.js  consider:2d 
4 weeks ago
Stanford CoreNLP – Natural language software | Stanford CoreNLP
Stanford CoreNLP provides a set of human language technology tools. It can give the base forms of words, their parts of speech, whether they are names of companies, people, etc., normalize dates, times, and numeric quantities, mark up the structure of sentences in terms of phrases and syntactic dependencies, indicate which noun phrases refer to the same entities, indicate sentiment, extract particular or open-class relations between entity mentions, get the quotes people said, etc.
natural-language-processing  library  Clojure  to-understand  to-use  to-write-about  notesapp 
4 weeks ago
« earlier      
per page:    204080120160

Copy this bookmark:





to read