12448
Alignment-based genetic programming for real life applications - ScienceDirect
A recent discovery has attracted the attention of many researchers in the field of genetic programming: given individuals with particular characteristics of alignment in the error space, called optimally aligned, it is possible to reconstruct a globally optimal solution. Furthermore, recent preliminary experiments have shown that an indirect search consisting of looking for optimally aligned individuals can have benefits in terms of generalization ability compared to a direct search for optimal solutions. For this reason, defining genetic programming systems that look for optimally aligned individuals is becoming an ambitious and important objective. Nevertheless, the systems that have been introduced so far present important limitations that make them unusable in practice, particularly for complex real-life applications. In this paper, we overcome those limitations, and we present the first usable alignment-based genetic programming system, called nested alignment genetic programming (NAGP). The presented experimental results show that NAGP is able to outperform two of the most recognized state-of-the-art genetic programming systems on four complex real-life applications. The predictive models generated by NAGP are not only more effective than the ones produced by the other studied methods but also significantly smaller and thus more manageable and interpretable.
yesterday
Indianapolis Collected: New Year's Eve at the Boom Boom Room - Historic Indianapolis | All Things Indianapolis History
The Martinique poked fun at the city’s fine-dining establishments in its souvenir memo (below), which featured delicacies such as Virgin Mermaid on Halfshell, Young Whale Stuffed with New Buick, Saddle of Mule (without stirrups), and Ice Cream with Mustard. All were available either a la carte or by bus.
8 days ago
[1807.09977] Colored range closest-pair problem under general distance functions
The range closest-pair (RCP) problem is the range-search version of the classical closest-pair problem, which aims to store a given dataset of points in some data structure such that when a query range X is specified, the closest pair of points contained in X can be reported efficiently. A natural generalization of the RCP problem is the {colored range closest-pair} (CRCP) problem in which the given data points are colored and the goal is to find the closest {bichromatic} pair contained in the query range. All the previous work on the RCP problem was restricted to the uncolored version and the Euclidean distance function. In this paper, we make the first progress on the CRCP problem. We investigate the problem under a general distance function induced by a monotone norm; in particular, this covers all the Lp-metrics for p>0 and the L∞-metric. We design efficient (1+ε)-approximate CRCP data structures for orthogonal queries in ℝ2, where ε>0 is a pre-specified parameter. The highlights are two data structures for answering rectangle queries, one of which uses O(ε−1nlog4n) space and O(log4n+ε−1log3n+ε−2logn) query time while the other uses O(ε−1nlog3n) space and O(log5n+ε−1log4n+ε−2log2n) query time. In addition, we also apply our techniques to the CRCP problem in higher dimensions, obtaining efficient data structures for slab, 2-box, and 3D dominance queries. Before this paper, almost all the existing results for the RCP problem were achieved in ℝ2.
computational-complexity  computational-geometry  algorithms  horse-races  to-write-about  nudge-targets  consider:looking-to-see  consider:relaxations  consider:representation
12 days ago
[1209.5958] Diffusion-limited aggregation with polygon particles
Diffusion-limited aggregation (DLA) assumes that particles perform pure random walk at a finite temperature and aggregate when they come close enough and stick together. Although it is well known that DLA in two dimensions results in a ramified fractal structure, how the particle shape influences the formed morphology is still unclear. In this work, we perform the off-lattice two-dimensional DLA simulations with different particle shapes of triangle, quadrangle, pentagon, hexagon, and octagon, respectively, and compared with the results for circular particles. Our results indicate that different particle shapes only change the local structure, but have no effects on the global structure of the formed fractal cluster. The local compactness decreases as the number of polygon edges increases.
self-organization  DLA  fractals  looking-to-see  to-simulate  consider:locking-rules
12 days ago
[1704.00454] Clustering in Hilbert simplex geometry
Clustering categorical distributions in the probability simplex is a fundamental task met in many applications dealing with normalized histograms. Traditionally, the differential-geometric structures of the probability simplex have been used either by (i) setting the Riemannian metric tensor to the Fisher information matrix of the categorical distributions, or (ii) defining the dualistic information-geometric structure induced by a smooth dissimilarity measure, the Kullback-Leibler divergence. In this work, we introduce for this clustering task a novel computationally-friendly framework for modeling the probability simplex termed {\em Hilbert simplex geometry}. In the Hilbert simplex geometry, the distance function is described by a polytope. We discuss the pros and cons of those different statistical modelings, and benchmark experimentally these geometries for center-based k-means and k-center clusterings. We show that Hilbert metric in the probability simplex satisfies the property of information monotonicity. Furthermore, since a canonical Hilbert metric distance can be defined on any bounded convex subset of the Euclidean space, we also consider Hilbert's projective geometry of the elliptope of correlation matrices and study its clustering performances.
clustering  representation  categorical-variables  rather-interesting  machine-learning  to-understand
12 days ago
[1802.04148] On Dendrites Generated By Symmetric Polygonal Systems: The Case of Regular Polygons
We define G-symmetric polygonal systems of similarities and study the properties of symmetric dendrites, which appear as their attractors. This allows us to find the conditions under which the attractor of a zipper becomes a dendrite.
fractals  geometry  nonlinear-dynamics  rather-interesting  purdy-pitchers
12 days ago
[1312.1001] Optimal detection of intersections between convex polyhedra
For a polyhedron P in ℝd, denote by |P| its combinatorial complexity, i.e., the number of faces of all dimensions of the polyhedra. In this paper, we revisit the classic problem of preprocessing polyhedra independently so that given two preprocessed polyhedra P and Q in ℝd, each translated and rotated, their intersection can be tested rapidly.
For d=3 we show how to perform such a test in O(log|P|+log|Q|) time after linear preprocessing time and space. This running time is the best possible and improves upon the last best known query time of O(log|P|log|Q|) by Dobkin and Kirkpatrick (1990).
We then generalize our method to any constant dimension d, achieving the same optimal O(log|P|+log|Q|) query time using a representation of size O(|P|⌊d/2⌋+ε) for any ε>0 arbitrarily small. This answers an even older question posed by Dobkin and Kirkpatrick 30 years ago.
In addition, we provide an alternative O(log|P|+log|Q|) algorithm to test the intersection of two convex polygons P and Q in the plane.
computational-complexity  computational-geometry  algorithms  rather-interesting  consider:performance-measures  to-write-about  nudge-targets
12 days ago
Meet Clojure MXNet - NDArray - Squid's Blog
This is the beginning of a series of blog posts to get to know the Apache MXNet Deep Learning project and the new Clojure language binding clojure-package
MXNet is a first class, modern deep learning library that AWS has officially picked as its chosen library. It supports multiple languages on a first class basis and is incubating as an Apache project.
The motivation for creating a Clojure package is to be able to open the deep learning library to the Clojure ecosystem and build bridges for future development and innovation for the community. It provides all the needed tools including low level and high level apis, dynamic graphs, and things like GAN and natural language support.
Clojure  deep-learning  library  to-understand  to-write-about  neural-networks
15 days ago
[1811.09989] The dry history of liquid computers
A liquid can be used to represent signals, actuate mechanical computing devices and to modify signals via chemical reactions. We give a brief overview of liquid based computing devices developed over hundreds of years. These include hydraulic calculators, fluidic computers, micro-fluidic devices, droplets, liquid marbles and reaction-diffusion chemical computers.
15 days ago
[1806.04609] Streaming PCA and Subspace Tracking: The Missing Data Case
For many modern applications in science and engineering, data are collected in a streaming fashion carrying time-varying information, and practitioners need to process them with a limited amount of memory and computational resources in a timely manner for decision making. This often is coupled with the missing data problem, such that only a small fraction of data attributes are observed. These complications impose significant, and unconventional, constraints on the problem of streaming Principal Component Analysis (PCA) and subspace tracking, which is an essential building block for many inference tasks in signal processing and machine learning. This survey article reviews a variety of classical and recent algorithms for solving this problem with low computational and memory complexities, particularly those applicable in the big data regime with missing data. We illustrate that streaming PCA and subspace tracking algorithms can be understood through algebraic and geometric perspectives, and they need to be adjusted carefully to handle missing data. Both asymptotic and non-asymptotic convergence guarantees are reviewed. Finally, we benchmark the performance of several competitive algorithms in the presence of missing data for both well-conditioned and ill-conditioned systems.
online-learning  algorithms  machine-learning  data-balancing  streaming-algorithms  performance-measure  rather-interesting  to-write-about  to-generalize  consider:multiobjective-versions
15 days ago
[1804.00746] The simple essence of automatic differentiation
Automatic differentiation (AD) in reverse mode (RAD) is a central component of deep learning and other uses of large-scale optimization. Commonly used RAD algorithms such as backpropagation, however, are complex and stateful, hindering deep understanding, improvement, and parallel execution. This paper develops a simple, generalized AD algorithm calculated from a simple, natural specification. The general algorithm is then specialized by varying the representation of derivatives. In particular, applying well-known constructions to a naive representation yields two RAD algorithms that are far simpler than previously known. In contrast to commonly used RAD implementations, the algorithms defined here involve no graphs, tapes, variables, partial derivatives, or mutation. They are inherently parallel-friendly, correct by construction, and usable directly from an existing programming language with no need for new data types or programming style, thanks to use of an AD-agnostic compiler plugin.
computer-science  differentiation  gradients  numerical-methods  machine-learning  algorithms  category-theory  rather-interesting  to-understand
15 days ago
The American Scholar: A Pleasure to Read You - Arthur Krystal
Something, I fear, goes missing when the historical particularity of style is dropped from the curriculum. That aesthetic exchange whereby writers strive to outdo their precursors (vividly traced by Harold Bloom and W. Jackson Bate) has taken a back seat to more socially pressing concerns. Although serious writers continue to write good books, interesting books, unusual books, literature itself is now viewed primarily as a cultural artifact defined by limitations of sex, race, and class. It acts more as a critique of society than as a gloss on previous work. To take a well-worn example: Joseph Conrad’s Heart of Darkness is invariably seen as a racial and colonialist work of fiction. No one is saying that the story is not well told. Nonetheless, it is bad in a way that is more important than the ways it is good.

More recently, the novelist Jesmyn Ward, writing in The New York Times Book Review, gracefully extolled the virtues of The Great Gatsby while focusing on Gatsby’s exclusionary status as though it were the novel’s most important feature: “the idea most invisible to [her] as a young reader [was] that the very social class that embodied the dream Gatsby wanted for himself was predicated on exclusion. That Gatsby was doomed from the start. He’d been born on the outside; he would die on the outside.” But what reader past the age of 14 doesn’t get this? It’s not that Ward is wrong; it’s just that harping on James Gatz’s displacement conveniently lines up with our culture’s need to condemn privilege.

I may be overreaching, but this emphasis on the socioeconomic aspect of the novel suggests that we’re in danger of losing a category of pleasure. If what is most important in a book is its attitude toward imperialism or class or injustice, then we automatically consign good writing to secondary status. Gatsby is great not because James Gatz is an interloper who exposes class prejudice, but because Fitzgerald learned from Conrad (as well as from Booth Tarkington, Sherwood Anderson, and Compton Mackenzie). Wanting to be a great writer, he had to be his own writer, and with Gatsby, he aspired to “write something new—something extraordinary and beautiful and simple + intricately patterned.” And part of the pleasure of reading Gatsby is discovering where and how he differed from the writers he admired.
15 days ago
How Machine Learning Found Flint’s Lead Pipes - The Atlantic
But something strange happened over the course of 2018: As more and more people had their pipes evaluated in 2018, fewer and fewer inspections were finding lead pipes. In November 2017, according to meeting notes obtained by local news outlet MLive’s Zahra Ahmad, the city’s head of public works estimated that about 10,000 of Flint’s homes still had lead pipes, roughly in line with the number other experts have floated. The new contractor hasn’t been efficiently locating those pipes: As of mid-December 2018, 10,531 properties had been explored and only 1,567 of those digs found lead pipes to replace. That’s a lead-pipe hit rate of just 15 percent, far below the 2017 mark.
machine-learning  planning  public-policy  models-and-modes  civil-engineering  failure-modes
15 days ago
[1612.07545] A Revisit of Hashing Algorithms for Approximate Nearest Neighbor Search
Approximate Nearest Neighbor Search (ANNS) is a fundamental problem in many areas of machine learning and data mining. During the past decade, numerous hashing algorithms are proposed to solve this problem. Every proposed algorithm claims outperform other state-of-the-art hashing methods. However, the evaluation of these hashing papers was not thorough enough, and those claims should be re-examined. The ultimate goal of an ANNS method is returning the most accurate answers (nearest neighbors) in the shortest time. If implemented correctly, almost all the hashing methods will have their performance improved as the code length increases. However, many existing hashing papers only report the performance with the code length shorter than 128. In this paper, we carefully revisit the problem of search with a hash index, and analyze the pros and cons of two popular hash index search procedures. Then we proposed a very simple but effective two level index structures and make a thorough comparison of eleven popular hashing algorithms. Surprisingly, the random-projection-based Locality Sensitive Hashing (LSH) is the best performed algorithm, which is in contradiction to the claims in all the other ten hashing papers. Despite the extreme simplicity of random-projection-based LSH, our results show that the capability of this algorithm has been far underestimated. For the sake of reproducibility, all the codes used in the paper are released on GitHub, which can be used as a testing platform for a fair comparison between various hashing algorithms.
hashing  algorithms  approximation  dimension-reduction  representation  data-analysis  feature-extraction  nudge-targets  consider:looking-to-see  to-write-about
15 days ago
Via freedom to coercion: the emergence of costly punishment
In human societies, cooperative behaviour in joint enterprises is often enforced through institutions that impose sanctions on defectors. Many experiments on so-called public goods games have shown that in the absence of such institutions, individuals are willing to punish defectors, even at a cost to themselves. Theoretical models confirm that social norms prescribing the punishment of uncooperative behaviour are stable: once established, they prevent dissident minorities from spreading. But how can such costly punishing behaviour gain a foothold in the population? A surprisingly simple model shows that if individuals have the option to stand aside and abstain from the joint endeavour, this paves the way for the emergence and establishment of cooperative behaviour based on the punishment of defectors. Paradoxically, the freedom to withdraw from the common enterprise leads to enforcement of social norms. Joint enterprises which are compulsory rather than voluntary are less likely to lead to cooperation.
evolutionary-economics  game-theory  agent-based  sociology  commons  to-write-about
15 days ago
The Fermat primality test and the GCD test | The Math Less Traveled
In my previous post we proved that if shares a nontrivial common factor with , then , and this in turn proves that is not prime (by Fermat’s Little Theorem).

But wait a minute, this is silly: if shares a common factor with , then we don’t need anything as complex as Fermat’s Little Theorem to figure out that is not prime! All we have to do is compute using the Euclidean Algorithm, and when we find out that the result isn’t , we can immediately conclude that isn’t prime since it has a nontrivial divisor.
algorithms  number-theory  rather-interesting  nudge-targets  consider:looking-to-see
15 days ago
Tanya Khovanova's Math Blog » Blog Archive » 3-Symmetric Permutations
I want to study patterns inside permutations. Consider a permutation of size 4: 1432. Today I am excited by ordered subset of size 3 inside this permutation. For example, I can drop the last number and look at 143. The ordering in 143 is the same as in 132, or, as a mathematician would say, 143 is order-isomorphic to 132. In my example of 1432, I have four subsets depending on which number I remove: 432 is order-isomorphic to 321, while 132, 142 and 143 are all order-isomorphic to 132.

The density of a pattern 123 in the permutation 1432 is the ratio of subsets of size 3 that are order-isomorphic to 123 to all subsets of size 3. As I already calculated, the density of 123 in 1432 is zero, while the density of 321 is 1/4, and the density of 132 is 3/4.
permutations  feature-construction  combinatorics  mathematical-recreations  conjecture  to-write-about
15 days ago
Tanya Khovanova's Math Blog » Blog Archive » 3-Symmetric Graphs
In my previous post I described 3-symmetric permutations. Now I want to define 3-symmetric graphs.

A reminder: a k-symmetric permutation is such that the densities of all permutations of size k in it are the same. In particular a 2-symmetric permutation has the same number of inversions and non-inversions. How do we translate this to graphs? I call a graph 2-symmetric if it has the same number of edges as non-edges. 2-symmetric graphs are easy to construct, but they only exist if the number of vertices, n, is such that n choose 2 is even. The simplest non-trivial examples are graphs with 4 vertices and three edges.
graph-theory  feature-construction  rather-interesting  mathematical-recreations
15 days ago
[1807.04271] A quantum-inspired classical algorithm for recommendation systems
A recommendation system suggests products to users based on data about user preferences. It is typically modeled by a problem of completing an m×n matrix of small rank k. We give the first classical algorithm to produce a recommendation in O(poly(k)polylog(m,n)) time, which is an exponential improvement on previous algorithms that run in time linear in m and n. Our strategy is inspired by a quantum algorithm by Kerenidis and Prakash: like the quantum algorithm, instead of reconstructing a user's full list of preferences, we only seek a randomized sample from the user's preferences. Our main result is an algorithm that samples high-weight entries from a low-rank approximation of the input matrix in time independent of m and n, given natural sampling assumptions on that input matrix. As a consequence, we show that Kerenidis and Prakash's quantum machine learning (QML) algorithm, one of the strongest candidates for provably exponential speedups in QML, does not in fact give an exponential speedup over classical algorithms.
recommendations  algorithms  quantum-computing  classical-computing  rather-interesting  information-theory  to-understand
15 days ago
Your friends are more popular than you. In the year 1991, the sociologist Scott L. Feld made an interesting discovery. He realized that on average, most individual’s friends have more friends than the individual. This phenomenon is called the friendship paradox. [1] In this article, we describe the friendship paradox using graph theory, provide a mathematical proof, and give examples for possible applications. Furthermore, we talk about its applications in monitoring disease outbreaks.
17 days ago
[1703.07054] Name-free combinators for concurrency
Yoshida demonstrated how to eliminate the bound names coming from the input prefix in the asynchronous pi calculus, but her combinators still depend on the "new" operator to bind names. We modify Yoshida's combinators by replacing "new" and replication with reflective operators to provide the first combinator calculus with no bound names into which the asynchronous pi calculus has a faithful embedding. We also show that multisorted Lawvere theories enriched over graphs suffice to capture the operational semantics of the calculus.
π-calculus  concurrency  to-understand  distributed-processing
17 days ago
An overview of semantic image segmentation.
More specifically, the goal of semantic image segmentation is to label each pixel of an image with a corresponding class of what is being represented. Because we're predicting for every pixel in the image, this task is commonly referred to as dense prediction.
image-segmentation  image-processing  distributed-processing  rather-interesting  neural-networks  to-write-about  to-do  nudge-targets  consider:representation
17 days ago
[1811.11888] Reality Inspired Voter Models: A Mini-review
This mini-review presents extensions of the voter model that incorporate a number of plausible features of real decision-making processes of individuals. Although these generalizations are not calibrated by empirical data, the resulting dynamics are suggestive of real collective social behaviors.
collective-behavior  voting  social-networks  social-dynamics  abstraction  simulation  to-write-about  review  rather-interesting
17 days ago
StringInterpolation in Swift 5 — AttributedStrings – Crunchy Development
In the previous post, we introduced the new StringInterpolation design coming to Swift 5. In this second part, I’ll focus on one application of that new ExpressibleByStringInterpolation, to make NSAttributedString prettier.
swift  programming-language  impressive
17 days ago
[1601.05613] Partial Sum Minimization of Singular Values Representation on Grassmann Manifolds
As a significant subspace clustering method, low rank representation (LRR) has attracted great attention in recent years. To further improve the performance of LRR and extend its applications, there are several issues to be resolved. The nuclear norm in LRR does not sufficiently use the prior knowledge of the rank which is known in many practical problems. The LRR is designed for vectorial data from linear spaces, thus not suitable for high dimensional data with intrinsic non-linear manifold structure. This paper proposes an extended LRR model for manifold-valued Grassmann data which incorporates prior knowledge by minimizing partial sum of singular values instead of the nuclear norm, namely Partial Sum minimization of Singular Values Representation (GPSSVR). The new model not only enforces the global structure of data in low rank, but also retains important information by minimizing only smaller singular values. To further maintain the local structures among Grassmann points, we also integrate the Laplacian penalty with GPSSVR. An effective algorithm is proposed to solve the optimization problem based on the GPSSVR model. The proposed model and algorithms are assessed on some widely used human action video datasets and a real scenery dataset. The experimental results show that the proposed methods obviously outperform other state-of-the-art methods.
dimension-reduction  feature-selection  spatial-embedding  metrics  define-your-terms  rather-interesting  representation  to-write-about  to-simulate  consider:performance-measures  consider:data-balancing
20 days ago
[1807.05283] When Are Two Gossips the Same? Types of Communication in Epistemic Gossip Protocols
We provide an in-depth study of the knowledge-theoretic aspects of communication in so-called gossip protocols. Pairs of agents communicate by means of calls in order to spread information---so-called secrets---within the group. Depending on the nature of such calls knowledge spreads in different ways within the group. Systematizing existing literature, we identify 18 different types of communication, and model their epistemic effects through corresponding indistinguishability relations. We then provide a classification of these relations and show its usefulness for an epistemic analysis in presence of different communication types. Finally, we explain how to formalise the assumption that the agents have common knowledge of a distributed epistemic gossip protocol.
agent-based  graph-theory  communication  artificial-life  collective-behavior  simulation  define-your-terms  rather-interesting  to-simulate
20 days ago
[1808.00722] On the Harborth constant of $C_3 oplus C_{3n}$
For a finite abelian group (G,+,0) the Harborth constant 𝗀(G) is the smallest integer k such that each squarefree sequence over G of length k, equivalently each subset of G of cardinality at least k, has a subsequence of length exp(G) whose sum is 0. In this paper, it is established that 𝗀(G)=3n+3 for prime n≠3 and 𝗀(C3⊕C9)=13.
20 days ago
[1712.02950] CycleGAN, a Master of Steganography
CycleGAN (Zhu et al. 2017) is one recent successful approach to learn a transformation between two image distributions. In a series of experiments, we demonstrate an intriguing property of the model: CycleGAN learns to "hide" information about a source image into the images it generates in a nearly imperceptible, high-frequency signal. This trick ensures that the generator can recover the original sample and thus satisfy the cyclic consistency requirement, while the generated image remains realistic. We connect this phenomenon with adversarial attacks by viewing CycleGAN's training procedure as training a generator of adversarial examples and demonstrate that the cyclic consistency loss causes CycleGAN to be especially vulnerable to adversarial attacks.
21 days ago
[1605.03502] A solution to the reversible embedding problem for finite Markov chains
The embedding problem for Markov chains is a famous problem in probability theory and only partial results are available up till now. In this paper, we propose a variant of the embedding problem called the reversible embedding problem which has a deep physical and biochemical background and provide a complete solution to this new problem. We prove that the reversible embedding of a stochastic matrix, if it exists, must be unique. Moreover, we obtain the sufficient and necessary conditions for the existence of the reversible embedding and provide an effective method to compute the reversible embedding. Some examples are also given to illustrate the main results of this paper.
inverse-problems  Markov-chains  probability-theory  algorithms  nudge-targets
21 days ago
[1808.02679] Age of Information Upon Decisions
We consider an M/M/1 update-and-decide system where Poisson distributed decisions are made based on the received updates. We propose to characterize the freshness of the received updates at decision epochs with Age upon Decisions (AuD). Under the first-come-first-served policy (FCFS), the closed form average AuD is derived. We show that the average AuD of the system is determined by the arrival rate and the service rate, and is independent of the decision rate. Thus, merely increasing the decision rate does not improve the timeliness of decisions. Nevertheless, increasing the arrival rate and the service rate simultaneously can decrease the average AuD efficiently.
queueing-theory  information-theory  planning  simulation  rather-interesting  to-write-about
21 days ago
"Created Facts and the Flawed Ontology of Copyright Law" by Justin Hughes
law  pragmatism  philosophy  rather-interesting  to-understand
21 days ago
[1809.07481] $L_1$ Shortest Path Queries in Simple Polygons
Let P be a simple polygon of n vertices. We consider two-point L1 shortest path queries in P. We build a data structure of O(n) size in O(n) time such that given any two query points s and t, the length of an L1 shortest path from s to t in P can be computed in O(logn) time, or in O(1) time if both s and t are vertices of P, and an actual shortest path can be output in additional linear time in the number of edges of the path. To achieve the result, we propose a mountain decomposition of simple polygons, which may be interesting in its own right. Most importantly, our approach is much simpler than the previous work on this problem.
computational-geometry  planning  algorithms  computational-complexity  representation  to-write-about  consider:feature-discovery
22 days ago
[1603.02853] A Time-Space Trade-off for Computing the k-Visibility Region of a Point in a Polygon
Let P be a simple polygon with n vertices, and let q∈P be a point in P. Let k∈{0,…,n−1}. A point p∈P is k-visible from q if and only if the line segment pq crosses the boundary of P at most k times. The k-visibility region of q in P is the set of all points that are k-visible from q. We study the problem of computing the k-visibility region in the limited workspace model, where the input resides in a random-access read-only memory of O(n) words, each with Ω(logn) bits. The algorithm can read and write O(s) additional words of workspace, where s∈ℕ is a parameter of the model. The output is written to a write-only stream.
Given a simple polygon P with n vertices and a point q∈P, we present an algorithm that reports the k-visibility region of q in P in O(cn/s+clogs+min{⌈k/s⌉n,nloglogsn}) expected time using O(s) words of workspace. Here, c∈{1,…,n} is the number of critical vertices of P for q where the k-visibility region of q may change. We generalize this result for polygons with holes and for sets of non-crossing line segments.
computational-geometry  plane-geometry  algorithms  polygon-visibility  computational-complexity  nudge-targets
22 days ago
CTK Insights » Blog Archive A pizza with a hole - CTK Insights
Now we are in a position to tackle the problem from the Crux. Any line through the center of the rectangular pizza divides it into equal parts. One of these lines stands out. It's the one that divides into equal parts the circular hole, that's the line that passes through the hole's center. Thus to solve the problem we cut through the centers of the rectangle and that of the hole.

But that's not the only solution. In fact there are infinitely many more, although to find any of these in a constructive manner is rather difficult, if not impossible.
mathematical-recreations  plane-geometry  rather-interesting  open-questions  nudge-targets  consider:looking-to-see  compass-and-straightedge
22 days ago
[PDF] Captivating algorithms: Recommender systems as traps
In this article, I describe how it came to be that people like Mike explain the purpose of their work as “hooking” users. Between 2011 and 2016, I conducted fieldwork with the developers of algorithmic music recommender systems across the US. What were these systems for, and how did their makers decide whether they worked? In settings ranging from university labs to corporate offices, one paradigmatic answer emerged above the others: recommender systems retained users on platforms, caught their attention, and helped companies capture market share.

Metaphors like these, which figured users as prey and recommender systems as devices for catching them, were surprisingly common. Algorithmic recommendation, it seemed, was a trap. Following the anthropologist’s prerogative to take our interlocutors more literally and more figuratively than they take themselves, I pursue here the consequences of this comparison. Drawing on the anthropology of animal trapping, I place recommender systems in unusual company—not among artificial intelligences and machine learners, but hidden spears and thorn-ribbed baskets. This is, assuredly, not what people meant when they said they wanted to capture users. However, traps offer a powerful vocabulary for articulating sociotechnical concerns, and thinking with traps gives purchase on vexing questions about the relationships among culture, technology, and ethics.
recommendations  machine-learning  marketing  feedback  cultural-engineering  cultural-norms  the-Data-Pageant-effect  to-write-about
22 days ago
Supermultiplexed optical imaging and barcoding with engineered polyynes | Nature Methods
Optical multiplexing has a large impact in photonics, the life sciences and biomedicine. However, current technology is limited by a 'multiplexing ceiling' from existing optical materials. Here we engineered a class of polyyne-based materials for optical supermultiplexing. We achieved 20 distinct Raman frequencies, as 'Carbon rainbow', through rational engineering of conjugation length, bond-selective isotope doping and end-capping substitution of polyynes. With further probe functionalization, we demonstrated ten-color organelle imaging in individual living cells with high specificity, sensitivity and photostability. Moreover, we realized optical data storage and identification by combinatorial barcoding, yielding to our knowledge the largest number of distinct spectral barcodes to date. Therefore, these polyynes hold great promise in live-cell imaging and sorting as well as in high-throughput diagnostics and screening.
materials-science  nanotechnology  indistinguishable-from-magic  molecular-design  molecular-biology  to-write-about  rather-interesting
22 days ago
The Language of Neoliberal Education
The culture of manufactured illiteracy is also reproduced through a media apparatus that trades in illusions and the spectacle of violence. Under these circumstances, illiteracy becomes the norm and education becomes central to a version of neoliberal zombie politics that functions largely to remove democratic values, social relations, and compassion from the ideology, policies and commanding institutions that now control American society. In the age of manufactured illiteracy, there is more at work than simply an absence of learning, ideas or knowledge. Nor can the reign of manufactured illiteracy be solely attributed to the rise of the new social media, a culture of immediacy, and a society that thrives on instant gratification. On the contrary, manufactured illiteracy is political and educational project central to a right-wing corporatist ideology and set of policies that work aggressively to depoliticize people and make them complicitous with the neoliberal and racist political and economic forces that impose misery and suffering upon their lives. There is more at work here than what Ariel Dorfman calls a “felonious stupidity,” there is also the workings of a deeply malicious form of 21stcentury neoliberal fascism and a culture of cruelty in which language is forced into the service of violence while waging a relentless attack on the ethical imagination and the notion of the common good. In the current historical moment illiteracy and ignorance offer the pretense of a community in doing so has undermined the importance of civic literacy both in higher education and the larger society.
neoliberalism  fascism  corporatism  education  nodding
22 days ago
@dynamicCallable: Unix Tools as Swift Functions – The Always Right Institute – Almost always sometimes definitely right.
A new feature in Swift 5 are Dynamic Callable’s. We combine this with the related Dynamic Member Lookup feature to expose the filesystem and Unix shell commands as regular Swift objects and functions.

