[1609.00206] Optimal point sets determining few distinct triangles
We generalize work of Erdos and Fishburn to study the structure of finite point sets that determine few distinct triangles. Specifically, we ask for a given t, what is the maximum number of points that can be placed in the plane to determine exactly t distinct triangles? Denoting this quantity by F(t), we show that F(1)=4, F(2)=5, and F(t)<48(t+1) for all t. We also completely characterize the optimal configurations for t=1,2.
optimization  plane-geometry  nudge-targets  Erdös  to-write-about  benchmarks 
2 hours ago
[1610.07836v1] Classification of crescent configurations
Let n points be in crescent configurations in ℝd if they lie in general position in ℝd and determine n−1 distinct distances, such that for every 1≤i≤n−1 there is a distance that occurs exactly i times. Since Erd\H{o}s' conjecture in 1989 on the existence of N sufficiently large such that no crescent configurations exist on N or more points, he, Pomerance, and Pal\'asti have given constructions for n up to 8 but nothing is yet known for n≥9. Most recently, Burt et. al. had proven that a crescent configuration on n points exists in ℝn−2 for n≥3. In this paper, we study the classification of these configurations on 4 and 5 points through graph isomorphism and rigidity. Our techniques, which can be generalized to higher dimensions, offer a new viewpoint on the problem through the lens of distance geometry and provide a systematic way to construct crescent configurations.
number-theory  to-write-about  nudge-targets 
2 hours ago
[1705.02584] On the structure of large sum-free sets of integers
A set of integers is called sum-free if it contains no triple of elements x,y,z with x+y=z. In this paper we provide a structural characterisation of sum-free subsets of {1,2,…,n} of density at least 2/5−c, where c is an absolute positive constant. As an application we derive a stability version of Hu's theorem [Proc. Amer. Math. Soc. 80 (1980), 711-712] about partitioning sets of integers into two sum-free subsets. We then use this result to show that the number of subsets of {1,2,…,n} which can be partitioned into two sum-free sets is Θ(24n/5), confirming a conjecture of Hancock, Staden and Treglown [arXiv:1701.04754].
number-theory  to-write-about  nudge-targets  consider:classification 
2 hours ago
[1201.1317v1] On sets of integers which are both sum-free and product-free
We consider sets of positive integers containing no sum of two elements in the set and also no product of two elements. We show that the upper density of such a set is strictly smaller than 1/2 and that this is best possible. Further, we also find the maximal order for the density of such sets that are also periodic modulo some positive integer.
number-theory  to-write-about  nudge-targets 
2 hours ago
[math/0609373] Lowest Terms Revisited
In the September 1994 issue of Math Horizons the following problem is given in the Problem Section (p. 33, Problem 5): Lowest Terms - what fraction has the smallest denominator in the interval (19/94, 17/76)? In this paper we develop a general algorithm for solving problems of this type.
mathematical-recreations  to-write-about  number-theory  nudge-targets 
2 hours ago
[1303.0605v1] Explicit Constructions of Large Families of Generalized More Sums Than Differences Sets
A More Sums Than Differences (MSTD) set is a set of integers A contained in {0, ..., n-1} whose sumset A+A is larger than its difference set A-A. While it is known that as n tends to infinity a positive percentage of subsets of {0, ..., n-1} are MSTD sets, the methods to prove this are probabilistic and do not yield nice, explicit constructions. Recently Miller, Orosz and Scheinerman gave explicit constructions of a large family of MSTD sets; though their density is less than a positive percentage, their family's density among subsets of {0, ..., n-1} is at least C/n^4 for some C>0, significantly larger than the previous constructions, which were on the order of 1 / 2^{n/2}. We generalize their method and explicitly construct a large family of sets A with |A+A+A+A| > |(A+A)-(A+A)|. The additional sums and differences allow us greater freedom than in Miller, Orosz and Scheinerman, and we find that for any epsilon>0 the density of such sets is at least C / n^epsilon. In the course of constructing such sets we find that for any integer k there is an A such that |A+A+A+A| - |A+A-A-A| = k, and show that the minimum span of such a set is 30.
number-theory  open-questions  generators  algorithms  to-write-about 
2 hours ago
[1512.01727v3] Solving the Subset Sum Problem with Heap-Ordered Subset Trees
In the field of algorithmic analysis, one of the more well-known exercises is the subset sum problem. That is, given a set of integers, determine whether one or more integers in the set can sum to a target value. Aside from the brute-force approach of verifying all combinations of integers, several solutions have been found, ranging from clever uses of various data structures to computationally-efficient approximation solutions. In this paper, a unique approach is discussed which builds upon the existing min-heap solution for positive integers, introducing a tree-based data structure influenced by the binomial heap. Termed the subset tree, this data structure solves the subset sum problem for all integers in time O(N3klogk), where N is the length of the set and k is the index of the list of subsets that is being searched.
algorithms  number-theory  rather-interesting  to-write-about  hard-problems  nudge-targets 
2 hours ago
[math/0608148v2] Sets with more sums than differences
Let A be a finite subset of the integers or, more generally, of any abelian group, written additively. The set A has "more sums than differences" if |A+A|>|A-A|. A set with this property is called an MSTD set. This paper gives explicit constructions of families of MSTD sets of integers.
number-theory  open-questions  to-write-about  nudge-targets  consider:classification 
3 hours ago
[1608.03256v1] When Sets Can and Cannot Have MSTD Subsets
A finite set of integers A is a More Sums Than Differences (MSTD) set if |A+A|>|A−A|. While almost all subsets of {0,…,n} are not MSTD, interestingly a small positive percentage are. We explore sufficient conditions on infinite sets of positive integers such that there are either no MSTD subsets, at most finitely many MSTD subsets, or infinitely many MSTD subsets. In particular, we prove no subset of the Fibonacci numbers is an MSTD set, establish conditions such that solutions to a recurrence relation have only finitely many MSTD subsets, and show there are infinitely many MSTD subsets of the primes.
number-theory  proof  to-write-about  open-questions  nudge-targets 
3 hours ago
[1702.04166v1] A set of 12 numbers is not determined by its set of 4-sums
We present two sets of 12 integers that have the same sets of 4-sums. The proof of the fact that a set of 12 numbers is uniquely determined by the set of its 4-sums published 50 years ago is wrong, and we demonstrate an incorrect calculation in it.
number-theory  open-questions  to-write-about  puzzles  nudge-targets 
3 hours ago
[1201.6339] Epidemics on Interconnected Networks
Populations are seldom completely isolated from their environment. Individuals in a particular geographic or social region may be considered a distinct network due to strong local ties, but will also interact with individuals in other networks. We study the susceptible-infected-recovered (SIR) process on interconnected network systems, and find two distinct regimes. In strongly-coupled network systems, epidemics occur simultaneously across the entire system at a critical infection strength βc, below which the disease does not spread. In contrast, in weakly-coupled network systems, a mixed phase exists below βc of the coupled network system, where an epidemic occurs in one network but does not spread to the coupled network. We derive an expression for the network and disease parameters that allow this mixed phase and verify it numerically. Public health implications of communities comprising these two classes of network systems are also mentioned.
epidemiology  network-theory  agent-based  rather-interesting  to-write-about  simulation 
[1212.0404] Explosive transitions to synchronization in networked phase oscillators
We introduce a condition for an ensemble of networked phase oscillators to feature an abrupt, first-order phase transition from an unsynchronized to a synchronized state. This condition is met in a very wide spectrum of situations, and for various oscillators' initial frequency distributions. We show that the occurrence of such transitions is always accompanied by the spontaneous emergence of frequency-degree correlations in random network architectures. We also discuss ways to relax the condition, and to further extend the possibility for the first-order transition to occur, and illustrate how to engineer magnetic-like states of synchronization. Our findings thus indicate how to search for abrupt transitions in real-world applications.
coupled-oscillators  nonlinear-dynamics  to-do  to-write-about  rather-interesting 
[0711.1778] Modules identification by a Dynamical Clustering algorithm based on chaotic R"ossler oscillators
A new dynamical clustering algorithm for the identification of modules in complex networks has been recently introduced \cite{BILPR}. In this paper we present a modified version of this algorithm based on a system of chaotic Roessler oscillators and we test its sensitivity on real and computer generated networks with a well known modular structure.
community-detection  dynamical-systems  coupled-oscillators  feature-construction  rather-interesting  nonlinear-dynamics  to-write-about  nudge-targets  consider:variant-overlays 
2 days ago
[1611.02617] Color-avoiding percolation
Many real world networks have groups of similar nodes which are vulnerable to the same failure or adversary. Nodes can be colored in such a way that colors encode the shared vulnerabilities. Using multiple paths to avoid these vulnerabilities can greatly improve network robustness. Color-avoiding percolation provides a theoretical framework for analyzing this scenario, focusing on the maximal set of nodes which can be connected via multiple color-avoiding paths. In this paper we extend the basic theory of color-avoiding percolation that was published in [Krause et. al., Phys. Rev. X 6 (2016) 041022]. We explicitly account for the fact that the same particular link can be part of different paths avoiding different colors. This fact was previously accounted for with a heuristic approximation. We compare this approximation with a new, more exact theory and show that the new theory is substantially more accurate for many avoided colors. Further, we formulate our new theory with differentiated node functions, as senders/receivers or as transmitters. In both functions, nodes can be explicitly trusted or avoided. With only one avoided color we obtain standard percolation. With one by one avoiding additional colors, we can understand the critical behavior of color avoiding percolation. For heterogeneous color frequencies, we find that the colors with the largest frequencies control the critical threshold and exponent. Colors of small frequencies have only a minor influence on color avoiding connectivity, thus allowing for approximations.
security  graph-theory  network-theory  robustness  algorithms  nudge-targets  consider:higher-order-features 
2 days ago
The Omidyar Network and the (Neoliberal) Future of Education
So, while in the US we see neoliberalism pushing to dismantle public institutions and public funding for public institutions, in the Global South, these very forces are there touting the “power of markets” to make sure public institutions can never emerge or thrive in the first place. Investors like the Omidyar Network are poised to extract value from the very people they promise their technologies and businesses are there to help.
Conveniently, the Omidyar Network’s investment portfolio also includes journalistic and research organizations that are too poised to promote and endorse the narratives that aggrandize these very technocratic, market-based solutions.
neoliberalism  education  corporatism  disintermediation-in-action  not-a-good-idea 
8 days ago
Who Really Makes Money Off of Bail Bonds? - The Atlantic
A new report from the nonprofit Color of Change and the American Civil Liberties Union (ACLU) sheds further light on the country’s bail system. The report finds that around 70 percent of those currently in jail have yet to be convicted of a crime. Not unrelated: Between 1990 and 2009, the share of people arrested who were required to post money bail grew from 37 percent to 61 percent, according to the report.
corporatism  police  politics  racism  legalism  public-policy  the-crises 
8 days ago
[1705.03394] That is not dead which can eternal lie: the aestivation hypothesis for resolving Fermi's paradox
If a civilization wants to maximize computation it appears rational to aestivate until the far future in order to exploit the low temperature environment: this can produce a 1030 multiplier of achievable computation. We hence suggest the "aestivation hypothesis": the reason we are not observing manifestations of alien civilizations is that they are currently (mostly) inactive, patiently waiting for future cosmic eras. This paper analyzes the assumptions going into the hypothesis and how physical law and observational evidence constrain the motivations of aliens compatible with the hypothesis.
aliens  Fermi-paradox  rather-interesting  to-write-about  via:absfac 
8 days ago
Trumpism: It’s Coming From the Suburbs | The Nation
If you’re looking for Trump’s implacable support, Texas trailer parks and Kentucky cabins are the wrong places to find it. Fascism develops over hands of poker in furnished basements, over the grill by the backyard pool, over beers on the commuter-rail ride back from the ball game—and in police stations and squad cars. 

fascism  cultural-norms 
11 days ago
[1609.07061] Quantized Neural Networks: Training Neural Networks with Low Precision Weights and Activations
We introduce a method to train Quantized Neural Networks (QNNs) --- neural networks with extremely low precision (e.g., 1-bit) weights and activations, at run-time. At train-time the quantized weights and activations are used for computing the parameter gradients. During the forward pass, QNNs drastically reduce memory size and accesses, and replace most arithmetic operations with bit-wise operations. As a result, power consumption is expected to be drastically reduced. We trained QNNs over the MNIST, CIFAR-10, SVHN and ImageNet datasets. The resulting QNNs achieve prediction accuracy comparable to their 32-bit counterparts. For example, our quantized version of AlexNet with 1-bit weights and 2-bit activations achieves 51% top-1 accuracy. Moreover, we quantize the parameter gradients to 6-bits as well which enables gradients computation using only bit-wise operation. Quantized recurrent neural networks were tested over the Penn Treebank dataset, and achieved comparable accuracy as their 32-bit counterparts using only 4-bits. Last but not least, we programmed a binary matrix multiplication GPU kernel with which it is possible to run our MNIST QNN 7 times faster than with an unoptimized GPU kernel, without suffering any loss in classification accuracy. The QNN code is available online.
representation  neural-networks  deep-learning  rather-interesting  to-write-about  consider:simple-examples 
12 days ago
[1705.00241] Dynamic interdependence and competition in multilayer networks
From critical infrastructure, to physiology and the human brain, complex systems rarely occur in isolation. Instead, the functioning of nodes in one system often promotes or suppresses the functioning of nodes in another. Despite advances in structural interdependence, modeling interdependence and other interactions between dynamic systems has proven elusive. Here we define a broadly applicable dynamic dependency link and develop a general framework for interdependent and competitive interactions between general dynamic systems. We apply our framework to studying interdependent and competitive synchronization in multi-layer oscillator networks and cooperative/competitive contagions in an epidemic model. Using a mean-field theory which we verify numerically, we find explosive transitions and rich behavior which is absent in percolation models including hysteresis, multi-stability and chaos. The framework presented here provides a powerful new way to model and understand many of the interacting complex systems which surround us.
dynamical-systems  coupled-oscillators  network-theory  rather-interesting  to-write-about  simulation  consider:simple-examples  nudge-targets  consider:control-theory  consider:feature-discovery 
12 days ago
[1702.08359] Dynamic Word Embeddings via Skip-Gram Filtering
We present a probabilistic language model for time-stamped text data which tracks the semantic evolution of individual words over time. The model represents words and contexts by latent trajectories in an embedding space. At each moment in time, the embedding vectors are inferred from a probabilistic version of word2vec [Mikolov, 2013]. These embedding vectors are connected in time through a latent diffusion process. We describe two scalable variational inference algorithms---skip-gram smoothing and skip-gram filtering---that allow us to train the model jointly over all times; thus learning on all data while simultaneously allowing word and context vectors to drift. Experimental results on three different corpora demonstrate that our dynamic model infers word embedding trajectories that are more interpretable and lead to higher predictive likelihoods than competing methods that are based on static models trained separately on time slices.
natural-language-processing  machine-learning  representation  to-understand  skip-grams  consider:looking-to-see  to-write-about 
12 days ago
[1703.01141] Dynamic State Warping
The ubiquity of sequences in many domains enhances significant recent interest in sequence learning, for which a basic problem is how to measure the distance between sequences. Dynamic time warping (DTW) aligns two sequences by nonlinear local warping and returns a distance value. DTW shows superior ability in many applications, e.g. video, image, etc. However, in DTW, two points are paired essentially based on point-to-point Euclidean distance (ED) without considering the autocorrelation of sequences. Thus, points with different semantic meanings, e.g. peaks and valleys, may be matched providing their coordinate values are similar. As a result, DTW is sensitive to noise and poorly interpretable. This paper proposes an efficient and flexible sequence alignment algorithm, dynamic state warping (DSW). DSW converts each time point into a latent state, which endows point-wise autocorrelation information. Alignment is performed by using the state sequences. Thus DSW is able to yield alignment that is semantically more interpretable than that of DTW. Using one nearest neighbor classifier, DSW shows significant improvement on classification accuracy in comparison to ED (70/85 wins) and DTW (74/85 wins). We also empirically demonstrate that DSW is more robust and scales better to long sequences than ED and DTW.
time-series  time-warping  representation  to-understand  algorithms  machine-learning  feature-construction 
12 days ago
[1704.00899] Dynamic Rank Maximal Matchings
We consider the problem of matching applicants to posts where applicants have preferences over posts. Thus the input to our problem is a bipartite graph G = (A U P,E), where A denotes a set of applicants, P is a set of posts, and there are ranks on edges which denote the preferences of applicants over posts. A matching M in G is called rank-maximal if it matches the maximum number of applicants to their rank 1 posts, subject to this the maximum number of applicants to their rank 2 posts, and so on.
We consider this problem in a dynamic setting, where vertices and edges can be added and deleted at any point. Let n and m be the number of vertices and edges in an instance G, and r be the maximum rank used by any rank-maximal matching in G. We give a simple O(r(m+n))-time algorithm to update an existing rank-maximal matching under each of these changes. When r = o(n), this is faster than recomputing a rank-maximal matching completely using a known algorithm like that of Irving et al., which takes time O(min((r + n, r*sqrt(n))m).
operations-research  optimization  rostering  scheduling  dynamic-optimization  to-write-about  consider:representation  consider:multiobjective-optimization 
12 days ago
[1704.00565] Dynamic Planar Embeddings of Dynamic Graphs
We present an algorithm to support the dynamic embedding in the plane of a dynamic graph. An edge can be inserted across a face between two vertices on the face boundary (we call such a vertex pair linkable), and edges can be deleted. The planar embedding can also be changed locally by flipping components that are connected to the rest of the graph by at most two vertices.
Given vertices u,v, linkable(u,v) decides whether u and v are linkable in the current embedding, and if so, returns a list of suggestions for the placement of (u,v) in the embedding. For non-linkable vertices u,v, we define a new query, one-flip-linkable(u,v) providing a suggestion for a flip that will make them linkable if one exists. We support all updates and queries in O(log2n) time. Our time bounds match those of Italiano et al. for a static (flipless) embedding of a dynamic graph.
Our new algorithm is simpler, exploiting that the complement of a spanning tree of a connected plane graph is a spanning tree of the dual graph. The primal and dual trees are interpreted as having the same Euler tour, and a main idea of the new algorithm is an elegant interaction between top trees over the two trees via their common Euler tour.
graph-layout  dynamical-systems  constraint-satisfaction  multiobjective-optimization  dynamic-optimization  to-write-about  consider:simple-examples  rather-interesting 
12 days ago
[1610.07631] Dynamic Phases of Active Matter Systems with Quenched Disorder
Depinning and nonequilibrium transitions within sliding states in systems driven over quenched disorder arise across a wide spectrum of size scales ranging from atomic friction at the nanoscale, flux motion in type-II superconductors at the mesoscale, colloidal motion in disordered media at the microscale, and plate tectonics at geological length scales. Here we show that active matter or self-propelled particles interacting with quenched disorder under an external drive represents a new class of system that can also exhibit pinning-depinning phenomena, plastic flow phases, and nonequilibrium sliding transitions that are correlated with distinct morphologies and velocity-force curve signatures. When interactions with the substrate are strong, a homogeneous pinned liquid phase forms that depins plastically into a uniform disordered phase and then dynamically transitions first into a moving stripe coexisting with a pinned liquid and then into a moving phase separated state at higher drives. We numerically map the resulting dynamical phase diagrams as a function of external drive, substrate interaction strength, and self-propulsion correlation length. These phases can be observed for active matter moving through random disorder. Our results indicate that intrinsically nonequilibrium systems can exhibit additional nonequilibrium transitions when subjected to an external drive.
active-matter  simulation  rather-interesting  to-write-about  physics!  emergent-design  phase-transitions 
12 days ago
[1610.09787] Edward: A library for probabilistic modeling, inference, and criticism
Probabilistic modeling is a powerful approach for analyzing empirical information. We describe Edward, a library for probabilistic modeling. Edward's design reflects an iterative process pioneered by George Box: build a model of a phenomenon, make inferences about the model given data, and criticize the model's fit to the data. Edward supports a broad class of probabilistic models, efficient algorithms for inference, and many techniques for model criticism. The library builds on top of TensorFlow to support distributed training and hardware such as GPUs. Edward enables the development of complex probabilistic models and their algorithms at a massive scale.
machine-learning  framework  rather-interesting  representation  probabilistic-languages 
12 days ago
[1703.08052] Dynamic Bernoulli Embeddings for Language Evolution
Word embeddings are a powerful approach for unsupervised analysis of language. Recently, Rudolph et al. (2016) developed exponential family embeddings, which cast word embeddings in a probabilistic framework. Here, we develop dynamic embeddings, building on exponential family embeddings to capture how the meanings of words change over time. We use dynamic embeddings to analyze three large collections of historical texts: the U.S. Senate speeches from 1858 to 2009, the history of computer science ACM abstracts from 1951 to 2014, and machine learning papers on the Arxiv from 2007 to 2015. We find dynamic embeddings provide better fits than classical embeddings and capture interesting patterns about how language changes.
natural-language-processing  representation  rather-interesting  to-write-about  nudge-targets  consider:representation 
12 days ago
[1611.05321] Bootstrap, Review, Decode: Using Out-of-Domain Textual Data to Improve Image Captioning
We propose a novel way of using out-of-domain textual data to enhance the performance of existing image captioning systems. We evaluate this learning approach on a newly designed model that uses - and improves upon - building blocks from state-of-the-art methods. This model starts from detecting visual concepts present in an image which are then fed to a reviewer-decoder architecture with an attention mechanism. Unlike previous approaches that encode visual concepts using word embeddings, we instead suggest using regional image features which capture more intrinsic information. The main benefit of this architecture is that it synthesizes meaningful thought vectors that capture salient image properties and then applies a soft attentive decoder to decode the thought vectors and generate image captions. We evaluate our model on both Microsoft COCO and Flickr30K datasets and demonstrate that this model combined with our bootstrap learning method can largely improve performance and help the model to generate more accurate and diverse captions.
data-fusion  image-processing  deep-learning  rather-interesting  to-write-about  nudge-targets  consider:feature-discovery 
12 days ago
[1506.03662] Variance Reduced Stochastic Gradient Descent with Neighbors
Stochastic Gradient Descent (SGD) is a workhorse in machine learning, yet its slow convergence can be a computational bottleneck. Variance reduction techniques such as SAG, SVRG and SAGA have been proposed to overcome this weakness, achieving linear convergence. However, these methods are either based on computations of full gradients at pivot points, or on keeping per data point corrections in memory. Therefore speed-ups relative to SGD may need a minimal number of epochs in order to materialize. This paper investigates algorithms that can exploit neighborhood structure in the training data to share and re-use information about past stochastic gradients across data points, which offers advantages in the transient optimization phase. As a side-product we provide a unified convergence analysis for a family of variance reduction algorithms, which we call memorization algorithms. We provide experimental results supporting our theory.
numerical-methods  optimization  computational-complexity  horse-races  heuristics  to-write-about  compare-to:lexicase 
12 days ago
[1605.06561] DynaNewton - Accelerating Newton's Method for Machine Learning
Newton's method is a fundamental technique in optimization with quadratic convergence within a neighborhood around the optimum. However reaching this neighborhood is often slow and dominates the computational costs. We exploit two properties specific to empirical risk minimization problems to accelerate Newton's method, namely, subsampling training data and increasing strong convexity through regularization. We propose a novel continuation method, where we define a family of objectives over increasing sample sizes and with decreasing regularization strength. Solutions on this path are tracked such that the minimizer of the previous objective is guaranteed to be within the quadratic convergence region of the next objective to be optimized. Thereby every Newton iteration is guaranteed to achieve super-linear contractions with regard to the chosen objective, which becomes a moving target. We provide a theoretical analysis that motivates our algorithm, called DynaNewton, and characterizes its speed of convergence. Experiments on a wide range of data sets and problems consistently confirm the predicted computational savings.
numerical-methods  data-fusion  rather-interesting  machine-learning  computational-complexity  to-write-about  sometimes-it-depends 
12 days ago
[1610.01983] Driving in the Matrix: Can Virtual Worlds Replace Human-Generated Annotations for Real World Tasks?
Deep learning has rapidly transformed the state of the art algorithms used to address a variety of problems in computer vision and robotics. These breakthroughs have relied upon massive amounts of human annotated training data. This time consuming process has begun impeding the progress of these deep learning efforts. This paper describes a method to incorporate photo-realistic computer images from a simulation engine to rapidly generate annotated data that can be used for the training of machine learning algorithms. We demonstrate that a state of the art architecture, which is trained only using these synthetic annotations, performs better than the identical architecture trained on human annotated real-world data, when tested on the KITTI data set for vehicle detection. By training machine learning algorithms on a rich virtual world, real objects in real scenes can be learned and classified using synthetic data. This approach offers the possibility of accelerating deep learning's application to sensor-based classification problems like those that appear in self-driving cars. The source code and data to train and validate the networks described in this paper are made available for researchers.
simulation  engineering-design  ontology  approximation  training  to-write-about  consider:stress-testing 
12 days ago
[1608.08844] Snapping Graph Drawings to the Grid Optimally
In geographic information systems and in the production of digital maps for small devices with restricted computational resources one often wants to round coordinates to a rougher grid. This removes unnecessary detail and reduces space consumption as well as computation time. This process is called snapping to the grid and has been investigated thoroughly from a computational-geometry perspective. In this paper we investigate the same problem for given drawings of planar graphs under the restriction that their combinatorial embedding must be kept and edges are drawn straight-line. We show that the problem is NP-hard for several objectives and provide an integer linear programming formulation. Given a plane graph G and a positive integer w, our ILP can also be used to draw G straight-line on a grid of width w and minimum height (if possible).
graph-layout  computational-geometry  algorithms  rather-interesting  constraint-satisfaction  nudge-targets  consider:looking-to-see  approximation  performance-measure 
12 days ago
[1409.0499] Drawing Graphs within Restricted Area
We study the problem of selecting a maximum-weight subgraph of a given graph such that the subgraph can be drawn within a prescribed drawing area subject to given non-uniform vertex sizes. We develop and analyze heuristics both for the general (undirected) case and for the use case of (directed) calculation graphs which are used to analyze the typical mistakes that high school students make when transforming mathematical expressions in the process of calculating, for example, sums of fractions.
graph-layout  constraint-satisfaction  multiobjective-optimization  computational-geometry  parametrization  to-write-about  aesthetics 
12 days ago
[1305.0750] Multi-Sided Boundary Labeling
In the Boundary Labeling problem, we are given a set of n points, referred to as sites, inside an axis-parallel rectangle R, and a set of n pairwise disjoint rectangular labels that are attached to R from the outside. The task is to connect the sites to the labels by non-intersecting rectilinear paths, so-called leaders, with at most one bend.
In this paper, we study the Multi-Sided Boundary Labeling problem, with labels lying on at least two sides of the enclosing rectangle. We present a polynomial-time algorithm that computes a crossing-free leader layout if one exists. So far, such an algorithm has only been known for the cases in which labels lie on one side or on two opposite sides of R (here a crossing-free solution always exists). The case where labels may lie on adjacent sides is more difficult. We present efficient algorithms for testing the existence of a crossing-free leader layout that labels all sites and also for maximizing the number of labeled sites in a crossing-free leader layout. For two-sided boundary labeling with adjacent sides, we further show how to minimize the total leader length in a crossing-free layout.
computational-geometry  graph-layout  maps  constraint-satisfaction  multiobjective-optimization  performance-measure  rather-interesting  engineering-philosophy  to-write-about  good-examples-for-MO 
12 days ago
[1209.0830] Progress on Partial Edge Drawings
Recently, a new way of avoiding crossings in straight-line drawings of non-planar graphs has been investigated. The idea of partial edge drawings (PED) is to drop the middle part of edges and rely on the remaining edge parts called stubs. We focus on a symmetric model (SPED) that requires the two stubs of an edge to be of equal length. In this way, the stub at the other endpoint of an edge assures the viewer of the edge's existence. We also consider an additional homogeneity constraint that forces the stub lengths to be a given fraction δ of the edge lengths (δ-SHPED). Given length and direction of a stub, this model helps to infer the position of the opposite stub.
We show that, for a fixed stub--edge length ratio δ, not all graphs have a δ-SHPED. Specifically, we show that K241 does not have a 1/4-SHPED, while bandwidth-k graphs always have a Θ(1/k√)-SHPED. We also give bounds for complete bipartite graphs. Further, we consider the problem \textsc{MaxSPED} where the task is to compute the SPED of maximum total stub length that a given straight-line drawing contains. We present an efficient solution for 2-planar drawings and a 2-approximation algorithm for the dual problem.
graph-layout  computational-geometry  algorithms  constraint-satisfaction  rather-interesting  representation  to-write-about 
12 days ago
[0806.0253] On collinear sets in straight line drawings
We consider straight line drawings of a planar graph G with possible edge crossings. The \emph{untangling problem} is to eliminate all edge crossings by moving as few vertices as possible to new positions. Let fix(G) denote the maximum number of vertices that can be left fixed in the worst case. In the \emph{allocation problem}, we are given a planar graph G on n vertices together with an n-point set X in the plane and have to draw G without edge crossings so that as many vertices as possible are located in X. Let fit(G) denote the maximum number of points fitting this purpose in the worst case. As fix(G)≤fit(G), we are interested in upper bounds for the latter and lower bounds for the former parameter.
For each ϵ>0, we construct an infinite sequence of graphs with fit(G)=O(nσ+ϵ), where σ<0.99 is a known graph-theoretic constant, namely the shortness exponent for the class of cubic polyhedral graphs. To the best of our knowledge, this is the first example of graphs with fit(G)=o(n). On the other hand, we prove that fix(G)≥n/30‾‾‾‾√ for all G with tree-width at most 2. This extends the lower bound obtained by Goaoc et al. [Discrete and Computational Geometry 42:542-569 (2009)] for outerplanar graphs.
Our upper bound for fit(G) is based on the fact that the constructed graphs can have only few collinear vertices in any crossing-free drawing. To prove the lower bound for fix(G), we show that graphs of tree-width 2 admit drawings that have large sets of collinear vertices with some additional special properties.
graph-theory  computational-geometry  graph-layout  algorithms  rather-interesting  nudge-targets  consider:mathematical-recreations  consider:classification 
12 days ago
[1607.01196] Drawing Graphs on Few Lines and Few Planes
We investigate the problem of drawing graphs in 2D and 3D such that their edges (or only their vertices) can be covered by few lines or planes. We insist on straight-line edges and crossing-free drawings. This problem has many connections to other challenging graph-drawing problems such as small-area or small-volume drawings, layered or track drawings, and drawing graphs with low visual complexity. While some facts about our problem are implicit in previous work, this is the first treatment of the problem in its full generality. Our contribution is as follows.
We show lower and upper bounds for the numbers of lines and planes needed for covering drawings of graphs in certain graph classes. In some cases our bounds are asymptotically tight; in some cases we are able to determine exact values.
We relate our parameters to standard combinatorial characteristics of graphs (such as the chromatic number, treewidth, maximum degree, or arboricity) and to parameters that have been studied in graph drawing (such as the track number or the number of segments appearing in a drawing).
We pay special attention to planar graphs. For example, we show that there are planar graphs that can be drawn in 3-space on a lot fewer lines than in the plane.
graph-layout  computational-geometry  optimization  graph-theory  topology  rather-interesting  to-write-about  consider:feature-discovery  nudge-targets  consider:classification 
12 days ago
[1607.06136] Eliminating Depth Cycles among Triangles in Three Dimensions
Given n non-vertical pairwise disjoint triangles in 3-space, their vertical depth (above/below) relation may contain cycles. We show that, for any ε>0, the triangles can be cut into O(n3/2+ε) pieces, where each piece is a connected semi-algebraic set whose description complexity depends only on the choice of ε, such that the depth relation among these pieces is now a proper partial order. This bound is nearly tight in the worst case. We are not aware of any previous study of this problem with a subquadratic bound on the number of pieces.
This work extends the recent study by two of the authors on eliminating depth cycles among lines in 3-space. Our approach is again algebraic, and makes use of a recent variant of the polynomial partitioning technique, due to Guth, which leads to a recursive procedure for cutting the triangles. In contrast to the case of lines, our analysis here is considerably more involved, due to the two-dimensional nature of the objects being cut, so additional tools, from topology and algebra, need to be brought to bear.
Our result essentially settles a 35-year-old open problem in computational geometry, motivated by hidden-surface removal in computer graphics.
computational-geometry  algorithms  hidden-line-removal  rather-interesting  computational-complexity  constraint-satisfaction  nudge-targets  consider:rediscovery 
13 days ago
[1612.08473] Doodles on surfaces I: An introduction to their basic properties
Doodles were introduced in [R. Fenn and P. Taylor, Introducing doodles, Topology of low-dimensional manifolds, pp. 37--43, Lecture Notes in Math., 722, Springer, Berlin, 1979] but were restricted to embedded circles in the 2-sphere. Khovanov, [M. Khovanov, Doodle groups, Trans. Amer. Math. Soc. 349 (1997), 2297--2315], extended the idea to immersed circles in the 2-sphere. In this paper we further extend the range of doodles to any closed orientable surfaces.
topology  geometry  to-understand 
13 days ago
[1605.08107] Dominance Products and Faster Algorithms for High-Dimensional Closest Pair under $L_infty$
We give improved algorithmic time bounds for two fundamental problems, and establish a new complexity connection between them. The first is computing dominance product: given a set of n points p1,…,pn in ℝd, compute a matrix D, such that D[i,j]=∣∣{k∣pi[k]≤pj[k]}∣∣; this is the number of coordinates at which pj dominates pi. Dominance product computation has often been applied in algorithm design over the last decade.
The second problem is the L∞ Closest Pair in high dimensions: given a set S of n points in ℝd, find a pair of distinct points in S at minimum distance under the L∞ metric. When d is constant, there are efficient algorithms that solve this problem, and fast approximate solutions are known for general d. However, obtaining an exact solution in very high dimensions seems to be much less understood. We significantly simplify and improve previous results, showing that the problem can be solved by a deterministic strongly-polynomial algorithm that runs in O(DP(n,d)logn) time, where DP(n,d) is the time bound for computing the dominance product for n points in ℝd. For integer coordinates from some interval [−M,M], and for d=nr for some r>0, we obtain an algorithm that runs in Õ (min{Mnω(1,r,1),DP(n,d)}) time, where ω(1,r,1) is the exponent of multiplying an n×nr matrix by an nr×n matrix.
multiobjective-optimization  matrices  algorithms  rather-interesting  to-understand  consider:lexicase 
13 days ago
[1505.07818] Domain-Adversarial Training of Neural Networks
We introduce a new representation learning approach for domain adaptation, in which data at training and test time come from similar but different distributions. Our approach is directly inspired by the theory on domain adaptation suggesting that, for effective domain transfer to be achieved, predictions must be made based on features that cannot discriminate between the training (source) and test (target) domains. The approach implements this idea in the context of neural network architectures that are trained on labeled data from the source domain and unlabeled data from the target domain (no labeled target-domain data is necessary). As the training progresses, the approach promotes the emergence of features that are (i) discriminative for the main learning task on the source domain and (ii) indiscriminate with respect to the shift between the domains. We show that this adaptation behaviour can be achieved in almost any feed-forward model by augmenting it with few standard layers and a new gradient reversal layer. The resulting augmented architecture can be trained using standard backpropagation and stochastic gradient descent, and can thus be implemented with little effort using any of the deep learning packages. We demonstrate the success of our approach for two distinct classification problems (document sentiment analysis and image classification), where state-of-the-art domain adaptation performance on standard benchmarks is achieved. We also validate the approach for descriptor learning task in the context of person re-identification application.
machine-learning  performance-measure  rather-interesting  to-write-about  nudge-targets  consider:looking-to-see  consider:error-measures 
13 days ago
[1606.03686] Does Having More Options Mean Harder to Reach Consensus?
We generalize a binary majority-vote model on adaptive networks to a plurality-vote counterpart. When opinions are uniformly distributed in the population of voters in the initial state, it is found that having more available opinions in the initial state actually accelerate the time to consensus. In particular, we investigate the three-state plurality-vote model. While time to consensus in two state model scales exponentially with population size N, for finite-size system, there is a non-zero probability that either the population reaches the consensus state in a time that is very short and independent of N (in the heterophily regime), or in a time that scales exponentially with N but is still much faster than two-state model.
voting-models  agent-based  evolutionary-economics  diversity  rather-interesting  to-write-about  looking-to-see 
13 days ago
[1603.05691] Do Deep Convolutional Nets Really Need to be Deep and Convolutional?
Yes, they do. This paper provides the first empirical demonstration that deep convolutional models really need to be both deep and convolutional, even when trained with methods such as distillation that allow small or shallow models of high accuracy to be trained. Although previous research showed that shallow feed-forward nets sometimes can learn the complex functions previously learned by deep nets while using the same number of parameters as the deep models they mimic, in this paper we demonstrate that the same methods cannot be used to train accurate models on CIFAR-10 unless the student models contain multiple layers of convolution. Although the student models do not have to be as deep as the teacher model they mimic, the students need multiple convolutional layers to learn functions of comparable accuracy as the deep convolutional teacher.
good-question  neural-networks  deep-learning  rather-interesting  approximation  heuristics  nudge-targets  consider:re-approximation 
13 days ago
[1604.07309] Division by zero
For any sufficiently strong theory of arithmetic, the set of Diophantine equations provably unsolvable in the theory is algorithmically undecidable, as a consequence of the MRDP theorem. In contrast, we show decidability of Diophantine equations provably unsolvable in Robinson's arithmetic Q. The argument hinges on an analysis of a particular class of equations, hitherto unexplored in Diophantine literature. We also axiomatize the universal fragment of Q in the process.
mathematics  to-understand  /shrug 
13 days ago
[1703.10970] Diversity of preferences can increase collective welfare in sequential exploration problems
In search engines, online marketplaces and other human-computer interfaces large collectives of individuals sequentially interact with numerous alternatives of varying quality. In these contexts, trial and error (exploration) is crucial for uncovering novel high-quality items or solutions, but entails a high cost for individual users. Self-interested decision makers, are often better off imitating the choices of individuals who have already incurred the costs of exploration. Although imitation makes sense at the individual level, it deprives the group of additional information that could have been gleaned by individual explorers. In this paper we show that in such problems, preference diversity can function as a welfare enhancing mechanism. It leads to a consistent increase in the quality of the consumed alternatives that outweighs the increased cost of search for the users.
wisdom-of-crowds  diversity  exploration-and-exploitation  collective-intelligence  game-theory  to-write-about 
13 days ago
[1011.4245] When the optimal is not the best: parameter estimation in complex biological models
Background: The vast computational resources that became available during the past decade enabled the development and simulation of increasingly complex mathematical models of cancer growth. These models typically involve many free parameters whose determination is a substantial obstacle to model development. Direct measurement of biochemical parameters in vivo is often difficult and sometimes impracticable, while fitting them under data-poor conditions may result in biologically implausible values.
Results: We discuss different methodological approaches to estimate parameters in complex biological models. We make use of the high computational power of the Blue Gene technology to perform an extensive study of the parameter space in a model of avascular tumor growth. We explicitly show that the landscape of the cost function used to optimize the model to the data has a very rugged surface in parameter space. This cost function has many local minima with unrealistic solutions, including the global minimum corresponding to the best fit.
Conclusions: The case studied in this paper shows one example in which model parameters that optimally fit the data are not necessarily the best ones from a biological point of view. To avoid force-fitting a model to a dataset, we propose that the best model parameters should be found by choosing, among suboptimal parameters, those that match criteria other than the ones used to fit the model. We also conclude that the model, data and optimization approach form a new complex system, and point to the need of a theory that addresses this problem more generally.
optimization  biophysics  noise  stochastic-resonance  modeling  rather-interesting  to-write-about  approximation  performance-measure 
13 days ago
[1612.09268] The ontogeny of discourse structure mimics the development of literature
Discourse varies with age, education, psychiatric state and historical epoch, but the ontogenetic and cultural dynamics of discourse structure remain to be quantitatively characterized. To this end we investigated word graphs obtained from verbal reports of 200 subjects ages 2-58, and 676 literary texts spanning ~5,000 years. In healthy subjects, lexical diversity, graph size, and long-range recurrence departed from initial near-random levels through a monotonic asymptotic increase across ages, while short-range recurrence showed a corresponding decrease. These changes were explained by education and suggest a hierarchical development of discourse structure: short-range recurrence and lexical diversity stabilize after elementary school, but graph size and long-range recurrence only stabilize after high school. This gradual maturation was blurred in psychotic subjects, who maintained in adulthood a near-random structure. In literature, monotonic asymptotic changes over time were remarkable: While lexical diversity, long-range recurrence and graph size increased away from near-randomness, short-range recurrence declined, from above to below random levels. Bronze Age texts are structurally similar to childish or psychotic discourses, but subsequent texts converge abruptly to the healthy adult pattern around the onset of the Axial Age (800-200 BC), a period of pivotal cultural change. Thus, individually as well as historically, discourse maturation increases the range of word recurrence away from randomness.
oh-my  psychology  linguistics  cognition  Big-Theories  ontology-recapitulates-Haeckel-again  to-write-about 
13 days ago
[1110.0373] An excitable electronic circuit as a sensory neuron model
An electronic circuit device, inspired on the FitzHugh-Nagumo model of neuronal excitability, was constructed and shown to operate with characteristics compatible with those of biological sensory neurons. The nonlinear dynamical model of the electronics quantitatively reproduces the experimental observations on the circuit, including the Hopf bifurcation at the onset of tonic spiking. Moreover, we have implemented an analog noise generator as a source to study the variability of the spike trains. When the circuit is in the excitable regime, coherence resonance is observed. At sufficiently low noise intensity the spike trains have Poisson statistics, as in many biological neurons. The transfer function of the stochastic spike trains has a dynamic range of 6 dB, close to experimental values for real olfactory receptor neurons.
neural-networks  neurology  biophysics  electronics  rather-interesting  simulation  emulation  to-write-about  dynamical-systems 
13 days ago
The Problem with Philanthropy | Public Books
The “myth” Kohl-Arenas identifies is the belief that individuals and communities can change their material circumstances in the absence of any change to the systems and policies that govern those circumstances. In the US, our national narrative places the lion’s share of responsibility on individuals: responsibility for poverty on the poor, for mental illness on the mentally ill and their families, for incarceration on the incarcerated. As a wealthy, developed nation, we are a bewildering outlier in our refusal to take more communal responsibility for our brethren. When people do organize to care for one another, and in doing so discover that life struggles are linked to structural problems in need of policy solutions, they are often demoralized to find that funders shy away from any work that would promote policy change.
philanthropy  public-policy  cultural-engineering  cultural-assumptions  corporatism  revolution 
13 days ago
[1608.04481] Lecture Notes on Randomized Linear Algebra
These are lecture notes that are based on the lectures from a class I taught on the topic of Randomized Linear Algebra (RLA) at UC Berkeley during the Fall 2013 semester.
matrices  linear-algebra  stochastic-systems  algorithms  optimization  to-understand  to-read  consider:lexicase 
13 days ago
[1104.5557] Randomized algorithms for matrices and data
Randomized algorithms for very large matrix problems have received a great deal of attention in recent years. Much of this work was motivated by problems in large-scale data analysis, and this work was performed by individuals from many different research communities. This monograph will provide a detailed overview of recent work on the theory of randomized matrix algorithms as well as the application of those ideas to the solution of practical problems in large-scale data analysis. An emphasis will be placed on a few simple core ideas that underlie not only recent theoretical advances but also the usefulness of these tools in large-scale data applications. Crucial in this context is the connection with the concept of statistical leverage. This concept has long been used in statistical regression diagnostics to identify outliers; and it has recently proved crucial in the development of improved worst-case matrix algorithms that are also amenable to high-quality numerical implementation and that are useful to domain scientists. Randomized methods solve problems such as the linear least-squares problem and the low-rank matrix approximation problem by constructing and operating on a randomized sketch of the input matrix. Depending on the specifics of the situation, when compared with the best previously-existing deterministic algorithms, the resulting randomized algorithms have worst-case running time that is asymptotically faster; their numerical implementations are faster in terms of clock-time; or they can be implemented in parallel computing environments where existing numerical algorithms fail to run at all. Numerous examples illustrating these observations will be described in detail.
via:arthegall  data-analysis  matrices  feature-extraction  learning-from-data  data-mining  rather-interesting  to-read  to-understand 
13 days ago
[1409.4178] The frustrated brain: From dynamics on motifs to communities and networks
Cognitive function depends on an adaptive balance between flexible dynamics and integrative processes in distributed cortical networks. Patterns of zero-lag synchrony likely underpin numerous perceptual and cognitive functions. Synchronization fulfils integration by reducing entropy, whilst adaptive function mandates that a broad variety of stable states be readily accessible. Here, we elucidate two complementary influences on patterns of zero-lag synchrony that derive from basic properties of brain networks. First, mutually coupled pairs of neuronal subsystems -- resonance pairs -- promote stable zero-lag synchrony amongst the small motifs in which they are embedded, and whose effects can propagate along connected chains. Second, frustrated closed-loop motifs disrupt synchronous dynamics, enabling metastable configurations of zero-lag synchrony to coexist. We document these two complementary influences in small motifs and illustrate how these effects underpin stable versus metastable phase-synchronization patterns in prototypical modular networks and in large-scale cortical networks of the macaque (CoCoMac). We find that the variability of synchronization patterns depends on the inter-node time delay, increases with the network size, and is maximized for intermediate coupling strengths. We hypothesize that the dialectic influences of resonance versus frustration may form a dynamic substrate for flexible neuronal integration, an essential platform across diverse cognitive processes.
dynamical-systems  network-theory  coupled-oscillators  emergent-design  looking-to-see  systems-biology  nudge-targets  consider:robustness  consider:looking-to-see 
13 days ago
[1304.5008] Mechanisms of Zero-Lag Synchronization in Cortical Motifs
Zero-lag synchronization between distant cortical areas has been observed in a diversity of experimental data sets and between many different regions of the brain. Several computational mechanisms have been proposed to account for such isochronous synchronization in the presence of long conduction delays: Of these, the phenomenon of "dynamical relaying" - a mechanism that relies on a specific network motif - has proven to be the most robust with respect to parameter mismatch and system noise. Surprisingly, despite a contrary belief in the community, the common driving motif is an unreliable means of establishing zero-lag synchrony. Although dynamical relaying has been validated in empirical and computational studies, the deeper dynamical mechanisms and comparison to dynamics on other motifs is lacking. By systematically comparing synchronization on a variety of small motifs, we establish that the presence of a single reciprocally connected pair - a "resonance pair" - plays a crucial role in disambiguating those motifs that foster zero-lag synchrony in the presence of conduction delays (such as dynamical relaying) from those that do not (such as the common driving triad). Remarkably, minor structural changes to the common driving motif that incorporate a reciprocal pair recover robust zero-lag synchrony. The findings are observed in computational models of spiking neurons, populations of spiking neurons and neural mass models, and arise whether the oscillatory systems are periodic, chaotic, noise-free or driven by stochastic inputs. The influence of the resonance pair is also robust to parameter mismatch and asymmetrical time delays amongst the elements of the motif. We call this manner of facilitating zero-lag synchrony resonance-induced synchronization, outline the conditions for its occurrence, and propose that it may be a general mechanism to promote zero-lag synchrony in the brain.
systems-biology  dynamical-systems  coupled-oscillators  engineering-design  emergent-design  looking-to-see  nudge-targets  consider:looking-to-see  consider:robustness  consider:reQ-like-systems 
13 days ago
[1507.05249] Diversity improves performance in excitable networks
As few real systems comprise indistinguishable units, diversity is a hallmark of nature. Diversity among interacting units shapes properties of collective behavior such as synchronization and information transmission. However, the benefits of diversity on information processing at the edge of a phase transition, ordinarily assumed to emerge from identical elements, remain largely unexplored. Analyzing a general model of excitable systems with heterogeneous excitability, we find that diversity can greatly enhance optimal performance (by two orders of magnitude) when distinguishing incoming inputs. Heterogeneous systems possess a subset of specialized elements whose capability greatly exceeds that of the nonspecialized elements. Nonetheless, the behavior of the whole network can outperform all subgroups. We also find that diversity can yield multiple percolation, with performance optimized at tricriticality. Our results are robust in specific and more realistic neuronal systems comprising a combination of excitatory and inhibitory units, and indicate that diversity-induced amplification can be harnessed by neuronal systems for evaluating stimulus intensities.
network-theory  collective-behavior  physics!  coupled-oscillators  simulation  it's-more-complicated-than-you-think  to-write-about  nudge-targets  consider:engineering-design 
13 days ago
[1611.01285] Naive Diversification Preferences and their Representation
A widely applied diversification paradigm is the naive diversification choice heuristic. It stipulates that an economic agent allocates equal decision weights to given choice alternatives independent of their individual characteristics. This article provides mathematically and economically sound choice theoretic foundations for the naive approach to diversification. We axiomatize naive diversification by defining it as a preference for equality over inequality and derive its relationship to the classical diversification paradigm. In particular, we show that (i) the notion of permutation invariance lies at the core of naive diversification and that an economic agent is a naive diversifier if and only if his preferences are convex and permutation invariant; (ii) Schur-concave utility functions capture the idea of being inequality averse on top of being risk averse; and (iii) the transformations, which rebalance unequal decision weights to equality, are characterized in terms of their implied turnover.
portfolio-theory  risk-management  multiobjective-optimization  financial-engineering  to-write-about  nudge-targets  consider:rediscovery 
13 days ago
[1501.01573] The Temporal Dimension of Risk
Multi-period measures of risk account for the path that the value of an investment portfolio takes. In the context of probabilistic risk measures, the focus has traditionally been on the magnitude of investment loss and not on the dimension associated with the passage of time. In this paper, the concept of temporal path-dependent risk measure is mathematically formalized to capture the risk associated with the temporal dimension of a stochastic process. We discuss the properties of temporal measures of risk and show that they can never be coherent. We then study the temporal dimension of investment drawdown, its duration, which measures the length of excursions below a running maximum. Its properties in the context of risk measures are analyzed both theoretically and empirically. In particular, we show that duration captures serial correlation in the returns of two major asset classes. We conclude by discussing the challenges of path-dependent temporal risk estimation in practice.
portfolio-theory  risk  risk-management  define-your-terms  financial-engineering  to-write-about  time-series  data-analysis  planning 
13 days ago
[1404.7493] Drawdown: From Practice to Theory and Back Again
Maximum drawdown, the largest cumulative loss from peak to trough, is one of the most widely used indicators of risk in the fund management industry, but one of the least developed in the context of measures of risk. We formalize drawdown risk as Conditional Expected Drawdown (CED), which is the tail mean of maximum drawdown distributions. We show that CED is a degree one positive homogenous risk measure, so that it can be linearly attributed to factors; and convex, so that it can be used in quantitative optimization. We empirically explore the differences in risk attributions based on CED, Expected Shortfall (ES) and volatility. An important feature of CED is its sensitivity to serial correlation. In an empirical study that fits AR(1) models to US Equity and US Bonds, we find substantially higher correlation between the autoregressive parameter and CED than with ES or with volatility.
portfolio-theory  performance-measure  financial-engineering  multiobjective-optimization  consider:feature-discovery  to-write-about  algorithms  representation 
13 days ago
[1507.02025] Diversification Preferences in the Theory of Choice
Diversification represents the idea of choosing variety over uniformity. Within the theory of choice, desirability of diversification is axiomatized as preference for a convex combination of choices that are equivalently ranked. This corresponds to the notion of risk aversion when one assumes the von-Neumann-Morgenstern expected utility model, but the equivalence fails to hold in other models. This paper studies axiomatizations of the concept of diversification and their relationship to the related notions of risk aversion and convex preferences within different choice theoretic models. Implications of these notions on portfolio choice are discussed. We cover model-independent diversification preferences, preferences within models of choice under risk, including expected utility theory and the more general rank-dependent expected utility theory, as well as models of choice under uncertainty axiomatized via Choquet expected utility theory. Remarks on interpretations of diversification preferences within models of behavioral choice are given in the conclusion.
game-theory  how-much-is-that-in-utiles?  economics  preferences  portfolio-theory  decision-making  to-write-about  nudge-targets  consider:looking-to-see  consider:performance-measures  consider:multiobjective-versions 
13 days ago
[1609.08312] Duality between Feature Selection and Data Clustering
The feature-selection problem is formulated from an information-theoretic perspective. We show that the problem can be efficiently solved by an extension of the recently proposed info-clustering paradigm. This reveals the fundamental duality between feature selection and data clustering,which is a consequence of the more general duality between the principal partition and the principal lattice of partitions in combinatorial optimization.
information-theory  modeling  define-your-terms  feature-extraction  to-understand  connections-made  statistics 
13 days ago
[1705.02249] Dynamics of Voter Models on Simple and Complex Network
This is a brief tutorial review of the dynamics of the voter model and the invasion process on complex networks.
voting  network-theory  SFI  tutorial  to-write-about  evolutionary-economics  agent-based 
13 days ago
[1705.02072] Dynamics of slow and fast systems on complex networks
We study the occurrence of frequency synchronised states with tunable emergent frequencies in a network of connected systems. This is achieved by the interplay between time scales of nonlinear dynamical systems connected to form a network, where out of N systems, m evolve on a slower time scale. In such systems, in addition to frequency synchronised states, we also observe amplitude death, synchronised clusters and multifrequency states. We report an interesting cross over behaviour from fast to slow collective dynamics as the number of slow systems m increases. The transition to amplitude death is analysed in detail for minimal network configurations of 3 and 4 systems which actually form possible motifs of the full network.
nonlinear-dynamics  coupled-oscillators  systems  pattern-discovery  rather-interesting  to-write-about  to-do  consider:looking-to-see 
13 days ago
Dragged from the plane in academia…time for a culture hack – Academic Irregularities
In another blog, Jana Bacevic wonders why, when there are so many critiques of the neoliberal, managerial university, is there so little resistance? I think there may not be so much mystery in this. All academics have been made to feel precarious and unworthy and it has led to a focus on meeting the metrics and staying ahead of the escalating demands of the university’s performance expectations. Raising a voice or organising with colleagues to change these absurd conditions seems too much like a risk when there is a mortgage to pay and children to feed. Managers know this, which is why they build structures to feed on academic insecurities – ‘imposter syndrome’- and incorporate employees into an anxiety machine (Hall and Bowles, 2016). So it is as much as academics dare, to reflect and write about their experiences in a rather dispassionate analytic way. Even this leads to a Catch 22 situation whereby academics find themselves required to publish, but publish to satisfy an urge to rebel by tilting at the REF windmill with their (published and peer-reviewed) critique.
academic-culture  precariat  corporatism  cultural-norms 
14 days ago
Universities, neoliberalisation, and the (im)possibility of critique – Jana Bacevic
(c) This doesn’t get emphasised enough, but one of the reasons why people vie for positions in the academia is because at least it offers a degree of intellectual satisfaction, in opposition to what Graeber has termed the ever-growing number of ‘bullshit jobs’. So, one of the ways of making working conditions in the academia more decent is by making working conditions outside of academia more decent – and, perhaps, by decentralising a bit the monopoly on knowledge work that the academia holds. Not, however, in the neoliberal outsourcing/’creative hubs’ model, which unfortunately mostly serves to generate value for existing centres while further depleting the peripheries.
academia  academic-culture  monopsony  life-o'-the-mind  worklife 
14 days ago
The United States of Work | New Republic
Anderson’s most provocative argument is that large companies, the institutions that employ most workers, amount to a de facto form of government, exerting massive and intrusive power in our daily lives. Unlike the state, these private governments are able to wield power with little oversight, because the executives and boards of directors that rule them are accountable to no one but themselves. Although they exercise their power to varying degrees and through both direct and “soft” means, employers can dictate how we dress and style our hair, when we eat, when (and if) we may use the toilet, with whom we may partner and under what arrangements. Employers may subject our bodies to drug tests; monitor our speech both on and off the job; require us to answer questionnaires about our exercise habits, off-hours alcohol consumption, and childbearing intentions; and rifle through our belongings. If the state held such sweeping powers, Anderson argues, we would probably not consider ourselves free men and women.
corporatism  via:bkerr  labor  politics  political-economy  cultural-assumptions  worklife  not-encouraging 
14 days ago
[1705.01088] Visual Attribute Transfer through Deep Image Analogy
We propose a new technique for visual attribute transfer across images that may have very different appearance but have perceptually similar semantic structure. By visual attribute transfer, we mean transfer of visual information (such as color, tone, texture, and style) from one image to another. For example, one image could be that of a painting or a sketch while the other is a photo of a real scene, and both depict the same type of scene.
Our technique finds semantically-meaningful dense correspondences between two input images. To accomplish this, it adapts the notion of "image analogy" with features extracted from a Deep Convolutional Neutral Network for matching; we call our technique Deep Image Analogy. A coarse-to-fine strategy is used to compute the nearest-neighbor field for generating the results. We validate the effectiveness of our proposed method in a variety of cases, including style/texture transfer, color/style swap, sketch/painting to photo, and time lapse.
via:twitter  image-analogies  deep-learning  neural-networks  algorithms  multiobjective-optimization  to-write-about  to-understand  nudge-targets  consider:objective-partitioning 
15 days ago
[1510.05464v3] Generation of real algebraic loci via complex detours
We discuss the locus generation algorithm used by the dynamic geometry software Cinderella, and how it uses complex detours to resolve singularities. We show that the algorithm is independent of the orientation of its complex detours. We conjecture that the algorithm terminates if it takes small enough complex detours and small enough steps on every complex detour. Moreover, we introduce a variant of the algorithm that possibly generates entire real connected components of real algebraic loci. Several examples illustrate its use for organic generation of real algebraic loci. Another example shows how we can apply the algorithm to simulate mechanical linkages. Apparently, the use of complex detours produces physically reasonable motion of such linkages.
plane-geometry  algorithms  rather-interesting  nudge-targets  consider:looking-to-see 
15 days ago
[1507.07970v2] Dividing the circle
There are known constructions for some regular polygons, usually inscribed in a circle, but not for all polygons - the Gauss-Wantzel Theorem states precisely which ones can be constructed.
The constructions differ greatly from one polygon to the other. There are, however, general processes for determining the side of the n-gon (approximately, but sometimes with great precision), which we describe in this paper. We present a joint mathematical analysis of the so-called Bion and Tempier approximation methods, comparing the errors and trying to explain why these constructions would work at all.
compass-and-straightedge  plane-geometry  construction  approximation  nudge-targets  consider:rediscovery 
15 days ago
[math/0411380] Cosine products, Fourier transforms, and random sums
We investigate several infinite product of cosines and find the closed form using the Fourier transform. The answers provide limiting distributions for some elementary probability experiments.
mathematical-recreations  history  trigonometry  algebra  nudge-targets  consider:looking-to-see  consider:novelty-search 
15 days ago
[1208.1329] The multiplication game
The multiplication game is a two-person game in which each player chooses a positive integer without knowledge of the other player's number. The two numbers are then multiplied together and the first digit of the product determines the winner. Rather than analyzing this game directly, we consider a closely related game in which the players choose positive real numbers between 1 and 10, multiply them together, and move the decimal point, if necessary, so that the result is between 1 and 10. The mixed strategies are probability distributions on this interval, and it is shown that for both players it is optimal to choose their numbers from the Benford distribution. Furthermore, this strategy is optimal for any winning set, and the probability of winning is the Benford measure of the player's winning set. Using these results we prove that the original game in which the players choose integers has a well-defined value and that strategies exist that are arbitrarily close to optimal. Finally, we consider generalizations of the game in which players choose elements from a compact topological group and show that choosing them according to Haar measure is an optimal strategy.
mathematical-recreations  game-theory  Benford's-law  number-theory  to-write-about  consider:looking-to-see  nudge-targets 
15 days ago
[1311.6511] Intransitive Dice
We consider n-sided dice whose face values lie between 1 and n and whose faces sum to n(n+1)/2. For two dice A and B, define A≻B if it is more likely for A to show a higher face than B. Suppose k such dice A1,…,Ak are randomly selected. We conjecture that the probability of ties goes to 0 as n grows. We conjecture and provide some supporting evidence that---contrary to intuition---each of the 2(k2) assignments of ≻ or ≺ to each pair is equally likely asymptotically. For a specific example, suppose we randomly select k dice A1,…,Ak and observe that A1≻A2≻…≻Ak. Then our conjecture asserts that the outcomes Ak≻A1 and A1≺Ak both have probability approaching 1/2 as n→∞.
combinatorics  mathematical-recreations  probability-theory  to-write-about  nudge-targets  consider:engineering-design  consider:feature-discovery 
15 days ago
[1401.2493] Guessing games
In a guessing game, players guess the value of a random real number selected using some probability density function. The winner may be determined in various ways; for example, a winner can be a player whose guess is closest in magnitude to the target or a winner can be a player coming closest without guessing higher than the target. We study optimal strategies for players in these games and determine some of them for two, three, and four players.
probability-theory  game-theory  games  mathematical-recreations  strategy  nudge-targets  consider:looking-to-see 
15 days ago
[1505.07363] An Enumeration of the Equivalence Classes of Self-Dual Matrix Codes
As a result of their applications in network coding, space-time coding, and coding for criss-cross errors, matrix codes have garnered significant attention; in various contexts, these codes have also been termed rank-metric codes, space-time codes over finite fields, and array codes. We focus on characterizing matrix codes that are both efficient (have high rate) and effective at error correction (have high minimum rank-distance). It is well known that the inherent trade-off between dimension and minimum distance for a matrix code is reversed for its dual code; specifically, if a matrix code has high dimension and low minimum distance, then its dual code will have low dimension and high minimum distance. With an aim towards finding codes with a perfectly balanced trade-off, we study self-dual matrix codes. In this work, we develop a framework based on double cosets of the matrix-equivalence maps to provide a complete classification of the equivalence classes of self-dual matrix codes, and we employ this method to enumerate the equivalence classes of these codes for small parameters.
information-theory  matrices  combinatorics  rather-interesting  to-write-about  nudge-targets  consider:feature-discovery  consider:rediscovery 
15 days ago
[1409.5531] A mathematical theory of resources
In many different fields of science, it is useful to characterize physical states and processes as resources. Chemistry, thermodynamics, Shannon's theory of communication channels, and the theory of quantum entanglement are prominent examples. Questions addressed by a theory of resources include: Which resources can be converted into which other ones? What is the rate at which arbitrarily many copies of one resource can be converted into arbitrarily many copies of another? Can a catalyst help in making an impossible transformation possible? How does one quantify the resource? Here, we propose a general mathematical definition of what constitutes a resource theory. We prove some general theorems about how resource theories can be constructed from theories of processes wherein there is a special class of processes that are implementable at no cost and which define the means by which the costly states and processes can be interconverted one to another. We outline how various existing resource theories fit into our framework. Our abstract characterization of resource theories is a first step in a larger project of identifying universal features and principles of resource theories. In this vein, we identify a few general results concerning resource convertibility.
systems  formalization  rather-interesting  to-understand  to-write-about  systems-biology  representation 
15 days ago
Best Git Client 2017 - Features | GitKraken
GitKraken is the only Git client built on Electron, allowing it to run natively on Windows, Mac and Linux desktop systems. Enjoy the same luxurious experience across all three!
via:many  git  software-development  UI  to-try 
15 days ago
[1705.00186] Cyclic Hypergraph Degree Sequences
The problem of efficiently characterizing degree sequences of simple hypergraphs is a fundamental long-standing open problem in Graph Theory. Several results are known for restricted versions of this problem. This paper adds to the list of sufficient conditions for a degree sequence to be {\em hypergraphic}. This paper proves a combinatorial lemma about cyclically permuting the columns of a binary table with length n binary sequences as rows. We prove that for any set of cyclic permutations acting on its columns, the resulting table has all of its 2n rows distinct. Using this property, we first define a subset {\em cyclic hyper degrees} of hypergraphic sequences and show that they admit a polynomial time recognition algorithm. Next, we prove that there are at least 2(n−1)(n−2)2 {\em cyclic hyper degrees}, which also serves as a lower bound on the number of {\em hypergraphic} sequences. The {\em cyclic hyper degrees} also enjoy a structural characterization, they are the integral points contained in the union of some n-dimensional rectangles.
hypergraphs  combinatorics  rather-interesting  classification  feature-discovery  algorithms  computational-complexity  performance-measure  nudge-targets  consider:looking-to-see 
15 days ago
[1607.08597] Efficient modularity optimization by self-avoiding walk
Different kinds of random walks have showed to be useful in the study of the structural properties of complex networks. Among them, the restricted dynamics of the self-avoiding random walk (SAW), which reaches only unvisited vertices in the same walk, has been succesfully used in network exploration. SAWs are therefore a promising tool to investigate community structures in networks. Despite its importance, community detection remains an open problem due to the high computational complexity of the associated optimization problem and a lack of a unique formal definition of communities. In this work, we propose a SAW-based modularity optimization algorithm to extract the community distribution of a network that achieves high modularity scores. We combined SAW with principal component analyses to define the dissimilarity measure and use agglomerative hierarchical clustering. To evaluate the performance of this algorithm we compare it with three popular methods for community detection: Girvan-Newman, Fastgreedy and Walktrap, using two types of synthetic networks and six well-known real world cases.
network-theory  feature-construction  random-walks  algorithms  rather-interesting  nudge-targets  consider:approximation  computational-complexity 
15 days ago
[1705.00317] Non-polynomial Worst-Case Analysis of Recursive Programs
We study the problem of developing efficient approaches for proving worst-case bounds of non-deterministic recursive programs. Ranking functions are sound and complete for proving termination and worst-case bounds of nonrecursive programs. First, we apply ranking functions to recursion, resulting in measure functions. We show that measure functions provide a sound and complete approach to prove worst-case bounds of non-deterministic recursive programs. Our second contribution is the synthesis of measure functions in nonpolynomial forms. We show that non-polynomial measure functions with logarithm and exponentiation can be synthesized through abstraction of logarithmic or exponentiation terms, Farkas' Lemma, and Handelman's Theorem using linear programming. While previous methods obtain worst-case polynomial bounds, our approach can synthesize bounds of the form (nlogn) as well as (nr) where r is not an integer. We present experimental results to demonstrate that our approach can obtain efficiently worst-case bounds of classical recursive algorithms such as (i) Merge-Sort, the divide-and-conquer algorithm for the Closest-Pair problem, where we obtain (nlogn) worst-case bound, and (ii) Karatsuba's algorithm for polynomial multiplication and Strassen's algorithm for matrix multiplication, where we obtain (nr) bound such that r is not an integer and close to the best-known bounds for the respective algorithms.
computer-science  recursion  algorithms  to-understand  benchmarking  computational-complexity 
15 days ago
[1608.00771] Smart Contract Templates: foundations, design landscape and research directions
In this position paper, we consider some foundational topics regarding smart contracts (such as terminology, automation, enforceability, and semantics) and define a smart contract as an automatable and enforceable agreement. We explore a simple semantic framework for smart contracts, covering both operational and non-operational aspects, and describe templates and agreements for legally-enforceable smart contracts, based on legal documents. Building upon the Ricardian Contract, we identify operational parameters in the legal documents and use these to connect legal agreements to standardised code. We also explore the design landscape, including increasing sophistication of parameters, increasing use of common standardised code, and long-term research.
law  contracts  to-write-about  formalization  ontology  software-development-is-not-programming  law-is-not-code-writing 
15 days ago
[1703.07915] Perspective: Energy Landscapes for Machine Learning
Machine learning techniques are being increasingly used as flexible non-linear fitting and prediction tools in the physical sciences. Fitting functions that exhibit multiple solutions as local minima can be analysed in terms of the corresponding machine learning landscape. Methods to explore and visualise molecular potential energy landscapes can be applied to these machine learning landscapes to gain new insight into the solution space involved in training and the nature of the corresponding predictions. In particular, we can define quantities analogous to molecular structure, thermodynamics, and kinetics, and relate these emergent properties to the structure of the underlying landscape. This Perspective aims to describe these analogies with examples from recent applications, and suggest avenues for new interdisciplinary research.
machine-learning  introspection  rather-interesting  fitness-landscapes  energy-landscapes  visualization  to-write-about  consider:performance-measures  algorithms  feature-construction 
15 days ago
« earlier      
academia academic-culture activism advice agent-based agility algorithms amusing ann-arbor approximation architecture archive art artificial-intelligence artificial-life bankers-should-start-avoiding-lampposts-right-about-now 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 crowdsourcing cultural-assumptions cultural-dynamics cultural-norms data-analysis data-mining deep-learning 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 genetic-programming geometry google government graph-theory graphic-design heuristics history horse-races humor image-analysis image-processing image-segmentation inference information-theory innovation intellectual-property interesting inverse-problems investment javascript kauffmania language law lawyers learning learning-by-doing learning-from-data library local machine-learning macos management marketing mathematical-recreations mathematics matrices media metaheuristics metrics michigan modeling models models-and-modes multiobjective-optimization music 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-science photography physics planning politics prediction probability-theory programming project-management 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 systems-biology technology the-mangle-in-practice theoretical-biology tiling time-series to-read to-understand to-write-about tools trading tutorial typography user-experience via:cshalizi video visualization web-design web2.0 worklife writing

Copy this bookmark: