Alignment-based genetic programming for real life applications - ScienceDirect

yesterday

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.

symbolic-regression
genetic-programming
hybrid-methods
system-identification
have-read
yesterday

Computer based design of Islamic geometric patterns - YouTube

2 days ago

Computer based design of Islamic geometric patterns

lecture
islamic-art
plane-geometry
generative-models
algorithms
aesthetics
history
compass-and-straightedge-constructions
2 days ago

Indianapolis Collected: New Year's Eve at the Boom Boom Room - Historic Indianapolis | All Things Indianapolis History

8 days ago

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.

nanohistory
humor
the-Win-Schuler-menu-in-my-hand-is-identical
how-odd
plagiarism?
8 days ago

Alan Feuer on Twitter: "In February 2010, an undercover FBI agent met with the target of a sensitive investigation: Christian Rodriguez, an IT specialist who had recently developed a remarkable product: an encrypted communication network for the Mexican d

crime-thriller truth-and-fiction security news also-wow

11 days ago

crime-thriller truth-and-fiction security news also-wow

11 days ago

[1807.09977] Colored range closest-pair problem under general distance functions

12 days ago

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

12 days ago

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

12 days ago

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

12 days ago

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

12 days ago

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

12 days ago

Meet Clojure MXNet - NDArray - Squid's Blog

15 days ago

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

15 days ago

[1811.09989] The dry history of liquid computers

15 days ago

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.

nontraditional-computing
representation
algorithms
out-of-the-box
review
history
computer-science
engineering-design
to-write-about
to-simulate
15 days ago

[1806.04609] Streaming PCA and Subspace Tracking: The Missing Data Case

15 days ago

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

15 days ago

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

15 days ago

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.

models-and-modes
literary-criticism
literature
performance-measure
social-construction-of-social-constructions
to-write-about
fads-and-well-not-really-fads-but-maybe-fallacies
aesthetics
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

15 days ago

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

15 days ago

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

15 days ago

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

15 days ago

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

15 days ago

Tanya Khovanova's Math Blog » Blog Archive » 3-Symmetric Permutations

15 days ago

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

15 days ago

Tanya Khovanova's Math Blog » Blog Archive » 3-Symmetric Graphs

15 days ago

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

15 days ago

[1807.04271] A quantum-inspired classical algorithm for recommendation systems

15 days ago

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

Friendship Paradox | Math Section

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

graph-theory
rather-interesting
network-theory
to-write-about
17 days ago

[1703.07054] Name-free combinators for concurrency

17 days ago

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.

17 days ago

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

17 days ago

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

17 days ago

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

20 days ago

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

20 days ago

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}$

20 days ago

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.

group-theory
combinatorics
algorithms
rather-interesting
feature-construction
to-understand
to-write-about
an-example-would-be-useful-about-now
20 days ago

[1712.02950] CycleGAN, a Master of Steganography

21 days ago

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.

adversarial-attacks
machine-learning
deep-learning
generative-models
tricksy-humans
steganography-as-a-side-effect
rather-interesting
to-write-about
21 days ago

[1605.03502] A solution to the reversible embedding problem for finite Markov chains

21 days ago

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

21 days ago

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

21 days ago

It is black letter doctrine that facts are not copyrightable: facts are discovered, not created—so they will always lack the originality needed for copyright protection. As straightforward as this reasoning seems, it is fundamentally flawed. Using the “social facts” theory of philosopher John Searle, this Article explores a variety of “created facts” cases—designation systems, systematic evaluations, and privately written laws—in which original expression from private individuals is adopted by social convention and generates facts in our social reality. In the course of this discussion, the paper places facts in their historical and philosophical context, explores how courts conflate facts with expressions of fact, and explains the difference between social facts created by expression and the “facts” of literature and fiction. Having established that the copyrighted works discussed in these cases produce facts, the question arises whether copyright's merger doctrine eliminates the copyright protection—a result that is both seemingly harsh and seemingly necessary. This Article proposes a recalibration of the merger doctrine to acknowledge that “created facts” are a unique situation in which the incentive of copyright is needed not just to generate the expression, but also needed to generate the facts. Reprinted by permission of the publisher.

law
pragmatism
philosophy
rather-interesting
to-understand
21 days ago

[1809.07481] $L_1$ Shortest Path Queries in Simple Polygons

22 days ago

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

22 days ago

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

22 days ago

CTK Insights » Blog Archive A pizza with a hole - CTK Insights

22 days ago

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

22 days ago

[PDF] Captivating algorithms: Recommender systems as traps

22 days ago

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

22 days ago

Supermultiplexed optical imaging and barcoding with engineered polyynes | Nature Methods

22 days ago

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

22 days ago

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.

22 days ago

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
Wait what?!

22 days ago

Polygenic scores and tea drinking | gcbias

23 days ago

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

25 days ago

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é

25 days ago

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

25 days ago

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

26 days ago

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

26 days ago

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

26 days ago

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

26 days ago

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

27 days ago

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

27 days ago

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

27 days ago

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

27 days ago

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

27 days ago

Unemployed Negativity: Its Competition All the Way Down: On the Spontaneous Anthropology of Contemporary Capitalism

27 days ago

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

27 days ago

[1703.09533] Routing in Polygonal Domains

27 days ago

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

27 days ago

[1706.06571] The Distribution of Knots in the Petaluma Model

27 days ago

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

27 days ago

[1810.04825] An Initial Step Towards Organ Transplantation Based on GitHub Repository

28 days ago

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.

software-engineering
rather-odd
not-a-bad-idea
reuse
crossover
to-write-about
28 days ago

Are Pop Lyrics Getting More Repetitive?

28 days ago

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

28 days ago

[1707.02643] The Junta Method for Hypergraphs and the ErdH{o}s-Chv'{a}tal Simplex Conjecture

4 weeks ago

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

4 weeks ago

[1808.08414] Unsupervised Hypergraph Feature Selection via a Novel Point-Weighting Framework and Low-Rank Representation

4 weeks ago

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

4 weeks ago

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

4 weeks ago

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

4 weeks ago

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

4 weeks ago

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

4 weeks ago

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

4 weeks ago

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

4 weeks ago

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

4 weeks ago

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

4 weeks ago

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

4 weeks ago

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

4 weeks ago

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

4 weeks ago

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

4 weeks ago

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

4 weeks ago

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

4 weeks ago

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

4 weeks ago

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

4 weeks ago

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

4 weeks ago

The coolest way to generate combinations - ScienceDirect

4 weeks ago

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!

combinatorics
algorithms
rather-interesting
to-write-about
-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

4 weeks ago

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

4 weeks ago

[1807.08178] DP-Colorings of Hypergraphs

4 weeks ago

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

4 weeks ago

academia
academic-culture
activism
advice
agent-based
agility
algorithms
amusing
ann-arbor
approximation
architecture
archive
art
artificial-intelligence
artificial-life
benchmarking
bioinformatics
biological-engineering
blogging
books
bushism
business
business-culture
business-model
cellular-automata
classification
clustering
collaboration
collective-intelligence
combinatorics
commons
communication
community
complex-systems
complexology
compressed-sensing
computational-complexity
computational-geometry
computer-science
conservatism
consider:feature-discovery
consider:looking-to-see
consider:performance-measures
consider:rediscovery
consider:representation
consider:stress-testing
constraint-satisfaction
copyright
corporatism
criticism
crowdsourcing
cultural-assumptions
cultural-dynamics
cultural-norms
data-analysis
data-mining
deep-learning
define-your-terms
design
design-patterns
development
digital-humanities
digitization
disintermediation-in-action
distributed-processing
diversity
dynamical-systems
economics
education
emergence
emergent-design
engineering
engineering-design
evolutionary-algorithms
evolutionary-economics
experiment
feature-construction
feature-extraction
finance
financial-crisis
fitness-landscapes
formalization
game-theory
games
generative-art
generative-models
genetic-programming
geometry
government
graph-theory
graphic-design
heuristics
hey-i-know-this-guy
history
horse-races
humor
image-analysis
image-processing
image-segmentation
inference
information-theory
innovation
intellectual-property
interesting
inverse-problems
javascript
kauffmania
language
law
lawyers
learning
learning-by-doing
learning-from-data
library
local
looking-to-see
machine-learning
macos
management
marketing
mathematical-recreations
mathematics
matrices
media
metaheuristics
metrics
modeling
models
models-and-modes
multiobjective-optimization
nanohistory
nanotechnology
natural-language-processing
network-theory
networks
neural-networks
nonlinear-dynamics
nudge
nudge-targets
number-theory
numerical-methods
open-access
open-questions
open-source
openness
operations-research
optimization
pedagogy
performance-measure
philosophy
philosophy-of-engineering
philosophy-of-science
photography
physics
plane-geometry
planning
politics
prediction
probability-theory
programming
proof
public-policy
publishing
rather-interesting
representation
research
review
robotics
robustness
ruby
science
self-organization
signal-processing
simulation
social-dynamics
social-engineering
social-networks
social-norms
sociology
software
software-development
statistics
strings
sustainability
system-of-professions
systems-biology
technology
the-mangle-in-practice
theoretical-biology
tiling
time-series
to-do
to-read
to-understand
to-write-about
tools
trading
typography
user-experience
via:cshalizi
video
visualization
web-design
web2.0
worklife
writing