Wait what?!
swift  programming-language  library  rather-interesting  to-do
22 days ago
Polygenic scores and tea drinking | gcbias
Some of these complications are perhaps best illustrated with a toy example. Say we perform a GWAS of the amount of tea that individuals in the UK drink (e.g. in the UK Biobank). On the basis of this tea GWAS, someone (let’s call him Bob) could claim that we could learn about France-UK differences in tea consumption by just counting up the average number of alleles for tea preference that individuals in the UK and France carry. If the British, overall, are more likely to have alleles that increase tea consumption than French people, then Bob might say that we have demonstrated that the difference between French and UK people’s preference for tea is in part genetic. Bob would assure us that these alleles are polymorphic in both countries, and that both environment and culture plays a role. He would further reassure us that there’ll be an overlapping distribution of tea drinking preferences in both countries, so he’s not saying that all British people drink more tea for genetic reasons. He’ll tell us he’s simply interested in showing that the average difference in tea consumption is partly genetic.
genetics  bioinformatics  GWAS  good-example  nature-and-nurture-sittin-in-a-tree  population-biology  cultural-norms
23 days ago
[1808.08697] Universal groups of cellular automata
We prove that the group of reversible cellular automata (RCA), on any alphabet A, contains a perfect subgroup generated by six involutions which contains an isomorphic copy of every finitely-generated group of RCA on any alphabet B. This result follows from a case study of groups of RCA generated by symbol permutations and partial shifts with respect to a fixed Cartesian product decomposition of the alphabet. For prime alphabets, we show that this group is virtually cyclic, and that for composite alphabets it is non-amenable. For alphabet size four, it is a linear group. For non-prime non-four alphabets, it contains copies of all finitely-generated groups of RCA. We also obtain that RCA of biradius one on all large enough alphabets generate copies of all finitely-generated groups of RCA. We ask a long list of questions.
group-theory  cellular-automata  rewriting-systems  reversible  open-questions  to-write-about  to-understand
25 days ago
Laudator Temporis Acti: The Higher Naiveté
And so there is this critical school that says, "I won't believe anything unless it is proven to me." At the other extreme, there's me, the most gullible historian imaginable. My principle is this. I believe anything written in ancient Latin or Greek unless I can't. Now, things that prevent me from believing what I read are that they are internally contradictory, or what they say is impossible, or different ones contradict each other and they can't both be right. So, in those cases I abandon the ancient evidence. Otherwise, you've got to convince me that they’re not true.
scholarship  criticism  open-mindedness  history  history-is-a-feature-not-a-bug  nicely-put
25 days ago
[1711.09442] Quantum Artificial Life in an IBM Quantum Computer
We present the first experimental realization of a quantum artificial life algorithm in a quantum computer. The quantum biomimetic protocol encodes tailored quantum behaviors belonging to living systems, namely, self-replication, mutation, interaction between individuals, and death, into the cloud quantum computer IBM ibmqx4. In this experiment, entanglement spreads throughout generations of individuals, where genuine quantum information features are inherited through genealogical networks. As a pioneering proof-of-principle, experimental data fits the ideal model with accuracy. Thereafter, these and other models of quantum artificial life, for which no classical device may predict its quantum supremacy evolution, can be further explored in novel generations of quantum computers. Quantum biomimetics, quantum machine learning, and quantum artificial intelligence will move forward hand in hand through more elaborate levels of quantum complexity.
artificial-life  simulation  quantum  uh-huh
25 days ago
[1712.07673] Self-attracting self-avoiding walk
This article is concerned with self-avoiding walks (SAW) on ℤd that are subject to a self-attraction. The attraction, which rewards instances of adjacent parallel edges, introduces difficulties that are not present in ordinary SAW. Ueltschi has shown how to overcome these difficulties for sufficiently regular infinite-range step distributions and weak self-attractions. This article considers the case of bounded step distributions. For weak self-attractions we show that the connective constant exists, and, in d≥5, carry out a lace expansion analysis to prove the mean-field behaviour of the critical two-point function, hereby addressing a problem posed by den Hollander.
lattice-polymers  random-walks  combinatorics  enumeration  probability-theory  to-write-about  to-simulate  consider:performance-measures
26 days ago
[1808.09032] An upper bound on the number of self-avoiding polygons via joining
For d≥2 and n∈ℕ even, let pn=pn(d) denote the number of length n self-avoiding polygons in ℤd up to translation. The polygon cardinality grows exponentially, and the growth rate limn∈2ℕp1/nn∈(0,∞) is called the connective constant and denoted by μ. Madras [J. Statist. Phys. 78 (1995) no. 3--4, 681--699] has shown that pnμ−n≤Cn−1/2 in dimension d=2. Here we establish that pnμ−n≤n−3/2+o(1) for a set of even n of full density when d=2. We also consider a certain variant of self-avoiding walk and argue that, when d≥3, an upper bound of n−2+d−1+o(1) holds on a full density set for the counterpart in this variant model of this normalized polygon cardinality.
combinatorics  enumeration  random-walks  lattice-polymers  probability-theory  limits
26 days ago
[1806.04129] Angels' staircases, Sturmian sequences, and trajectories on homothety surfaces
A homothety surface can be assembled from polygons by identifying their edges in pairs via homotheties, which are compositions of translation and scaling. We consider linear trajectories on a 1-parameter family of genus-2 homothety surfaces. The closure of a trajectory on each of these surfaces always has Hausdorff dimension 1, and contains either a closed loop or a lamination with Cantor cross-section. Trajectories have cutting sequences that are either eventually periodic or eventually Sturmian. Although no two of these surfaces are affinely equivalent, their linear trajectories can be related directly to those on the square torus, and thence to each other, by means of explicit functions. We also briefly examine two related families of surfaces and show that the above behaviors can be mixed; for instance, the closure of a linear trajectory can contain both a closed loop and a lamination.
plane-geometry  geometry  algebra  continued-fractions  fractals  to-understand  topology  several-overlaps
26 days ago
[1706.08105] Compatible 4-Holes in Point Sets
Counting interior-disjoint empty convex polygons in a point set is a typical Erdős-Szekeres-type problem. We study this problem for 4-gons. Let P be a set of n points in the plane and in general position. A subset Q of P, with four points, is called a 4-hole in P if Q is in convex position and its convex hull does not contain any point of P in its interior. Two 4-holes in P are compatible if their interiors are disjoint. We show that P contains at least ⌊5n/11⌋−1 pairwise compatible 4-holes. This improves the lower bound of 2⌊(n−2)/5⌋ which is implied by a result of Sakai and Urrutia (2007).
computational-geometry  plane-geometry  limits  proof  nudge-targets  to-write-about  to-simulate
26 days ago
CTK Insights » Blog Archive It Never Stops with Pythagoras - CTK Insights
In the previous blog I described a discovery of Hirotaka Ebisui and an observation by Thanos Kalogerakis, both concerning what's known as Vecten's configuration. Vecten's configuration is a generalization of the famous Bride's Chair that underlies Euclid I.47, generally identified as the proof of the Pythagorean Theorem, although by now there are hundreds of them. In response to the previous post, Long Huynh Huu has expanded the two results, with the tools from linear algebra. To cut that introduction short, earlier today I was informed by Thanos Kalogerakis of a post by Carlos Hugo Olivera Días at the Peru Geometrico facebook group that adds another (and most fundamental at that) link to the just described chain of discoveries.
plane-geometry  mathematical-recreations  rather-interesting  discovery  feature-construction  to-write-about
27 days ago
[1802.06223] The Geodesic Farthest-point Voronoi Diagram in a Simple Polygon
Given a set of point sites in a simple polygon, the geodesic farthest-point Voronoi diagram partitions the polygon into cells, at most one cell per site, such that every point in a cell has the same farthest site with respect to the geodesic metric. We present an O(nloglogn+mlogm)- time algorithm to compute the geodesic farthest-point Voronoi diagram of m point sites in a simple n-gon. This improves the previously best known algorithm by Aronov et al. [Discrete Comput. Geom. 9(3):217-255, 1993]. In the case that all point sites are on the boundary of the simple polygon, we can compute the geodesic farthest-point Voronoi diagram in O((n+m)loglogn) time.
computational-geometry  algorithms  computational-complexity  to-understand  to-simulate  nudge-targets  consider:looking-to-see
27 days ago
[1801.08056] The ascent-plateau statistics on Stirling permutations
In this paper, several variants of the ascent-plateau statistic are introduced, including flag ascent-plateau, double ascent and descent-plateau. We first study the flag ascent-plateau statistic on Stirling permutations by using context-free grammars. We then present a unified refinement of the ascent polynomials and the ascent-plateau polynomials. In particular, by using Foata and Strehl's group action, we prove two bistatistics over the set of Stirling permutations of order n are equidistributed.
combinatorics  permutations  enumeration  probability-theory  to-understand  nudge-targets  consider:feature-discovery
27 days ago
Our Story
The history of the Beehive goes back and forth between the local and the global, the little and the big picture — just like our graphics. In the big picture story, we emerged out of the energy of the anti-globalization/global justice movement of the late 1990s and early 2000s, as massive protests were trying to shut down the meetings of global financial institutions and free trade negotiations, rocking cities from Seattle to Miami. We distributed our early work on the streets of these mobilizations, putting thousands of posters directly into people’s hands from all over the country, doing impromptu storytelling, and gathering contacts and collaborators for our first tours.

On the local level, the Beehive was sparked by a collaborative mosaic installation in Maine. The original group that became the Beehive came together as a mosaic cooperative to teach and practice the traditional craft of hand-cut stone mosaic, and take on commissions that would support this swarm of artists and activists in other creative endeavors as well. Out of this project a small group set down roots in eastern Maine, and began restoration work on the beautiful but endangered Machias Valley Grange Hall, originally with the desire to fix it up as studio space.

The building restoration soon grew into a much bigger project of bringing a community cultural center back to life, entirely with volunteer labor and donations from our posters. By the time the Grange was re-opened in 2005 in time for it’s 100th Birthday Celebration, the focus of the group had shifted from mosaics to working more full time on illustration projects. We often compare our mosaics and illustration work, as they are both forms of making storytelling murals that take a lot of patience, made up of a multitude of carefully gathered and assembled pieces that add up to a much bigger picture!
community  to-watch  cooperation  activism
27 days ago
Unemployed Negativity: Its Competition All the Way Down: On the Spontaneous Anthropology of Contemporary Capitalism
The cooperative dimension of our social life is constantly faced with its own disappearance. It is eclipsed by the ideologies that tell us that we live brutal lives of competition and self interest, and by the technologies that make it so. Social media has made friendship itself quantitative and competitive. However, it does not totally go away, and it cannot. As Peter Fleming has argued, it is precisely this incalculable sociality that is at the basis of contemporary work. Social relations not only sustain the workplace, as our attempts to assist and amuse each other do more for morale than any imposed "team building workshop," but also outside of it as well, networks of care from carpooling to grandparents babysitting kids make possible the world of isolated and competitive workers. Every squeeze, every reduction of wages or increase in working times, may be addressed to us as competitive individuals, compelling us to increase our competitive leverage, but it material affects us as parts of networks of relations that exceed it. Every cut to social services, every reduction in wages, is very often absorbed by increased pressure on relations of cooperation that are invisible to a society that tells itself it functions in and through cooperation. Cooperation functions as the concealed support and buttress for an ideology of competition.

It is not a matter of not only refusing to believe in competition, but to turn the networks of pollination into something other than support for our continued exploitation.  Viewed from the outside and fairly superficially, the "gilet jaunes" in France would seem to be an example of what can happen when social relations contest capital rather than simply absorb its costs. It is necessary to go from worker bees to a swarm.
political-economy  metaphors-on-the-run  social-norms  collaboration  competition  to-write-about
27 days ago
[1703.09533] Routing in Polygonal Domains
We consider the problem of routing a data packet through the visibility graph of a polygonal domain P with n vertices and h holes. We may preprocess P to obtain a label and a routing table for each vertex of P. Then, we must be able to route a data packet between any two vertices p and q of P, where each step must use only the label of the target node q and the routing table of the current node.
For any fixed ε>0, we present a routing scheme that always achieves a routing path whose length exceeds the shortest path by a factor of at most 1+ε. The labels have O(logn) bits, and the routing tables are of size O((ε−1+h)logn). The preprocessing time is O(n2logn). It can be improved to O(n2) for simple polygons.
planning  computational-geometry  operations-research  algorithms  computational-complexity  layered-problems  to-write-about
27 days ago
[1706.06571] The Distribution of Knots in the Petaluma Model
The representation of knots by petal diagrams (Adams et al. 2012) naturally defines a sequence of distributions on the set of knots. In this article we establish some basic properties of this randomized knot model. We prove that in the random n-petal model the probability of obtaining every specific knot type decays to zero as n, the number of petals, grows. In addition we improve the bounds relating the crossing number and the petal number of a knot. This implies that the n-petal model represents at least exponentially many distinct knots.
Past approaches to showing, in some random models, that individual knot types occur with vanishing probability, rely on the prevalence of localized connect summands as the complexity of the knot increases. However this phenomenon is not clear in other models, including petal diagrams, random grid diagrams, and uniform random polygons. Thus we provide a new approach to investigate this question.
knot-theory  representation  rather-interesting  to-write-about  topology  feature-construction
27 days ago
[1810.04825] An Initial Step Towards Organ Transplantation Based on GitHub Repository
Organ transplantation, which is the utilization of codes directly related to some specific functionalities to complete ones own program, provides more convenience for developers than traditional component reuse. However, recent techniques are challenged with the lack of organs for transplantation. Hence, we conduct an empirical study on extracting organs from GitHub repository to explore transplantation based on large-scale dataset. We analyze statistics from 12 representative GitHub projects and get the conclusion that 1) there are abundant practical organs existing in commits with add as a key word in the comments; 2) organs in this repository mainly possess four kinds of contents; 3) approximately 70% of the organs are easy-to-transplant. Implementing our transplantation strategy for different kinds of organs, we manually extract 30 organs in three different programming languages, namely Java, Python, and C, and make unit tests for them utilizing four testing tools (two for Java, one for Python, and one for C). At last, we transplant three Java organs into a specific platform for a performance check to verify whether they can work well in the new system. All the 30 organs extracted by our strategy possess good performances in unit test with the highest passing rate reaching 97% and the lowest one still passing 80% and the three Java organs work well in the new system, providing three new functionalities for the host. All the results indicate the feasibility of organ transplantation based on open-source repository, bringing new idea for code reuse.
28 days ago
Are Pop Lyrics Getting More Repetitive?
In 1977, the great computer scientist Donald Knuth published a paper called The Complexity of Songs, which is basically one long joke about the repetitive lyrics of newfangled music (example quote: "the advent of modern drugs has led to demands for still less memory, and the ultimate improvement of Theorem 1 has consequently just been announced").

I'm going to try to test this hypothesis with data. I'll be analyzing the repetitiveness of a dataset of 15,000 songs that charted on the Billboard Hot 100 between 1958 and 2017.
visualization  graphic-design  data-analysis  essay  looking-to-see  javascript  rather-interesting  via:cdzombak
28 days ago
[1707.02643] The Junta Method for Hypergraphs and the ErdH{o}s-Chv'{a}tal Simplex Conjecture
Numerous problems in extremal hypergraph theory ask to determine the maximal size of a k-uniform hypergraph on n vertices that does not contain an enlarged' copy H+ of a fixed hypergraph H. These include well-known problems such as the Erdős-Sós forbidding one intersection' problem and the Frankl-Füredi special simplex' problem.
We present a general approach to such problems, using a junta approximation method' that originates from analysis of Boolean functions. We prove that any H+-free hypergraph is essentially contained in a junta' -- a hypergraph determined by a small number of vertices -- that is also H+-free, which effectively reduces the extremal problem to an easier problem on juntas. Using this approach, we obtain, for all C<k<n/C, a complete solution of the extremal problem for a large class of H's, which includes the aforementioned problems, and solves them for a large new set of parameters.
We apply our method also to the 1974 Erdős-Chvátal simplex conjecture, which asserts that for any d<k≤dd+1n, the maximal size of a k-uniform family that does not contain a d-simplex (i.e., d+1 sets with empty intersection such that any d of them intersect) is (n−1k−1). We prove the conjecture for all d and k, provided n>n0(d).
hypergraphs  set-theory  optimization  conjecture  proof  combinatorics  nudge-targets  consider:looking-to-see  consider:representation
4 weeks ago
[1808.08414] Unsupervised Hypergraph Feature Selection via a Novel Point-Weighting Framework and Low-Rank Representation
Feature selection methods are widely used in order to solve the 'curse of dimensionality' problem. Many proposed feature selection frameworks, treat all data points equally; neglecting their different representation power and importance. In this paper, we propose an unsupervised hypergraph feature selection method via a novel point-weighting framework and low-rank representation that captures the importance of different data points. We introduce a novel soft hypergraph with low complexity to model data. Then, we formulate the feature selection as an optimization problem to preserve local relationships and also global structure of data. Our approach for global structure preservation helps the framework overcome the problem of unavailability of data labels in unsupervised learning. The proposed feature selection method treats with different data points based on their importance in defining data structure and representation power. Moreover, since the robustness of feature selection methods against noise and outlier is of great importance, we adopt low-rank representation in our model. Also, we provide an efficient algorithm to solve the proposed optimization problem. The computational cost of the proposed algorithm is lower than many state-of-the-art methods which is of high importance in feature selection tasks. We conducted comprehensive experiments with various evaluation methods on different benchmark data sets. These experiments indicate significant improvement, compared with state-of-the-art feature selection methods.
classification  feature-selection  rather-interesting  hypergraphs  to-understand  machine-learning  to-do
4 weeks ago
[1807.10492] Limits with Signed Digit Streams
We work with the signed digit representation of abstract real numbers, which roughly is the binary representation enriched by the additional digit -1. The main objective of this paper is an algorithm which takes a sequence of signed digit representations of reals and returns the signed digit representation of their limit, if the sequence converges. As a first application we use this algorithm together with Heron's method to build up an algorithm which converts the signed digit representation of a non-negative real number into the signed digit representation of its square root. Instead of writing the algorithms first and proving their correctness afterwards, we work the other way round, in the tradition of program extraction from proofs. In fact we first give constructive proofs, and from these proofs we then compute the extracted terms, which is the desired algorithm. The correctness of the extracted term follows directly by the Soundness Theorem of program extraction. In order to get the extracted term from some proofs which are often quite long, we use the proof assistant Minlog. However, to apply the extracted terms, the programming language Haskell is useful. Therefore after each proof we show a notation of the extracted term, which can be easily rewritten as a definition in Haskell.
algebra  representation  algorithms  rather-interesting  to-write-about  consider:looking-to-see  nudge-targets  consider:simulation
4 weeks ago
[1806.01823] Integrating Flexible Normalization into Mid-Level Representations of Deep Convolutional Neural Networks
Deep convolutional neural networks (CNNs) are becoming increasingly popular models to predict neural responses in visual cortex. However, contextual effects, which are prevalent in neural processing and in perception, are not explicitly handled by current CNNs, including those used for neural prediction. In primary visual cortex, neural responses are modulated by stimuli spatially surrounding the classical receptive field in rich ways. These effects have been modeled with divisive normalization approaches, including flexible models where spatial normalization is recruited only to the degree responses from center and surround locations are deemed statistically dependent. We propose a flexible normalization model applied to mid-level representations of deep CNNs as a tractable way to study contextual normalization mechanisms in mid-level visual areas. This approach captures non-trivial spatial dependencies among mid-level features in CNNs, such as those present in textures and other visual stimuli that arise from tiling high order features, geometrically. We expect that the proposed approach can make predictions about when spatial normalization might be recruited in mid-level cortical areas. We also expect this approach to be useful as part of the CNN toolkit, therefore going beyond more restrictive fixed forms of normalization.
neural-networks  deep-learning  design-patterns  rather-interesting  to-write-about  consider:other-design-patterns
4 weeks ago
[1309.3441] On the shape of subword complexity sequences of finite words
The subword complexity of a word w over a finite alphabet  is a function that assigns for each positive integer n, the number of distinct subwords of length n in w. The subword complexity of a word is a good measure of the randomness of the word and gives insight to what the word itself looks like. In this paper, we discuss the properties of subword complexity sequences, and consider different variables that influence their shape. We also compute the number of distinct subword complexity sequences for certain lengths of words over different alphabets, and state some conjectures about the growth of these numbers.
strings  combinatorics  enumeration  pattern-discovery  complexity-measures  information-theory  rather-interesting  to-write-about  for-puzzles  you-know-for-kids
4 weeks ago
[1808.07990] Making Bubbling Practical
Bubbling is a run-time graph transformation studied for the execution of non-deterministic steps in functional logic computations. This transformation has been proven correct, but as currently formulated it requires information about the entire context of a step, even when the step affects only a handful of nodes. Therefore, despite some advantages, it does not appear to be competitive with approaches that require only localized information, such as backtracking and pull-tabbing. We propose a novel algorithm that executes bubbling steps accessing only local information. To this aim, we define graphs that have an additional attribute, a dominator of each node, and we maintain this attribute when a rewrite and/or bubbling step is executed. When a bubbling step is executed, the dominator is available at no cost, and only local information is accessed. Our work makes bubbling practical, and theoretically competitive, for implementing non-determinism in functional logic computations.
functional-languages  computer-science  programming-language  remarkably-legible  rewriting-systems  representation  dynamical-systems  ReQ
4 weeks ago
[1803.11463] Arctic curves for paths with arbitrary starting points: a tangent method approach
We use the tangent method to investigate the arctic curve in a model of non-intersecting lattice paths with arbitrary fixed starting points aligned along some boundary and whose distribution is characterized by some arbitrary piecewise differentiable function. We find that the arctic curve has a simple explicit parametric representation depending of this function, providing us with a simple transform that maps the arbitrary boundary condition to the arctic curve location. We discuss generic starting point distributions as well as particular freezing ones which create additional frozen domains adjacent to the boundary, hence new portions for the arctic curve. A number of examples are presented, corresponding to both generic and freezing distributions.
combinatorics  arctic-curves  tiling  statistical-mechanics  simulation  looking-to-see  feature-construction  emergence  to-write-about  consider:prediction  consider:feature-discovery
4 weeks ago
[1810.04909] Tangent method for the arctic curve arising from freezing boundaries
In the paper arXiv:1803.11463, the authors study the arctic curve arising in random tilings of some planar domains with an arbitrary distribution of defects on one edge. Using the tangent method they derive a parametric equation for portions of arctic curve in terms of an arbitrary piecewise differentiable function that describes the defect distribution. When this distribution presents "freezing" intervals, other portions of arctic curve appear and typically have a cusp. These freezing boundaries can be of two types, respectively with maximal or minimal density of defects. Our purpose here is to extend the tangent method derivation of arXiv:1803.11463 to include these portions, hence providing the proof of the conjectures made in arXiv:1803.11463.
combinatorics  tiling  phase-transitions  arctic-curve  statistical-mechanics  looking-to-see  rather-interesting  to-write-about  to-simulate
4 weeks ago
[1611.03052] Cluster algebraic interpretation of infinite friezes
Originally studied by Conway and Coxeter, friezes appeared in various recreational mathematics publications in the 1970s. More recently, in 2015, Baur, Parsons, and Tschabold constructed periodic infinite friezes and related them to matching numbers in the once-punctured disk and annulus. In this paper, we study such infinite friezes with an eye towards cluster algebras of type D and affine A, respectively. By examining infinite friezes with Laurent polynomial entries, we discover new symmetries and formulas relating the entries of this frieze to one another. Lastly, we also present a correspondence between Broline, Crowe and Isaacs's classical matching tuples and combinatorial interpretations of elements of cluster algebras from surfaces.
combinatorics  algebra  enumeration  representation  to-understand  geometry
4 weeks ago
[1701.06377] Counting Arithmetical Structures on Paths and Cycles
Let G be a finite, simple, connected graph. An arithmetical structure on G is a pair of positive integer vectors d,r such that (diag(d)−A)r=0, where A is the adjacency matrix of G. We investigate the combinatorics of arithmetical structures on path and cycle graphs, as well as the associated critical groups (the cokernels of the matrices (diag(d)−A)). For paths, we prove that arithmetical structures are enumerated by the Catalan numbers, and we obtain refined enumeration results related to ballot sequences. For cycles, we prove that arithmetical structures are enumerated by the binomial coefficients (2n−1n−1), and we obtain refined enumeration results related to multisets. In addition, we determine the critical groups for all arithmetical structures on paths and cycles.
graph-theory  combinatorics  enumeration  counting  to-understand  matrices  feature-construction
4 weeks ago
[1705.01122] Cyclically Symmetric Lozenge Tilings of a Hexagon with Four Holes
The work of Mills, Robbins, and Rumsey on cyclically symmetric plane partitions yields a simple product formula for the number of lozenge tilings of a regular hexagon, which are invariant under roation by 120∘. In this paper we generalize this result by enumerating the cyclically symmetric lozenge tilings of a hexagon in which four triangles have been removed in the center.
combinatorics  tiling  to-understand  to-write-about  representation  translations-between-representations  enumeration  nudge-targets
4 weeks ago
[1805.09280] Dungeons and Dragons: Combinatorics for the $dP_3$ Quiver
In this paper, we utilize the machinery of cluster algebras, quiver mutations, and brane tilings to study a variety of historical enumerative combinatorics questions all under one roof. Previous work by the second author and REU students [Zha, LMNT14], and more recently of both authors [LM17], analyzed the cluster algebra associated to the cone over dP3, the del Pezzo surface of degree 6 (ℂℙ2 blown up at three points). By investigating sequences of toric mutations, those occurring only at vertices with two incoming and two outgoing arrows, in this cluster algebra, we obtained a family of cluster variables that could be parameterized by ℤ3 and whose Laurent expansions had elegant combinatorial interpretations in terms of dimer partition functions (in most cases). While the earlier work [Zha, LMNT14, LM17] focused exclusively on one possible initial seed for this cluster algebra, there are in total four relevant initial seeds (up to graph isomorphism). In the current work, we explore the combinatorics of the Laurent expansions from these other initial seeds and how this allows us to relate enumerations of perfect matchings on Dungeons to Dragons.
combinatorics  tiling  visualization  representation  to-understand  enumeration  algebra  to-write-about
4 weeks ago
[1812.02907] Caustics of Poncelet polygons and classical extremal polynomials
A comprehensive analysis of periodic trajectories of billiards within ellipses in the Euclidean plane is presented. The novelty of the approach is based on a relationship recently established by the authors between periodic billiard trajectories and extremal polynomials on the systems of d intervals on the real line and ellipsoidal billiards in d-dimensional space. Even in the planar case, systematically studied in the present paper it leads to new results in characterizing n periodic trajectories vs. so-called n elliptic periodic trajectories, which are n-periodic in elliptical coordinates. The characterizations are done both in terms of the underlying elliptic curve and divisors on it and in terms of polynomial functional equations, like Pell's equation. This new approach also sheds light on some classical results. In particular we connect search for caustics which generate periodic trajectories with three classical classes of extremal polynomials on two intervals, introduced by Zolotarev and Akhiezer. The main classifying tool are winding numbers, for which we provide several interpretations, including one in terms of numbers of points of alternance of extremal polynomials. The latter implies important inequality between the winding numbers, which as a consequence, provides another proof of monotonicity of rotation numbers. A complete catalog of billiard trajectories with small periods is provided for n=3,4,5,6 along with an effective search for caustics. As a byproduct, an intriguing connection between Cayle type conditions and discriminantly separable polynomials has been observed for all those small periods.
dynamical-systems  billiards  polynomials  plane-geometry  rather-interesting
4 weeks ago
Largest and Smallest Convex Hulls for Imprecise Points | SpringerLink
Assume that a set of imprecise points is given, where each point is specified by a region in which the point may lie. We study the problem of computing the smallest and largest possible convex hulls, measured by length and by area. Generally we assume the imprecision region to be a square, but we discuss the case where it is a segment or circle as well. We give polynomial time algorithms for several variants of this problem, ranging in running time from O(nlog n) to O(n 13), and prove NP-hardness for some other variants.
computational-geometry  plane-geometry  optimization  uncertainty  imprecision  rather-interesting  to-write-about  nudge-targets
4 weeks ago
[1712.08911] Largest and Smallest Area Triangles on Imprecise Points
Assume we are given a set of parallel line segments in the plane, and we wish to place a point on each line segment such that the resulting point set maximizes or minimizes the area of the largest or smallest triangle in the set. We analyze the complexity of the four resulting computational problems, and we show that three of them admit polynomial-time algorithms, while the fourth is NP-hard. Specifically, we show that maximizing the largest triangle can be done in O(n2) time (or in O(nlogn) time for unit segments); minimizing the largest triangle can be done in O(n2logn) time; maximizing the smallest triangle is NP-hard; but minimizing the smallest triangle can be done in O(n2) time. We also discuss to what extent our results can be generalized to polygons with k>3 sides.
computational-geometry  rather-interesting  approximation  plane-geometry  optimization  to-write-about  nudge-targets  consider:looking-to-see
4 weeks ago
[1712.05081] Linear time Minimum Area All-flush Triangles Circumscribing a Convex Polygon
We study the problem of computing the minimum area triangle that circumscribes a given n-sided convex polygon touching edge-to-edge. In other words, we compute the minimum area triangle that is the intersection of 3 half-planes out of n half-planes defined by a given convex polygon. Building on the Rotate-and-Kill technique {arXiv:1707.04071}, we propose an algorithm that solves the problem in O(n) time, improving the best-known O(nlogn) time algorithms given in [A. Aggarwal et. al. DCG94; B. Schieber. SODA95}. Our algorithm computes all the locally minimal area circumscribing triangles touching edge-to-edge.
computational-geometry  algorithms  plane-geometry  rather-interesting  to-write-about  nudge-targets  consider:looking-to-see
4 weeks ago
[1705.11035] Maximum-Area Triangle in a Convex Polygon, Revisited
We revisit the following problem: Given a convex polygon P, find the largest-area inscribed triangle. We show by example that the linear-time algorithm presented in 1979 by Dobkin and Snyder for solving this problem fails. We then proceed to show that with a small adaptation, their approach does lead to a quadratic-time algorithm. We also present a more involved O(nlogn) time divide-and-conquer algorithm. Also we show by example that the algorithm presented in 1979 by Dobkin and Snyder for finding the largest-area k-gon that is inscribed in a convex polygon fails to find the optimal solution for k=4. Finally, we discuss the implications of our discoveries on the literature.
computational-geometry  optimization  plane-geometry  rather-interesting  to-write-about  oopsie  nudge-targets  consider:looking-to-see
4 weeks ago
[1707.04071] Maximal Area Triangles in a Convex Polygon
The widely known linear time algorithm for computing the maximum area triangle in a convex polygon was found incorrect recently by Keikha et. al.(arXiv:1705.11035). We present an alternative algorithm in this paper. Comparing to the only previously known correct solution, ours is much simpler and more efficient. More importantly, our new approach is powerful in solving related problems.
computational-geometry  algorithms  plane-geometry  rather-interesting  nudge-targets  consider:looking-to-see  to-write-about
4 weeks ago
[1809.06451] A new lower bound on Hadwiger-Debrunner numbers in the plane
A family of sets F is said to satisfy the (p,q) property if among any p sets in F, some q have a non-empty intersection. Hadwiger and Debrunner (1957) conjectured that for any p≥q≥d+1 there exists c=cd(p,q), such that any family of compact convex sets in ℝd that satisfies the (p,q) property, can be pierced by at most c points. In a celebrated result from 1992, Alon and Kleitman proved the conjecture. However, obtaining sharp bounds on cd(p,q), called the Hadwiger-Debrunner numbers', is still a major open problem in discrete and computational geometry. The best currently known lower bound on the Hadwiger-Debrunner numbers in the plane is c2(p,q)=Ω(pqlog(pq)) while the best known upper bound is O(p(1.5+δ)(1+1q−2)).
In this paper we improve the lower bound significantly by showing that c2(p,q)≥p1+Ω(1/q). Furthermore, the bound is obtained by a family of lines, and is tight for all families that have a bounded VC-dimension. Unlike previous bounds on the Hadwiger-Debrunner numbers which mainly used the weak epsilon-net theorem, our bound stems from a surprising connection of the (p,q) problem to an old problem of Erdős on points in general position in the plane. We use a novel construction for the Erdős' problem, obtained recently by Balogh and Solymosi using the hypergraph container method, to get the lower bound on c2(p,3). We then generalize the bound to c2(p,q) for any q≥3.
computational-geometry  plane-geometry  to-understand  graph-theory  proof  nudge-targets  consider:looking-to-see  also:a-fucking-drawing-or-two-might-be-nice-people
4 weeks ago
The coolest way to generate combinations - ScienceDirect
We present a practical and elegant method for generating all
-combinations (binary strings with
zeros and
ones): Identify the shortest prefix ending in 010 or 011 (or the entire string if no such prefix exists), and rotate it by one position to the right. This iterative rule gives an order to
-combinations that is circular and genlex. Moreover, the rotated portion of the string always contains at most four contiguous runs of zeros and ones, so every iteration can be achieved by transposing at most two pairs of bits. This leads to an efficient loopless and branchless implementation that consists only of two variables and six assignment statements. The order also has a number of striking similarities to colex order, especially its recursive definition and ranking algorithm. In the light of these similarities we have named our order cool-lex!
4 weeks ago
[1804.05578] Probabilistic Rewriting: Relations between Normalization, Termination, and Unique Normal Forms
We adapt to the probabilistic setting techniques from Rewrite Theory, to gain a better understanding of the operational properties of calculi whose evaluation is both probabilistic and non-deterministic. The non-determinism we have in mind is that of parallelism, which arises from a choice between several redexes (think of lambda-calculus). In this context, questions such as "is the result unique?", or "is there a strategy to find a result with greatest probability?" are natural and computationally important.
We investigate how the asymptotic behavior of different rewrite sequences starting from the same term compare w.r.t. normal forms, and we develop methods to study and compare strategies. Our approach is that of Abstract Rewrite Systems, we search for general properties of probabilistic rewriting, which hold independently of the specific nature of the objects.
As an application, we study a lambda calculus, equipped with call-by-value weak evaluation and a probabilistic choice.
probabilistic-languages  lambda-calculus  rewriting-systems  computer-science  programming-language  to-understand  formal-languages  ReQ
4 weeks ago
[1807.08178] DP-Colorings of Hypergraphs
Classical problems in hypergraph coloring theory are to estimate the minimum number of edges, m2(r) (respectively, m∗2(r)), in a non-2-colorable r-uniform (respectively, r-uniform and simple) hypergraph. The best currently known bounds are
c⋅r/logr‾‾‾‾‾‾√⋅2r⩽m2(r)⩽C⋅r2⋅2randc′⋅r−ε⋅4r⩽m∗2(r)⩽C′⋅r4⋅4r,
for any fixed ε>0 and some c, c′, C, C′>0 (where c′ may depend on ε). In this paper we consider the same problems in the context of DP-coloring (also known as correspondence coloring), which is a generalization of list coloring introduced by Dvořák and Postle and related to local conflict coloring studied independently by Fraigniaud, Heinrich, and Kosowski. Let m̃2(r) (respectively, m̃∗2(r)) denote the minimum number of edges in a non-2-DP-colorable r-uniform (respectively, r-uniform and simple) hypergraph. By definition, m̃2(r)⩽m2(r) and m̃∗2(r)⩽m∗2(r).
While the proof of the bound m∗2(r)=Ω(r−34r) due to Erdős and Lovász also works for m̃∗2(r), we show that the trivial lower bound m̃2(r)⩾2r−1 is asymptotically tight, i.e., m̃2(r)⩽(1+o(1))2r−1. On the other hand, when r⩾2 is even, we prove that the lower bound m̃2(r)⩾2r−1 is not sharp, i.e., m̃2(r)⩾2r−1+1. Whether this result holds for any odd r remains an open problem. Nevertheless, we find it tempting to conjecture that the difference m̃2(r)−2r−1 tends to infinity with r.
set-theory  hypergraphs  graph-theory  graph-coloring  combinatorics  rather-interesting  to-write-about
4 weeks ago

Copy this bookmark:

description:

tags: