[1605.04679] Typical Performance of Approximation Algorithms for NP-hard Problems

2 days ago

Typical performance of approximation algorithms is studied for randomized minimum vertex cover problems. A wide class of random graph ensembles characterized by an arbitrary degree distribution is discussed with some theoretical frameworks. Here three approximation algorithms are examined; the linear-programming relaxation, the loopy-belief propagation, and the leaf-removal algorithm. The former two algorithms are analyzed using the statistical-mechanical technique while the average-case analysis of the last one is studied by the generating function method. These algorithms have a threshold in the typical performance with increasing the average degree of the random graph, below which they find true optimal solutions with high probability. Our study reveals that there exist only three cases determined by the order of the typical-performance thresholds. We provide some conditions for classifying the graph ensembles and demonstrate explicitly examples for the difference in the threshold.

approximation
computational-complexity
rather-interesting
to-write-about
to-do
nudge-targets
consider:approximation
2 days ago

[1711.01129] Hamilton-Jacobi Theory and Information Geometry

2 days ago

Recently, a method to dynamically define a divergence function D for a given statistical manifold (,g,T) by means of the Hamilton-Jacobi theory associated with a suitable Lagrangian function 𝔏 on T has been proposed. Here we will review this construction and lay the basis for an inverse problem where we assume the divergence function D to be known and we look for a Lagrangian function 𝔏 for which D is a complete solution of the associated Hamilton-Jacobi theory. To apply these ideas to quantum systems, we have to replace probability distributions with probability amplitudes.

information-geometry
statistics
information-theory
to-understand
modeling
2 days ago

Directory of Mathematical Headaches

2 days ago

Let’s try to create headaches for the concepts below.

Ask yourself, “If this skill is aspirin, then what is the headache and how do I create it?”

Ask yourself, “How would a mathematician’s life be worse if they didn’t have this skill?”

Let that guide you in your design of an activity for students.

via:robertogreco
pedagogy
mathematics
nudge-targets
machine-learning-targets
Ask yourself, “If this skill is aspirin, then what is the headache and how do I create it?”

Ask yourself, “How would a mathematician’s life be worse if they didn’t have this skill?”

Let that guide you in your design of an activity for students.

2 days ago

Gauges – Web Analytics Software

2 days ago

Website Analytics you can Actually Understand

Gauges helps you focus on your most important web traffic stats — in real time.

Google-replacements
web-design
analytics
services
subscriptions
Gauges helps you focus on your most important web traffic stats — in real time.

2 days ago

Vulpa™ - Webfont & Desktop font « MyFonts

10 days ago

Vulpa is a charming serif family in regular, italic and bold, informed by the proportions of a personal favorite, Plantin. The quirky foxtail terminals (inspired in part by my script font, Gelato Script) can be seen across all three styles. These little details make the typeface very expressive at display sizes, but practically disappear at text sizes, making for a very versatile face. More…

typeface
want
10 days ago

Mathematics must be creative, else it ain’t mathematics

10 days ago

When people ask, often cynically, what creativity looks like, it is surely this: the ability to join seemingly disparate ideas to form new expressions of thought and emotion.

By this definition, mathematics must be considered a creative pursuit. The mathematical world is governed by patterns and symmetries, some of them known and most of them awaiting our discovery.

There are no topics in mathematics; only artificial barriers that we have erected to help organise the curriculum. At school, we study topics in discrete chunks and come to understand them as separate islands of knowledge. Yet the most powerful and interesting mathematics arises when we cut through these barriers.

creativity
mathematics
mathematical-recreations
to-write-about
essay
system-of-professions
By this definition, mathematics must be considered a creative pursuit. The mathematical world is governed by patterns and symmetries, some of them known and most of them awaiting our discovery.

There are no topics in mathematics; only artificial barriers that we have erected to help organise the curriculum. At school, we study topics in discrete chunks and come to understand them as separate islands of knowledge. Yet the most powerful and interesting mathematics arises when we cut through these barriers.

10 days ago

[1711.08412] Word Embeddings Quantify 100 Years of Gender and Ethnic Stereotypes

10 days ago

Word embeddings use vectors to represent words such that the geometry between vectors captures semantic relationship between the words. In this paper, we develop a framework to demonstrate how the temporal dynamics of the embedding can be leveraged to quantify changes in stereotypes and attitudes toward women and ethnic minorities in the 20th and 21st centuries in the United States. We integrate word embeddings trained on 100 years of text data with the U.S. Census to show that changes in the embedding track closely with demographic and occupation shifts over time. The embedding captures global social shifts -- e.g., the women's movement in the 1960s and Asian immigration into the U.S -- and also illuminates how specific adjectives and occupations became more closely associated with certain populations over time. Our framework for temporal analysis of word embedding opens up a powerful new intersection between machine learning and quantitative social science.

digital-humanities
text-processing
big-data
rather-interesting
history
to-write-about
sociology
10 days ago

[1704.00640] Symmetric motifs in random geometric graphs

10 days ago

We study symmetric motifs in random geometric graphs. Symmetric motifs are subsets of nodes which have the same adjacencies. These subgraphs are particularly prevalent in random geometric graphs and appear in the Laplacian and adjacency spectrum as sharp, distinct peaks, a feature often found in real-world networks. We look at the probabilities of their appearance and compare these across parameter space and dimension. We then use the Chen-Stein method to derive the minimum separation distance in random geometric graphs which we apply to study symmetric motifs in both the intensive and thermodynamic limits. In the thermodynamic limit the probability that the closest nodes are symmetric approaches one, whilst in the intensive limit this probability depends upon the dimension.

graph-theory
network-theory
rather-interesting
probability-theory
symmetry
to-write-about
to-simulate
10 days ago

Information Theory of Complex Networks

10 days ago

Complex networks are characterized by highly heterogeneous distributions of links, often pervading the presence of key properties such as robustness under node removal. Several correlation measures have been defined in order to characterize the structure of these nets. Here we show that mutual information, noise and joint entropies can be properly defined on a static graph. These measures are computed for a number of real networks and analytically estimated for some simple standard models. It is shown that real networks are clustered in a well-defined domain of the entropy- noise space. By using simulated annealing optimization, it is shown that optimally heterogeneous nets actually cluster around the same narrow domain, suggesting that strong constraints actually operate on the possible universe of complex networks. The evolutionary implications are discussed

via:twitter
complexology
network-theory
information-theory
to-read
hey-I-know-this-guy
10 days ago

[1708.04215] A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem

10 days ago

We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of that relaxation.

Our techniques build upon the constant-factor approximation algorithm for the special case of node-weighted metrics. Specifically, we give a generic reduction to structured instances that resemble but are more general than those arising from node-weighted metrics. For those instances, we then solve Local-Connectivity ATSP, a problem known to be equivalent (in terms of constant-factor approximation) to the asymmetric traveling salesman problem.

algorithms
via:vielmetti
operations-research
approximation
optimization
computational-complexity
to-write-about
nudge-targets
consider:looking-to-see
Our techniques build upon the constant-factor approximation algorithm for the special case of node-weighted metrics. Specifically, we give a generic reduction to structured instances that resemble but are more general than those arising from node-weighted metrics. For those instances, we then solve Local-Connectivity ATSP, a problem known to be equivalent (in terms of constant-factor approximation) to the asymmetric traveling salesman problem.

10 days ago

[1711.07387] How morphological development can guide evolution

10 days ago

Organisms result from multiple adaptive processes occurring and interacting at different time scales. One such interaction is that between development and evolution. In modeling studies, it has been shown that development sweeps over a series of traits in a single agent, and sometimes exposes promising static traits. Subsequent evolution can then canalize these rare traits. Thus, development can, under the right conditions, increase evolvability. Here, we report on a previously unknown phenomenon when embodied agents are allowed to develop and evolve: Evolution discovers body plans which are robust to control changes, these body plans become genetically assimilated, yet controllers for these agents are not assimilated. This allows evolution to continue climbing fitness gradients by tinkering with the developmental programs for controllers within these permissive body plans. This exposes a previously unknown detail about the Baldwin effect: instead of all useful traits becoming genetically assimilated, only phenotypic traits that render the agent robust to changes in other traits become assimilated. We refer to this phenomenon as differential canalization. This finding also has important implications for the evolutionary design of artificial and embodied agents such as robots: robots that are robust to internal changes in their controllers may also be robust to external changes in their environment, such as transferal from simulation to reality, or deployment in novel environments.

artificial-life
evolved-devo
developmental-biology
representation
rather-interesting
genetic-programming
hey-I-know-this-guy
10 days ago

acrolinx/clj-queue-by: A queue which schedules fairly by key

10 days ago

We developed this library with a program in mind that requires a central in-memory queue. The queue must allow the program to serve active users in a timely manner while still ensuring that users with massive traffic get their job done eventually.

queueing-theory
software
library
Clojure
to-learn
to-understand
distributed-processing
10 days ago

OpenAPI Specification | Swagger

10 days ago

The OpenAPI Specification (OAS) defines a standard, language-agnostic interface to RESTful APIs which allows both humans and computers to discover and understand the capabilities of the service without access to source code, documentation, or through network traffic inspection. When properly defined, a consumer can understand and interact with the remote service with a minimal amount of implementation logic.

OpenAPI
software-development-is-not-programming
standards
API
to-learn
to-use
10 days ago

Game & Puzzle Design

14 days ago

Game & Puzzle Design is a peer-reviewed print journal publishing high quality work on all aspects of game and puzzle design. The journal aims to bring together designers and researchers from a variety of backgrounds, to foster a deeper understanding of games and facilitate the creation of new high quality games and puzzles. We are particularly interested in the intersection between traditional and digital game design, and the points at which these disciplines converge and diverge.

Submissions may pertain to any type of game or puzzle – abstract, physical, printed, digital, etc. – but should focus on underlying mechanics or gameplay rather than visual design. The emphasis will be on traditional games and puzzles, although submissions on digital games (other than major AAA video games) are also welcome, especially where links are drawn between traditional and digital design approaches.

games
mathematical-recreations
journal
to-read
not-open
to-write-about
Submissions may pertain to any type of game or puzzle – abstract, physical, printed, digital, etc. – but should focus on underlying mechanics or gameplay rather than visual design. The emphasis will be on traditional games and puzzles, although submissions on digital games (other than major AAA video games) are also welcome, especially where links are drawn between traditional and digital design approaches.

14 days ago

[1710.03248] Synthesizing Bijective Lenses

16 days ago

Bidirectional transformations between different data representations occur frequently in modern software systems. They appear as serializers and deserializers, as database views and view updaters, and more. Manually building bidirectional transformations---by writing two separate functions that are intended to be inverses---is tedious and error prone. A better approach is to use a domain-specific language in which both directions can be written as a single expression. However, these domain-specific languages can be difficult to program in, requiring programmers to manage fiddly details while working in a complex type system.

To solve this, we present Optician, a tool for type-directed synthesis of bijective string transformers. The inputs to Optician are two ordinary regular expressions representing two data formats and a few concrete examples for disambiguation. The output is a well-typed program in Boomerang (a bidirectional language based on the theory of lenses). The main technical challenge involves navigating the vast program search space efficiently enough. Unlike most prior work on type-directed synthesis, our system operates in the context of a language with a rich equivalence relation on types (the theory of regular expressions). We synthesize terms of a equivalent language and convert those generated terms into our lens language. We prove the correctness of our synthesis algorithm. We also demonstrate empirically that our new language changes the synthesis problem from one that admits intractable solutions to one that admits highly efficient solutions. We evaluate Optician on a benchmark suite of 39 examples including both microbenchmarks and realistic examples derived from other data management systems including Flash Fill, a tool for synthesizing string transformations in spreadsheets, and Augeas, a tool for bidirectional processing of Linux system configuration files.

programming-language
to-understand
data-structures
translation
strings
to-write-about
nudge-targets?
To solve this, we present Optician, a tool for type-directed synthesis of bijective string transformers. The inputs to Optician are two ordinary regular expressions representing two data formats and a few concrete examples for disambiguation. The output is a well-typed program in Boomerang (a bidirectional language based on the theory of lenses). The main technical challenge involves navigating the vast program search space efficiently enough. Unlike most prior work on type-directed synthesis, our system operates in the context of a language with a rich equivalence relation on types (the theory of regular expressions). We synthesize terms of a equivalent language and convert those generated terms into our lens language. We prove the correctness of our synthesis algorithm. We also demonstrate empirically that our new language changes the synthesis problem from one that admits intractable solutions to one that admits highly efficient solutions. We evaluate Optician on a benchmark suite of 39 examples including both microbenchmarks and realistic examples derived from other data management systems including Flash Fill, a tool for synthesizing string transformations in spreadsheets, and Augeas, a tool for bidirectional processing of Linux system configuration files.

16 days ago

[1710.03370] iVQA: Inverse Visual Question Answering

16 days ago

In recent years, visual question answering (VQA) has become topical as a long-term goal to drive computer vision and multi-disciplinary AI research. The premise of VQA's significance, is that both the image and textual question need to be well understood and mutually grounded in order to infer the correct answer. However, current VQA models perhaps `understand' less than initially hoped, and instead master the easier task of exploiting cues given away in the question and biases in the answer distribution.

In this paper we propose the inverse problem of VQA (iVQA), and explore its suitability as a benchmark for visuo-linguistic understanding. The iVQA task is to generate a question that corresponds to a given image and answer pair. Since the answers are less informative than the questions, and the questions have less learnable bias, an iVQA model needs to better understand the image to be successful. We pose question generation as a multi-modal dynamic inference process and propose an iVQA model that can gradually adjust its focus of attention guided by both a partially generated question and the answer. For evaluation, apart from existing linguistic metrics, we propose a new ranking metric. This metric compares the ground truth question's rank among a list of distractors, which allows the drawbacks of different algorithms and sources of error to be studied. Experimental results show that our model can generate diverse, grammatically correct and content correlated questions that match the given answer.

artificial-intelligence
image-analysis
rather-interesting
jeopardy-questions
inverse-problems
natural-language-processing
to-write-about
nudge-targets
benchmarks
In this paper we propose the inverse problem of VQA (iVQA), and explore its suitability as a benchmark for visuo-linguistic understanding. The iVQA task is to generate a question that corresponds to a given image and answer pair. Since the answers are less informative than the questions, and the questions have less learnable bias, an iVQA model needs to better understand the image to be successful. We pose question generation as a multi-modal dynamic inference process and propose an iVQA model that can gradually adjust its focus of attention guided by both a partially generated question and the answer. For evaluation, apart from existing linguistic metrics, we propose a new ranking metric. This metric compares the ground truth question's rank among a list of distractors, which allows the drawbacks of different algorithms and sources of error to be studied. Experimental results show that our model can generate diverse, grammatically correct and content correlated questions that match the given answer.

16 days ago

[1703.07856] Testing for the Equality of two Distributions on High Dimensional Object Spaces

16 days ago

Energy statistics are estimators of the energy distance that depend on the distances between observations. The idea behind energy statistics is to consider a statistical potential energy that would parallel Newton's gravitational potential energy. This statistical potential energy is zero if and only if a certain null hypothesis relating two distributions holds true. In Szekely and Rizzo(2004), a nonparametric test for equality of two multivariate distributions was given, based on the Euclidean distance between observations. This test was shown to be effective for high dimensional multivariate data, and was implemented by an appropriate distribution free permutation test. As an extension of Szekely and Rizzo (2013), here we consider the energy distance between to independent random objects X and Y on the object space M, that admits an embedding into an Euclidean space. In the case of a Kendall shape space, we can use its VW-embedding into an Euclidean space of matrices and define the extrinsic distance between two shapes as their VW associated distance. The corresponding energy distance between two distributions of Kendall shapes of k-ads will be called VW-energy distance We test our methodology on, to compare the distributions of Kendall shape of the contour of the midsagittal section of the Corpus Callossum in normal vs ADHD diagnosed individuals. Here we use the VW distance between the shapes of two children CC midsections. Using the CC data coming originally from this http URL 1000.projects.nitrc.org/indi/adhd200/ it appears that the two Kendall shape distributions are not significantly different.

classification
feature-construction
rather-interesting
computer-vision
representation
algorithms
nudge-targets
consider:rediscovery
consider:looking-to-see
16 days ago

[1710.04562] Universal Scaling in Complex Substitutive Systems

16 days ago

Diffusion processes are central to human interactions. Despite extensive studies that span multiple disciplines, our knowledge is limited to spreading processes in non-substitutive systems. Yet, a considerable number of ideas, products and behaviors spread by substitution-to adopt a new one, agents must give up an existing one. Here, we find that, ranging from mobile handsets to automobiles to smart phone apps, early growth patterns in substitutive systems follow a power law with non-integer exponents, in sharp contrast to the exponential growth customary in spreading phenomena. Tracing 3.6 million individuals substituting for mobile handsets for over a decade, we uncover three generic ingredients governing substitutive processes, allowing us to develop a minimal substitution model, which not only predict analytically the observed growth patterns, but also collapse growth trajectories of constituents from rather diverse systems into a single universal curve. These results demonstrate that the dynamics of complex substitutive systems are governed by robust self-organizing principles that go beyond the particulars of individual systems, which implies that these results could guide the understanding and prediction of all spreading phenomena driven by substitutions, from electric cars to scientific paradigms, from renewable energy to new healthy habits.

social-dynamics
consumerism
economics
rather-interesting
scaling
power-laws
to-read
to-write-about
consider:simulation
16 days ago

[1710.03453] The Sparse Multivariate Method of Simulated Quantiles

16 days ago

In this paper the method of simulated quantiles (MSQ) of Dominicy and Veredas (2013) and Dominick et al. (2013) is extended to a general multivariate framework (MMSQ) and to provide a sparse estimator of the scale matrix (sparse-MMSQ). The MSQ, like alternative likelihood-free procedures, is based on the minimisation of the distance between appropriate statistics evaluated on the true and synthetic data simulated from the postulated model. Those statistics are functions of the quantiles providing an effective way to deal with distributions that do not admit moments of any order like the α-Stable or the Tukey lambda distribution. The lack of a natural ordering represents the major challenge for the extension of the method to the multivariate framework. Here, we rely on the notion of projectional quantile recently introduced by Hallin etal. (2010) and Kong Mizera (2012). We establish consistency and asymptotic normality of the proposed estimator. The smoothly clipped absolute deviation (SCAD) ℓ1--penalty of Fan and Li (2001) is then introduced into the MMSQ objective function in order to achieve sparse estimation of the scaling matrix which is the major responsible for the curse of dimensionality problem. We extend the asymptotic theory and we show that the sparse-MMSQ estimator enjoys the oracle properties under mild regularity conditions. The method is illustrated and its effectiveness is tested using several synthetic datasets simulated from the Elliptical Stable distribution (ESD) for which alternative methods are recognised to perform poorly. The method is then applied to build a new network-based systemic risk measurement framework. The proposed methodology to build the network relies on a new systemic risk measure and on a parametric test of statistical dominance.

statistics
reinventing-the-wheel
how-is-this-not-constrained-symbolic-regression?
algorithms
models-and-modes
to-understand
inference
16 days ago

[1708.08691] Extremal solutions to some art gallery and terminal-pairability problems

26 days ago

The chosen tool of this thesis is an extremal type approach. The lesson drawn by the theorems proved in the thesis is that surprisingly small compromise is necessary on the efficacy of the solutions to make the approach work. The problems studied have several connections to other subjects and practical applications.

The first part of the thesis is concerned with orthogonal art galleries. A sharp extremal bound is proved on partitioning orthogonal polygons into at most 8-vertex polygons using established techniques in the field of art gallery problems. This fills in the gap between already known results for partitioning into at most 6- and 10-vertex orthogonal polygons.

Next, these techniques are further developed to prove a new type of extremal art gallery result. The novelty provided by this approach is that it establishes a connection between mobile and stationary guards. This theorem has strong computational consequences, in fact, it provides the basis for an 83-approximation algorithm for guarding orthogonal polygons with rectangular vision.

In the second part, the graph theoretical concept of terminal-pairability is studied in complete and complete grid graphs. Once again, the extremal approach is conductive to discovering efficient methods to solve the problem.

In the case of a complete base graph, the new demonstrated lower bound on the maximum degree of realizable demand graphs is 4 times higher than previous best results. The techniques developed are then used to solve the classical extremal edge number problem for the terminal-pairability problem in complete base graphs.

The complete grid base graph lies on the other end of the spectrum in terms density amongst path-pairable graphs. It is shown that complete grid graphs are relatively efficient in routing edge-disjoint paths.

computational-geometry
combinatorics
plane-geometry
extreme-values
rather-interesting
to-write-about
nudge-targets
consider:approximation
consider:looking-to-see
The first part of the thesis is concerned with orthogonal art galleries. A sharp extremal bound is proved on partitioning orthogonal polygons into at most 8-vertex polygons using established techniques in the field of art gallery problems. This fills in the gap between already known results for partitioning into at most 6- and 10-vertex orthogonal polygons.

Next, these techniques are further developed to prove a new type of extremal art gallery result. The novelty provided by this approach is that it establishes a connection between mobile and stationary guards. This theorem has strong computational consequences, in fact, it provides the basis for an 83-approximation algorithm for guarding orthogonal polygons with rectangular vision.

In the second part, the graph theoretical concept of terminal-pairability is studied in complete and complete grid graphs. Once again, the extremal approach is conductive to discovering efficient methods to solve the problem.

In the case of a complete base graph, the new demonstrated lower bound on the maximum degree of realizable demand graphs is 4 times higher than previous best results. The techniques developed are then used to solve the classical extremal edge number problem for the terminal-pairability problem in complete base graphs.

The complete grid base graph lies on the other end of the spectrum in terms density amongst path-pairable graphs. It is shown that complete grid graphs are relatively efficient in routing edge-disjoint paths.

26 days ago

[1710.03395] Efficient Dynamic Dictionary Matching with DAWGs and AC-automata

26 days ago

The dictionary matching is a task to find all occurrences of pattern strings in a set D (called a dictionary) on a text string T. The Aho-Corasick-automaton (AC-automaton) is a data structure which enables us to solve the dictionary matching problem in O(dlogσ) preprocessing time and O(nlogσ+occ) matching time, where d is the total length of the patterns in D, n is the length of the text, σ is the alphabet size, and occ is the total number of occurrences of all the patterns in the text. The dynamic dictionary matching is a variant where patterns may dynamically be inserted into and deleted from D. This problem is called semi-dynamic dictionary matching if only insertions are allowed. In this paper, we propose two efficient algorithms. For a pattern of length m, our first algorithm supports insertions in O(mlogσ+logd/loglogd) time and pattern matching in O(nlogσ+occ) time for the semi-dynamic setting and supports both insertions and deletions in O(σm+logd/loglogd) time and pattern matching in O(n(logd/loglogd+logσ)+occ(logd/loglogd)) time for the dynamic setting by some modifications. This algorithm is based on the directed acyclic word graph. Our second algorithm, which is based on the AC-automaton, supports insertions in O(mlogσ+uf+uo) time for the semi-dynamic setting and supports both insertions and deletions in O(σm+uf+uo) time for the dynamic setting, where uf and uo respectively denote the numbers of states of which the failure function and the output function need to be updated. This algorithm performs pattern matching in O(nlogσ+occ) time for both settings. Our algorithm achieves optimal update time for AC-automaton based methods, since any algorithm which explicitly maintains the AC-automaton requires Ω(uf+uo) update time.

algorithms
strings
rather-interesting
formal-languages
representation
rewriting-systems
to-write-about
consider:rediscovery
nudge-targets
26 days ago

[1706.01557] The minimum Manhattan distance and minimum jump of permutations

26 days ago

Let π be a permutation of {1,2,…,n}. If we identify a permutation with its graph, namely the set of n dots at positions (i,π(i)), it is natural to consider the minimum L1 (Manhattan) distance, d(π), between any pair of dots. The paper computes the expected value of d(π) when n→∞ and π is chosen uniformly, and settles a conjecture of Bevan, Homberger and Tenner (motivated by permutation patterns), showing that when d is fixed and n→∞, the probability that d(π)≥d+2 tends to e−d2−d.

The minimum jump 𝗆𝗃(π) of π, defined by 𝗆𝗃(π)=min1≤i≤n−1|π(i+1)−π(i)|, is another natural measure in this context. The paper computes the expected value of 𝗆𝗃(π), and the asymptotic probability that 𝗆𝗃(π)≥d+1 for any constant d.

combinatorics
probability-theory
permutations
rather-interesting
to-write-about
to-simulate
nudge-targets
consider:looking-to-see
The minimum jump 𝗆𝗃(π) of π, defined by 𝗆𝗃(π)=min1≤i≤n−1|π(i+1)−π(i)|, is another natural measure in this context. The paper computes the expected value of 𝗆𝗃(π), and the asymptotic probability that 𝗆𝗃(π)≥d+1 for any constant d.

26 days ago

[1711.01012] Genetic Policy Optimization

26 days ago

Genetic algorithms have been widely used in many practical optimization problems. Inspired by natural selection, operators, including mutation, crossover and selection, provide effective heuristics for search and black-box optimization. However, they have not been shown useful for deep reinforcement learning, possibly due to the catastrophic consequence of parameter crossovers of neural networks. Here, we present Genetic Policy Optimization (GPO), a new genetic algorithm for sample-efficient deep policy optimization. GPO uses imitation learning for policy crossover in the state space and applies policy gradient methods for mutation. Our experiments on Mujoco tasks show that GPO as a genetic algorithm is able to provide superior performance over the state-of-the-art policy gradient methods and achieves comparable or higher sample efficiency.

machine-learning
genetic-algorithm
representation
reinvented-wheel
to-understand
to-write-about
evolutionary-algorithms
26 days ago

[1610.08123] Socratic Learning: Augmenting Generative Models to Incorporate Latent Subsets in Training Data

26 days ago

A challenge in training discriminative models like neural networks is obtaining enough labeled training data. Recent approaches use generative models to combine weak supervision sources, like user-defined heuristics or knowledge bases, to label training data. Prior work has explored learning accuracies for these sources even without ground truth labels, but they assume that a single accuracy parameter is sufficient to model the behavior of these sources over the entire training set. In particular, they fail to model latent subsets in the training data in which the supervision sources perform differently than on average. We present Socratic learning, a paradigm that uses feedback from a corresponding discriminative model to automatically identify these subsets and augments the structure of the generative model accordingly. Experimentally, we show that without any ground truth labels, the augmented generative model reduces error by up to 56.06% for a relation extraction task compared to a state-of-the-art weak supervision technique that utilizes generative models.

machine-learning
algorithms
performance-space-analysis
coevolution
to-write-about
system-of-professions
reinvented-wheels
26 days ago

[1710.06993] Improved Search in Hamming Space using Deep Multi-Index Hashing

26 days ago

Similarity-preserving hashing is a widely-used method for nearest neighbour search in large-scale image retrieval tasks. There has been considerable research on generating efficient image representation via the deep-network-based hashing methods. However, the issue of efficient searching in the deep representation space remains largely unsolved. To this end, we propose a simple yet efficient deep-network-based multi-index hashing method for simultaneously learning the powerful image representation and the efficient searching. To achieve these two goals, we introduce the multi-index hashing (MIH) mechanism into the proposed deep architecture, which divides the binary codes into multiple substrings. Due to the non-uniformly distributed codes will result in inefficiency searching, we add the two balanced constraints at feature-level and instance-level, respectively. Extensive evaluations on several benchmark image retrieval datasets show that the learned balanced binary codes bring dramatic speedups and achieve comparable performance over the existing baselines.

metrics
image-processing
deep-learning
performance-space-analysis
feature-construction
machine-learning
rather-interesting
similarity-measures
to-write-about
26 days ago

[1610.06934] The K Shortest Paths Problem with Application to Routing

26 days ago

Due to the computational complexity of finding almost shortest simple paths, we propose that identifying a larger collection of (nonbacktracking) paths is more efficient than finding almost shortest simple paths on positively weighted real-world networks. First, we present an easy to implement O(mlogm+kL) solution for finding all (nonbacktracking) paths with bounded length D between two arbitrary nodes on a positively weighted graph, where L is an upperbound for the number of nodes in any of the k outputted paths. Subsequently, we illustrate that for undirected Chung-Lu random graphs, the ratio between the number of nonbacktracking and simple paths asymptotically approaches 1 with high probability for a wide range of parameters. We then consider an application to the almost shortest paths algorithm to measure path diversity for internet routing in a snapshot of the Autonomous System graph subject to an edge deletion process.

planning
data-structures
algorithms
rather-interesting
operations-research
graph-theory
to-write-about
nudge-targets
consider:looking-to-see
26 days ago

[1711.03172] Curve Reconstruction via the Global Statistics of Natural Curves

26 days ago

Reconstructing the missing parts of a curve has been the subject of much computational research, with applications in image inpainting, object synthesis, etc. Different approaches for solving that problem are typically based on processes that seek visually pleasing or perceptually plausible completions. In this work we focus on reconstructing the underlying physically likely shape by utilizing the global statistics of natural curves. More specifically, we develop a reconstruction model that seeks the mean physical curve for a given inducer configuration. This simple model is both straightforward to compute and it is receptive to diverse additional information, but it requires enough samples for all curve configurations, a practical requirement that limits its effective utilization. To address this practical issue we explore and exploit statistical geometrical properties of natural curves, and in particular, we show that in many cases the mean curve is scale invariant and often times it is extensible. This, in turn, allows to boost the number of examples and thus the robustness of the statistics and its applicability. The reconstruction results are not only more physically plausible but they also lead to important insights on the reconstruction problem, including an elegant explanation why certain inducer configurations are more likely to yield consistent perceptual completions than others.

inference
computer-vision
rather-interesting
algorithms
nudge-targets
consider:looking-to-see
consider:representation
performance-measure
to-write-about
26 days ago

[1704.07422] Iterative Methods for Photoacoustic Tomography in Attenuating Acoustic Media

26 days ago

The development of efficient and accurate reconstruction methods is an important aspect of tomographic imaging. In this article, we address this issue for photoacoustic tomography. To this aim, we use models for acoustic wave propagation accounting for frequency dependent attenuation according to a wide class of attenuation laws that may include memory. We formulate the inverse problem of photoacoustic tomography in attenuating medium as an ill-posed operator equation in a Hilbert space framework that is tackled by iterative regularization methods. Our approach comes with a clear convergence analysis. For that purpose we derive explicit expressions for the adjoint problem that can efficiently be implemented. In contrast to time reversal, the employed adjoint wave equation is again damping and, thus has a stable solution. This stability property can be clearly seen in our numerical results. Moreover, the presented numerical results clearly demonstrate the Efficiency and accuracy of the derived iterative reconstruction algorithms in various situations including the limited view case.

tomography
numerical-methods
inverse-problems
rather-interesting
signal-processing
algorithms
nudge-targets
consider:benchmarking
consider:looking-to-see
26 days ago

[1705.01887] Streaming for Aibohphobes: Longest Palindrome with Mismatches

26 days ago

A palindrome is a string that reads the same as its reverse, such as "aibohphobia" (fear of palindromes). Given an integer d>0, a d-near-palindrome is a string of Hamming distance at most d from its reverse. We study the natural problem of identifying a longest d-near-palindrome in data streams. The problem is relevant to the analysis of DNA databases, and to the task of repairing recursive structures in documents such as XML and JSON. We present an algorithm that returns a d-near-palindrome whose length is within a multiplicative (1+ϵ)-factor of the longest d-near-palindrome. Our algorithm also returns the set of mismatched indices of the d-near-palindrome, using (dlog7nϵlog(1+ϵ)) bits of space, and (dlog6nϵlog(1+ϵ)) update time per arriving symbol. We show that Ω(dlogn) space is necessary for estimating the length of longest d-near-palindromes with high probability. We further obtain an additive-error approximation algorithm and a comparable lower bound, as well as an exact two-pass algorithm that solves the longest d-near-palindrome problem using (d2n‾√log6n) bits of space.

strings
computational-complexity
algorithms
probability-theory
inference
online-learning
rather-interesting
to-write-about
nudge-targets
consider:looking-to-see
consider:representation
26 days ago

[1611.07769] The many facets of community detection in complex networks

26 days ago

Community detection, the decomposition of a graph into essential building blocks, has been a core research topic in network science over the past years. Since a precise notion of what constitutes a community has remained evasive, community detection algorithms have often been compared on benchmark graphs with a particular form of assortative community structure and classified based on the mathematical techniques they employ. However, this comparison can be misleading because apparent similarities in their mathematical machinery can disguise different goals and reasons for why we want to employ community detection in the first place. Here we provide a focused review of these different motivations that underpin community detection. This problem-driven classification is useful in applied network science, where it is important to select an appropriate algorithm for the given purpose. Moreover, highlighting the different facets of community detection also delineates the many lines of research and points out open directions and avenues for future research.

community-detection
social-networks
philosophy-of-science
define-your-terms
review
to-write-about
26 days ago

[1702.01522] Inverse statistical problems: from the inverse Ising problem to data science

26 days ago

Inverse problems in statistical physics are motivated by the challenges of `big data' in different fields, in particular high-throughput experiments in biology. In inverse problems, the usual procedure of statistical physics needs to be reversed: Instead of calculating observables on the basis of model parameters, we seek to infer parameters of a model based on observations. In this review, we focus on the inverse Ising problem and closely related problems, namely how to infer the coupling strengths between spins given observed spin correlations, magnetisations, or other data. We review applications of the inverse Ising problem, including the reconstruction of neural connections, protein structure determination, and the inference of gene regulatory networks. For the inverse Ising problem in equilibrium, a number of controlled and uncontrolled approximate solutions have been developed in the statistical mechanics community. A particularly strong method, pseudolikelihood, stems from statistics. We also review the inverse Ising problem in the non-equilibrium case, where the model parameters must be reconstructed based on non-equilibrium statistics.

data-science
statistics
inverse-problems
complexology
rather-interesting
inference
to-write-about
review
to-simulate
philosophy-of-science
26 days ago

[1504.08259] Edit Distance for Pushdown Automata

26 days ago

The edit distance between two words w1,w2 is the minimal number of word operations (letter insertions, deletions, and substitutions) necessary to transform w1 to w2. The edit distance generalizes to languages 1,2, where the edit distance from 1 to 2 is the minimal number k such that for every word from 1 there exists a word in 2 with edit distance at most k. We study the edit distance computation problem between pushdown automata and their subclasses. The problem of computing edit distance to a pushdown automaton is undecidable, and in practice, the interesting question is to compute the edit distance from a pushdown automaton (the implementation, a standard model for programs with recursion) to a regular language (the specification). In this work, we present a complete picture of decidability and complexity for the following problems: (1)~deciding whether, for a given threshold k, the edit distance from a pushdown automaton to a finite automaton is at most k, and (2)~deciding whether the edit distance from a pushdown automaton to a finite automaton is finite.

formal-languages
edit-distance
metrics
define-your-terms
rather-interesting
open-questions
discrete-mathematics
26 days ago

[1709.07485] The Covering Path Problem on a Grid

26 days ago

This paper introduces the covering path problem on a grid (CPPG) which finds the cost-minimizing path connecting a subset of points in a grid such that each point is within a predetermined distance of a point from the chosen subset. We leverage the geometric properties of the grid graph which captures the road network structure in many transportation problems, including our motivating setting of school bus routing. As defined in this paper, the CPPG is a bi-objective optimization problem comprised of one cost term related to path length and one cost term related to stop count. We develop a trade-off constraint which quantifies the trade-off between path length and stop count and provides a lower bound for the bi-objective optimization problem. We introduce simple construction techniques to provide feasible paths that match the lower bound within a constant factor. Importantly, this solution approach uses transformations of the general CPPG to either a discrete CPPG or continuous CPPG based on the value of the coverage radius. For both the discrete and continuous versions, we provide fast constant-factor approximations, thus solving the general CPPG.

operations-research
planning
multiobjective-optimization
rather-interesting
to-write-about
26 days ago

In, against and beyond the Co-operative University | Richard Hall's Space

29 days ago

In part my questioning is situated against my own weltschmerz, in particular in the face of ongoing, secular capitalist crisis with its attendant punishing and disciplinary austerity. However, my questioning extends the nature of this socio-economic crisis, which is destroying the lives/futures of millions of people, into the terrain of socio-environmental crisis. I also wonder why we are building a model in this way that is deliberately connected to a hegemonic system of oppression, and which is rooted in contradictions and tensions around the ongoing nature of work and the availability of employment that is increasingly predicted to be marginalised/made redundant by technology in so many sectors. So in building for an unstable world that is increasingly governed by debt as a moment of social discipline, I found myself asking why are we building in this way for a capitalist world that is collapsing? Is building an alternative form of sociability impossible? I found myself questioning how to enact Rosa Luxemburg’s idea (on socialism or barbarism) that ’to push ahead to the victory of socialism we need a strong, activist, educated proletariat, and masses whose power lies in intellectual culture as well as numbers.’

academia
corporatism
activism
cooperation
institutional-design
life-o'-the-mind
to-read
29 days ago

CEOs Don’t Steer

29 days ago

This is why CEOs are different from other kinds of leaders. Leaders in other societal roles are typically not the stewards of any source of promethean energy. Instead, they are involved with directing and routing second-order effects that drain it. So they can afford to steer and be clever about it. They are zero-sum carve-the-pie leaders (which is important too, just not the point of this post).

But CEOs don’t steer.

What is good for countries, militaries, and art movements is not good for companies (and conversely, when the Trumps, Modis, and Xi Jinpengs bring CEO-like orientation-locking tendencies to inclusive governance jobs that require non-trivial steering, the results are usually not pretty).

business-culture
leadership
corporatism
worklife
a-reasonable-assessment
myths-of-the-managers
But CEOs don’t steer.

What is good for countries, militaries, and art movements is not good for companies (and conversely, when the Trumps, Modis, and Xi Jinpengs bring CEO-like orientation-locking tendencies to inclusive governance jobs that require non-trivial steering, the results are usually not pretty).

29 days ago

Why is it more difficult to imagine the end of universities than the end of capitalism, or: is the crisis of the university in fact a crisis of imagination? – Jana Bacevic

4 weeks ago

I’m particularly interested in questions such as:

Qualifications and credentials: can we imagine a society where universities do not hold a monopoly on credentials? What would this look like?

Knowledge work: can we conceive of knowledge production (teaching and research) not only ‘outside of’, but without the university? What would this look like?

Financing: what other modes of funding for knowledge production are conceivable? Is there a form of public funding that does not involve universities (e.g., through an academic workers’ cooperative – Mondragon University in Spain is one example – or guild)? What would be the implications of this, and how it would be regulated?

Built environment/space: can we think of knowledge not confined to specific buildings or an institution? What would this look like – how would it be organised? What would be the consequences for learning, teaching and research?

academic-culture
disintermediation-in-action
sociology
neoliberalism-sidestepped
life-o'-the-mind
Qualifications and credentials: can we imagine a society where universities do not hold a monopoly on credentials? What would this look like?

Knowledge work: can we conceive of knowledge production (teaching and research) not only ‘outside of’, but without the university? What would this look like?

Financing: what other modes of funding for knowledge production are conceivable? Is there a form of public funding that does not involve universities (e.g., through an academic workers’ cooperative – Mondragon University in Spain is one example – or guild)? What would be the implications of this, and how it would be regulated?

Built environment/space: can we think of knowledge not confined to specific buildings or an institution? What would this look like – how would it be organised? What would be the consequences for learning, teaching and research?

4 weeks ago

plaidml/plaidml: PlaidML is a framework for making deep learning work everywhere.

4 weeks ago

PlaidML is a multi-language acceleration framework that:

Enables practitioners to deploy high-performance neural nets on any device

Allows hardware developers to quickly integrate with high-level frameworks

Allows framework developers to easily add support for many kinds of hardware

For background and early benchmarks see our blog post announcing the release. PlaidML is under active development and should be thought of as early alpha quality.

machine-learning
library
software-development
to-learn
to-write-about
Enables practitioners to deploy high-performance neural nets on any device

Allows hardware developers to quickly integrate with high-level frameworks

Allows framework developers to easily add support for many kinds of hardware

For background and early benchmarks see our blog post announcing the release. PlaidML is under active development and should be thought of as early alpha quality.

4 weeks ago

[1710.05183] Inferring Mesoscale Models of Neural Computation

4 weeks ago

Recent years have seen dramatic progress in the development of techniques for measuring the activity and connectivity of large populations of neurons in the brain. However, as these techniques grow ever more powerful---allowing us to even contemplate measuring every neuron in entire brain---a new problem arises: how do we make sense of the mountains of data that these techniques produce? Here, we argue that the time is ripe for building an intermediate or "mesoscale" computational theory that can bridge between single-cell (microscale) accounts of neural function and behavioral (macroscale) accounts of animal cognition and environmental complexity. Just as digital accounts of computation in conventional computers abstract away the non-essential dynamics of the analog circuits that implementing gates and registers, so too a computational account of animal cognition can afford to abstract from the non-essential dynamics of neurons. We argue that the geometry of neural circuits is essential in explaining the computational limitations and technological innovations inherent in biological information processing. We propose a blueprint for how to employ tools from modern machine learning to automatically infer a satisfying mesoscale account of neural computation that combines functional and structural data, with an emphasis on learning and exploiting regularity and repeating motifs in neuronal circuits. Rather than suggest a specific theory, we present a new class of scientific instruments that can enable neuroscientists to design, propose, implement and test mesoscale theories of neural computation.

dynamical-systems
machine-learning
deep-learning
representation
temporal-models
rather-interesting
inference
to-write-about
4 weeks ago

[1512.00507] Beyond Aztec Castles: Toric Cascades in the $dP_3$ Quiver

4 weeks ago

Given one of an infinite class of supersymmetric quiver gauge theories, string theorists can associate a corresponding toric variety (which is a Calabi-Yau 3-fold) as well as an associated combinatorial model known as a brane tiling. In combinatorial language, a brane tiling is a bipartite graph on a torus and its perfect matchings are of interest to both combinatorialists and physicists alike. A cluster algebra may also be associated to such quivers and in this paper we study the generators of this algebra, known as cluster variables, for the quiver associated to the cone over the del Pezzo surface dP3. In particular, mutation sequences involving mutations exclusively at vertices with two in-coming arrows and two out-going arrows are referred to as toric cascades in the string theory literature. Such toric cascades give rise to interesting discrete integrable systems on the level of cluster variable dynamics. We provide an explicit algebraic formula for all cluster variables which are reachable by toric cascades as well as a combinatorial interpretation involving perfect matchings of subgraphs of the dP3 brane tiling for these formulas in most cases.

tiling
domino-tiling
enumeration
combinatorics
to-write-about
to-simulate
review
rather-interesting
4 weeks ago

[1504.00303] A Generalization of Aztec Dragons

4 weeks ago

Aztec dragons are lattice regions first introduced by James Propp, which have the number of tilings given by a power of 2. This family of regions has been investigated further by a number of authors. In this paper, we consider a generalization of the Aztec dragons to two new families of 6-sided regions. By using Kuo's graphical condensation method, we prove that the tilings of the new regions are always enumerated by powers of 2 and 3.

tiling
combinatorics
enumeration
out-of-the-box
to-write-about
to-simulate
4 weeks ago

[1504.00291] On the numbers of perfect matchings of trimmed Aztec rectangles

4 weeks ago

We consider several new families of graphs obtained from Aztec rectangle and augmented Aztec rectangle graphs by trimming two opposite corners. We prove that the perfect matchings of these new graphs are enumerated by powers of 2, 3, 5, and 11. The result yields a proof of a conjectured posed by Ciucu. In addition, we reveal a hidden relation between our graphs and the hexagonal dungeons introduced by Blum.

combinatorics
Aztec-diamond
domino-tiling
enumeration
to-write-about
to-simulate
4 weeks ago

[1411.0146] Double Aztec Rectangles

4 weeks ago

We investigate the connection between lozenge tilings and domino tilings by introducing a new family of regions obtained by attaching two different Aztec rectangles. We prove a simple product formula for the generating functions of the tilings of the new regions, which involves the statistics as in the Aztec diamond theorem (Elkies, Kuperberg, Larsen, and Propp, J. Algebraic Combin. 1992). Moreover, we consider the connection between the generating function and MacMahon's q-enumeration of plane partitions fitting in a given box

combinatorics
enumeration
tiling
domino-tiling
Aztec-diamond
to-write-about
to-simulate
4 weeks ago

[1403.4493] Enumeration of tilings of quartered Aztec rectangles

4 weeks ago

We generalize a theorem of W. Jockusch and J. Propp on quartered Aztec diamonds by enumerating the tilings of quartered Aztec rectangles. We use subgraph replacement method to transform the dual graph of a quartered Aztec rectangle to the dual graph of a quartered lozenge hexagon, and then use Lindstr\"{o}m-Gessel-Viennot methodology to find the number of tilings of a quartered lozenge hexagon.

combinatorics
enumeration
Aztec-diamond
domino-tiling
to-write-about
to-simulate
4 weeks ago

[1711.02818] Enumeration of lozenge tilings of a hexagon with a shamrock missing on the symmetry axis

4 weeks ago

In their paper about a dual of MacMahon's classical theorem on plane partitions, Ciucu and Krattenthaler proved a closed form product formula for the tiling number of a hexagon with a "shamrock", a union of four adjacent triangles, removed in the center (Proc. Natl. Acad. Sci. USA 2013). Lai later presented a q-enumeration for lozenge tilings of a hexagon with a shamrock removed from the boundary (European J. Combin. 2017). It appears that the above are the only two positions of the shamrock hole that yield nice tiling enumerations. In this paper, we show that in the case of symmetric hexagons, we always have a simple product formula for the number of tilings when removing a shamrock at any position along the symmetry axis. Our result also generalizes Eisenk\"olbl's related work about lozenge tilings of a hexagon with two unit triangles missing on the symmetry axis (Electron. J. Combin. 1999).

tiling
domino-tiling
rather-interesting
combinatorics
enumeration
the-mangle-in-practice
representation
to-write-about
consider:the-convoluted-approach
4 weeks ago

notes on academic alienation and mass intellectuality | Richard Hall's Space

4 weeks ago

SEVEN. What Is To Be Done?

The generation of resistances, across an intersectional set of terrains and which acknowledge issues of privilege and powerlessness, require us to move beyond the triptych of private property, commodity exchange and division of labour, to uncover the realities of alienated labour. This is to work against the reconceptualization of academic labour by advocating solidarity inside and outside universities so that academic labour, including that of students, is recognised as having the same fundamental characteristics as other forms of labour and is therefore subject to the same crises of capitalism that are the focus of other social movements. This does not argue for the militant defence of academic labour, but sees it for what it is: wage labour subject to the alienation of the capitalist valorisation process, and to be abolished. Resistance to the processes of work intensification are all the while necessary, but the discovery of new forms of social solidarity and large scale transformation (rather than reformation) of political economy are the end goals.

Here the terrain of personal narratives grounded in alienation, which have yet to reveal their root in alienated labour, open-up the possibility that we might discuss an overcoming of academic competition and overwork. However, developing a counter-hegemonic solidarity requires that such narratives are connected to both a critique of academic labour, and a focus upon social solidarity and the social strike. This situates the exploitation of academic labour against the wider exploitation of paid and unpaid labour in the social factory. Not only must the academic labourer overcome her own competition with other academics to reduce her exploitation, but she must situate this cognitively and emotionally against the abolition of wage-labour more generally.

Of course, this must be attempted in association, so that an alternative intellectual, physical and humane existence might offer new forms of sociability that are grounded in autonomy over time. This requires praxis at the level of society, rather than within specific institutions like universities or inside specific, commodified curricula. As Marx (1844/2014, 115) argues, ‘The resolution of the theoretical contradictions are possible only through practical means, only through the practical energy of man.’

academic-culture
disintermediation-in-action
life-o'-the-mind
political-economy
cultural-dynamics
workalike
to-write-about
The generation of resistances, across an intersectional set of terrains and which acknowledge issues of privilege and powerlessness, require us to move beyond the triptych of private property, commodity exchange and division of labour, to uncover the realities of alienated labour. This is to work against the reconceptualization of academic labour by advocating solidarity inside and outside universities so that academic labour, including that of students, is recognised as having the same fundamental characteristics as other forms of labour and is therefore subject to the same crises of capitalism that are the focus of other social movements. This does not argue for the militant defence of academic labour, but sees it for what it is: wage labour subject to the alienation of the capitalist valorisation process, and to be abolished. Resistance to the processes of work intensification are all the while necessary, but the discovery of new forms of social solidarity and large scale transformation (rather than reformation) of political economy are the end goals.

Here the terrain of personal narratives grounded in alienation, which have yet to reveal their root in alienated labour, open-up the possibility that we might discuss an overcoming of academic competition and overwork. However, developing a counter-hegemonic solidarity requires that such narratives are connected to both a critique of academic labour, and a focus upon social solidarity and the social strike. This situates the exploitation of academic labour against the wider exploitation of paid and unpaid labour in the social factory. Not only must the academic labourer overcome her own competition with other academics to reduce her exploitation, but she must situate this cognitively and emotionally against the abolition of wage-labour more generally.

Of course, this must be attempted in association, so that an alternative intellectual, physical and humane existence might offer new forms of sociability that are grounded in autonomy over time. This requires praxis at the level of society, rather than within specific institutions like universities or inside specific, commodified curricula. As Marx (1844/2014, 115) argues, ‘The resolution of the theoretical contradictions are possible only through practical means, only through the practical energy of man.’

4 weeks ago

On the alienation of academic labour and the possibilities for mass intellectuality | Richard Hall's Space

4 weeks ago

Abstract: As one response to the secular crisis of capitalism, higher education is being proletarianised. Its academics and students, encumbered by precarious employment, overwhelming debt, and new levels of performance management, are shorn of any autonomy. Increasingly the labour of those academics and students is subsumed and re-engineered for value production, and is prey to the vicissitudes of the twin processes of financialisation and marketization. At the core of understanding the impact of these processes and their relationships to higher education is the alienated labour of the academic, as it defines the sociability of the University. The article examines the role of alienated labour in academic work, and relates this to feelings of hopelessness, in order to ask what might be done differently. The argument centres on the role of mass intellectuality, or socially-useful knowledge and knowing, as a potential moment for overcoming alienated labour.

academic-culture
political-economy
life-o'-the-mind
to-write-about
disintermediation-in-action
capitalism-as-a-bug
4 weeks ago

China Thinks Strategically and We Don’t | Ian Welsh

4 weeks ago

Our states are poor. Their ideology, with a few exceptions (smaller countries, all) is to let the rich get richer and have the rich spend money. So instead of NASA leading a huge space program, we have a variety of private companies like SpaceX building technology which a rich state would have created 20 years ago.

China doesn’t think this way. Chinese citizens may not be as rich as the average westerner (though there are plenty of rich Chinese as every world-class city that allows foreigners to buy its real-estate has found out, much to the sorrow of its ordinary citizens), but the state is rich, and the state and the companies it controls and influences are rich.

Most of our companies are not driven by the bottom line. Rather, they are driven by how much money they can create for those who control them. This is often not the case for Chinese companies.

political-economy
world-politics
history
economics
planning
to-watch
China doesn’t think this way. Chinese citizens may not be as rich as the average westerner (though there are plenty of rich Chinese as every world-class city that allows foreigners to buy its real-estate has found out, much to the sorrow of its ordinary citizens), but the state is rich, and the state and the companies it controls and influences are rich.

Most of our companies are not driven by the bottom line. Rather, they are driven by how much money they can create for those who control them. This is often not the case for Chinese companies.

4 weeks ago

slides and notes on academic alienation and mass intellectuality | Richard Hall's Space

4 weeks ago

I presented at the DMU Institute for Education Futures seminar yesterday. My paper is based on a forthcoming article in a special issue of TripleC on academic labour, and underpins work that I am doing towards a monograph on the alienated academic, for Palgrave Macmillan.

academic-culture
academia
disintermediation-in-action
to-read
to-write-about
4 weeks ago

[1703.07244] A Hybrid Feasibility Constraints-Guided Search to the Two-Dimensional Bin Packing Problem with Due Dates

4 weeks ago

The two-dimensional non-oriented bin packing problem with due dates packs a set of rectangular items, which may be rotated by 90 degrees, into identical rectangular bins. The bins have equal processing times. An item's lateness is the difference between its due date and the completion time of its bin. The problem packs all items without overlap as to minimize maximum lateness Lmax.

The paper proposes a tight lower bound that enhances an existing bound on Lmax for 24.07% of the benchmark instances and matches it in 30.87% cases. In addition, it models the problem using mixed integer programming (MIP), and solves small-sized instances exactly using CPLEX. It approximately solves larger-sized instances using a two-stage heuristic. The first stage constructs an initial solution via a first-fit heuristic that applies an iterative constraint programming (CP)-based neighborhood search. The second stage, which is iterative too, approximately solves a series of assignment low-level MIPs that are guided by feasibility constraints. It then enhances the solution via a high-level random local search. The approximate approach improves existing upper bounds by 27.45% on average, and obtains the optimum for 33.93% of the instances. Overall, the exact and approximate approaches identify the optimum for 39.07% cases.

The proposed approach is applicable to complex problems. It applies CP and MIP sequentially, while exploring their advantages, and hybridizes heuristic search with MIP. It embeds a new lookahead strategy that guards against infeasible search directions and constrains the search to improving directions only; thus, differs from traditional lookahead beam searches.

operations-research
planning
algorithms
hard-problems
bin-packing
computational-complexity
to-write-about
rather-interesting
nudge-targets
consider:multiobjective-approach
consider:performance-measures
The paper proposes a tight lower bound that enhances an existing bound on Lmax for 24.07% of the benchmark instances and matches it in 30.87% cases. In addition, it models the problem using mixed integer programming (MIP), and solves small-sized instances exactly using CPLEX. It approximately solves larger-sized instances using a two-stage heuristic. The first stage constructs an initial solution via a first-fit heuristic that applies an iterative constraint programming (CP)-based neighborhood search. The second stage, which is iterative too, approximately solves a series of assignment low-level MIPs that are guided by feasibility constraints. It then enhances the solution via a high-level random local search. The approximate approach improves existing upper bounds by 27.45% on average, and obtains the optimum for 33.93% of the instances. Overall, the exact and approximate approaches identify the optimum for 39.07% cases.

The proposed approach is applicable to complex problems. It applies CP and MIP sequentially, while exploring their advantages, and hybridizes heuristic search with MIP. It embeds a new lookahead strategy that guards against infeasible search directions and constrains the search to improving directions only; thus, differs from traditional lookahead beam searches.

4 weeks ago

The Big Picture: Confederate Revisionist History | Public Books

4 weeks ago

Thus the Confederate revolt was not about states’ rights, it was about protecting the institution of chattel slavery from a remote future threat. Proof of the centrality of slavery to the Southern cause lies in the Confederate Constitution itself, in which the cryptic references to persons “held to Service or Labour” were replaced with explicit references to slaves and Negroes. Article I, Section 9, Paragraph 3, for example, stated that “no bill of attainder, ex post facto law, or law denying or impairing the right of property in negro slaves shall be passed” (italics my own). Apart from these substitutions, the Confederate Constitution was identical to the original US Constitution in all respects.

history
politics
well-summarized
American-cultural-assumptions
4 weeks ago

Statistical Thinking: Classification vs. Prediction

4 weeks ago

A special problem with classifiers illustrates an important issue. Users of machine classifiers know that a highly imbalanced sample with regard to a binary outcome variable Y results in a strange classifier. For example, if the sample has 1000 diseased patients and 1,000,000 non-diseased patients, the best classifier may classify everyone as non-diseased; you will be correct 0.999 of the time. For this reason the odd practice of subsampling the controls is used in an attempt to balance the frequencies and get some variation that will lead to sensible looking classifiers (users of regression models would never exclude good data to get an answer). Then they have to, in some ill-defined way, construct the classifier to make up for biasing the sample. It is simply the case that a classifier trained to a 1/1000 prevalence situation will not be applicable to a population with a vastly different prevalence. The classifier would have to be re-trained on the new sample, and the patterns detected may change greatly. Logistic regression on the other hand elegantly handles this situation by either (1) having as predictors the variables that made the prevalence so low, or (2) recalibrating the intercept (only) for another dataset with much higher prevalence. Classifiers' extreme dependence on prevalence may be enough to make some researchers always use probability estimators instead. One could go so far as to say that classifiers should not be used at all when there is little variation in the outcome variable, and that only tendencies should be modeled.

philosophy-of-engineering
classification
statistics
machine-learning
prediction
to-write-about
engineering-criticism
4 weeks ago

radical book club: the Centralized Left | Status 451

4 weeks ago

Alinsky is kind of a curious cat. The Lefties who are most influenced by his methods often don’t talk about him much, and in many cases Lefties who do talk about him are critical. Here’s the dynamic you need to appreciate to understand this: Lefties, by and large, do not read older Lefty books the way Righties read older Righty books. A lot of Lefty training is done orally, and it’s not always hugely sourced. One Lefty friend of mine, for example, was shocked to realize years later that his college newspaper had literally been doing Maoist criticism/self-criticism sessions. They’d left any mention of Mao himself behind, of course, but they’d kept the technique.

That’s kind of what happened to Saul Alinsky. His methods are everywhere, but if you read organizing books you’ll be surprised how rarely he’s mentioned. Mainstream Lefties are actually baffled by how popular Righties think Alinsky is.

history-of-ideas
politics
organization
organizational-behavior
rather-interesting
citation
cultural-norms
That’s kind of what happened to Saul Alinsky. His methods are everywhere, but if you read organizing books you’ll be surprised how rarely he’s mentioned. Mainstream Lefties are actually baffled by how popular Righties think Alinsky is.

4 weeks ago

[1711.02724] Algorithms to Approximate Column-Sparse Packing Problems

4 weeks ago

Column-sparse packing problems arise in several contexts in both deterministic and stochastic discrete optimization. We present two unifying ideas, (non-uniform) attenuation and multiple-chance algorithms, to obtain improved approximation algorithms for some well-known families of such problems. As three main examples, we attain the integrality gap, up to lower-order terms, for known LP relaxations for k-column sparse packing integer programs (Bansal et al., Theory of Computing, 2012) and stochastic k-set packing (Bansal et al., Algorithmica, 2012), and go "half the remaining distance" to optimal for a major integrality-gap conjecture of Furedi, Kahn and Seymour on hypergraph matching (Combinatorica, 1993).

integer-programming
matrices
optimization
operations-research
set-theory
hypergraphs
to-write-about
approximation
algorithms
4 weeks ago

Reprogramming, oscillations and transdifferentiation in epigenetic landscapes | bioRxiv

4 weeks ago

Waddington's epigenetic landscape provides a phenomenological understanding of the cell differentiation pathways from the pluripotent to mature lineage-committed cell lines. In light of recent successes in the reverse programming process there has been significant interest in quantifying the underlying landscape picture through the mathematics of gene regulatory networks. We investigate the role of time delays arising from multistep chemical reactions and epigenetic rearrangement on the cell differentiation landscape for a realistic two-gene regulatory network, consisting of self-promoting and mutually inhibiting genes. Our work provides the first theoretical basis of the transdifferentiation process in the presence of delays, where one differentiated cell type can transition to another directly without passing through the undifferentiated state. Additionally, the interplay of time-delayed feedback and a time dependent chemical drive leads to long-lived oscillatory states in appropriate parameter regimes. This work emphasizes the important role played by time-delayed feedback loops in gene regulatory circuits and provides a framework for the characterization of epigenetic landscapes.

epigenetics
gene-regulatory-networks
bioinformatics
theoretical-biology
simulation
biological-engineering
rather-interesting
to-write-about
4 weeks ago

Understanding LSTM Networks -- colah's blog

4 weeks ago

Humans don’t start their thinking from scratch every second. As you read this essay, you understand each word based on your understanding of previous words. You don’t throw everything away and start thinking from scratch again. Your thoughts have persistence.

Traditional neural networks can’t do this, and it seems like a major shortcoming. For example, imagine you want to classify what kind of event is happening at every point in a movie. It’s unclear how a traditional neural network could use its reasoning about previous events in the film to inform later ones.

recurrent-neural-nets
machine-learning
architecture
dynamical-systems
explainer
Traditional neural networks can’t do this, and it seems like a major shortcoming. For example, imagine you want to classify what kind of event is happening at every point in a movie. It’s unclear how a traditional neural network could use its reasoning about previous events in the film to inform later ones.

4 weeks ago

[1202.4503] A Critical Look at Decentralized Personal Data Architectures

4 weeks ago

While the Internet was conceived as a decentralized network, the most widely used web applications today tend toward centralization. Control increasingly rests with centralized service providers who, as a consequence, have also amassed unprecedented amounts of data about the behaviors and personalities of individuals.

Developers, regulators, and consumer advocates have looked to alternative decentralized architectures as the natural response to threats posed by these centralized services. The result has been a great variety of solutions that include personal data stores (PDS), infomediaries, Vendor Relationship Management (VRM) systems, and federated and distributed social networks. And yet, for all these efforts, decentralized personal data architectures have seen little adoption.

This position paper attempts to account for these failures, challenging the accepted wisdom in the web community on the feasibility and desirability of these approaches. We start with a historical discussion of the development of various categories of decentralized personal data architectures. Then we survey the main ideas to illustrate the common themes among these efforts. We tease apart the design characteristics of these systems from the social values that they (are intended to) promote. We use this understanding to point out numerous drawbacks of the decentralization paradigm, some inherent and others incidental. We end with recommendations for designers of these systems for working towards goals that are achievable, but perhaps more limited in scope and ambition.

social-networks
software
user-experience
social-dynamics
decentralization
good-intentions
Developers, regulators, and consumer advocates have looked to alternative decentralized architectures as the natural response to threats posed by these centralized services. The result has been a great variety of solutions that include personal data stores (PDS), infomediaries, Vendor Relationship Management (VRM) systems, and federated and distributed social networks. And yet, for all these efforts, decentralized personal data architectures have seen little adoption.

This position paper attempts to account for these failures, challenging the accepted wisdom in the web community on the feasibility and desirability of these approaches. We start with a historical discussion of the development of various categories of decentralized personal data architectures. Then we survey the main ideas to illustrate the common themes among these efforts. We tease apart the design characteristics of these systems from the social values that they (are intended to) promote. We use this understanding to point out numerous drawbacks of the decentralization paradigm, some inherent and others incidental. We end with recommendations for designers of these systems for working towards goals that are achievable, but perhaps more limited in scope and ambition.

4 weeks ago

[1707.05589] On the State of the Art of Evaluation in Neural Language Models

4 weeks ago

Ongoing innovations in recurrent neural network architectures have provided a steady influx of apparently state-of-the-art results on language modelling benchmarks. However, these have been evaluated using differing code bases and limited computational resources, which represent uncontrolled sources of experimental variation. We reevaluate several popular architectures and regularisation methods with large-scale automatic black-box hyperparameter tuning and arrive at the somewhat surprising conclusion that standard LSTM architectures, when properly regularised, outperform more recent models. We establish a new state of the art on the Penn Treebank and Wikitext-2 corpora, as well as strong baselines on the Hutter Prize dataset.

natural-language-processing
representation
machine-learning
deep-learning
to-write-about
4 weeks ago

CTK Insights » Blog Archive A Discovery of Hirotaka Ebisui And Thanos Kalogerakis - CTK Insights

4 weeks ago

Hirotaka Ebisui has found that in the case of the right triangle,

A

′

+

B

′

=

5

C

′

A

′

+B

′

=5C

′

. On informing me of that result, Thanos added an identity for the next layer

A

′

′

+

B

′

′

=

C

′

′

.

A

′′

+B

′′

=C

′′

.

That was exciting enough for me to investigate. I can happily and proudly report that, for the next layer,

A

′

′

′

+

B

′

′

′

=

5

C

′

′

′

A

′′′

+B

′′′

=5C

′′′

.

plane-geometry
rather-interesting
mathematical-recreations
looking-to-see
to-write-about
A

′

+

B

′

=

5

C

′

A

′

+B

′

=5C

′

. On informing me of that result, Thanos added an identity for the next layer

A

′

′

+

B

′

′

=

C

′

′

.

A

′′

+B

′′

=C

′′

.

That was exciting enough for me to investigate. I can happily and proudly report that, for the next layer,

A

′

′

′

+

B

′

′

′

=

5

C

′

′

′

A

′′′

+B

′′′

=5C

′′′

.

4 weeks ago

[1711.00867] The (Un)reliability of saliency methods

4 weeks ago

Saliency methods aim to explain the predictions of deep neural networks. These methods lack reliability when the explanation is sensitive to factors that do not contribute to the model prediction. We use a simple and common pre-processing step ---adding a constant shift to the input data--- to show that a transformation with no effect on the model can cause numerous methods to incorrectly attribute. In order to guarantee reliability, we posit that methods should fulfill input invariance, the requirement that a saliency method mirror the sensitivity of the model with respect to transformations of the input. We show, through several examples, that saliency methods that do not satisfy input invariance result in misleading attribution.

via:?
machine-learning
looking-to-see
saliency
define-your-terms
algorithms
criticism
to-write-about
4 weeks ago

Abandoned Footnotes: Utopia and Revolution

4 weeks ago

(Mostly a disorganized discussion of Richard Stites’ superb Revolutionary Dreams: Utopian Vision and Experimental Life in the Russian Revolution, by someone who is not a historian. Contains half-baked analogies to current events).

literary-criticism
history
to-read
rather-interesting
4 weeks ago

Feature Visualization

4 weeks ago

This article focusses on feature visualization. While feature visualization is a powerful tool, actually getting it to work involves a number of details. In this article, we examine the major issues and explore common approaches to solving them. We ﬁnd that remarkably simple methods can produce high-quality visualizations. Along the way we introduce a few tricks for exploring variation in what neurons react to, how they interact, and how to improve the optimization process.

neural-networks
inverse-problems
generative-art
to-write-about
4 weeks ago

The New CSS Layout, An Excerpt · An A List Apart Article

4 weeks ago

As we have seen, flexbox wasn’t designed for grid layouts—but this is where our newest specification is most at home. CSS Grid Layout does exactly what its name suggests: it enables the creation of grid layouts in CSS. This is two-dimensional layout—laying things out as a row and a column at the same time. We’ll go over many more examples of Grid Layout in the rest of this book, but let’s start by seeing how Grid can solve the problem we had with making flexbox display like a grid.

web-design
css
layout
library
to-understand
to-do
4 weeks ago

[1711.01032] A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings

4 weeks ago

Stable matching is a classical combinatorial problem that has been the subject of intense theoretical and empirical study since its introduction in 1962 in a seminal paper by Gale and Shapley. In this paper, we provide a new upper bound on f(n), the maximum number of stable matchings that a stable matching instance with n men and n women can have. It has been a long-standing open problem to understand the asymptotic behavior of f(n) as n→∞, first posed by Donald Knuth in the 1970s. Until now the best lower bound was approximately 2.28n, and the best upper bound was 2nlogn−O(n). In this paper, we show that for all n, f(n)≤cn for some universal constant c. This matches the lower bound up to the base of the exponent. Our proof is based on a reduction to counting the number of downsets of a family of posets that we call "mixing". The latter might be of independent interest.

combinatorics
open-questions
out-of-the-box
matchings
to-write-about
consider:simulation
consider:heuristics
4 weeks ago

[1404.1008] Spectral concentration and greedy k-clustering

4 weeks ago

A popular graph clustering method is to consider the embedding of an input graph into R^k induced by the first k eigenvectors of its Laplacian, and to partition the graph via geometric manipulations on the resulting metric space. Despite the practical success of this methodology, there is limited understanding of several heuristics that follow this framework. We provide theoretical justification for one such natural and computationally efficient variant.

Our result can be summarized as follows. A partition of a graph is called strong if each cluster has small external conductance, and large internal conductance. We present a simple greedy spectral clustering algorithm which returns a partition that is provably close to a suitably strong partition, provided that such a partition exists. A recent result shows that strong partitions exist for graphs with a sufficiently large spectral gap between the k-th and (k+1)-th eigenvalues. Taking this together with our main theorem gives a spectral algorithm which finds a partition close to a strong one for graphs with large enough spectral gap. We also show how this simple greedy algorithm can be implemented in near-linear time for any fixed k and error guarantee. Finally, we evaluate our algorithm on some real-world and synthetic inputs.

clustering
graph-theory
algorithms
rather-interesting
heuristics
performance-measure
to-write-about
Our result can be summarized as follows. A partition of a graph is called strong if each cluster has small external conductance, and large internal conductance. We present a simple greedy spectral clustering algorithm which returns a partition that is provably close to a suitably strong partition, provided that such a partition exists. A recent result shows that strong partitions exist for graphs with a sufficiently large spectral gap between the k-th and (k+1)-th eigenvalues. Taking this together with our main theorem gives a spectral algorithm which finds a partition close to a strong one for graphs with large enough spectral gap. We also show how this simple greedy algorithm can be implemented in near-linear time for any fixed k and error guarantee. Finally, we evaluate our algorithm on some real-world and synthetic inputs.

4 weeks ago

Proofs are not only often beautiful but also necessary | Dan McQuillan

4 weeks ago

I hope you get the idea. When mathematicians seem obsessed with rigor, it is at least in part due to our history of making mistakes, seemingly every time we tried to jump to a conclusion. But perhaps there’s something more. So for that, we end with a quote from William Thurston:

what we are doing is finding ways for people to understand and think about mathematics… what they really want is usually not some collection of of ‘answers’-what they want is understanding.

mathematics
proof
philosophy
to-write-about
consider:representation
what we are doing is finding ways for people to understand and think about mathematics… what they really want is usually not some collection of of ‘answers’-what they want is understanding.

4 weeks ago

Minus Infinity |

4 weeks ago

Today we’ll talk about some paradoxical things, like the logarithm of zero, and the maximum element of a set of real numbers that doesn’t contain any real numbers at all. More importantly, we’ll see how mathematicians try to wrap their heads around such enigmas.

All today’s logarithms will be base ten logarithms; so the logarithm of 100 is 2 (because 100 is 102) and the logarithm of 1/1000 is −3 (because 1/1000 is 10−3)). The logarithm of 0 would have to be an x that satisfies the equation 10x = 0. Since there’s no such number, we could just say “log 0 is undefined” and walk away, with our consciences clear and our complacency unruffled.

mathematical-recreations
math
representation
to-read
to-write-about
All today’s logarithms will be base ten logarithms; so the logarithm of 100 is 2 (because 100 is 102) and the logarithm of 1/1000 is −3 (because 1/1000 is 10−3)). The logarithm of 0 would have to be an x that satisfies the equation 10x = 0. Since there’s no such number, we could just say “log 0 is undefined” and walk away, with our consciences clear and our complacency unruffled.

4 weeks ago

Swine in a Line |

4 weeks ago

What I hope you take away from this essay is a sense that there’s an interestingly tangled relationship between games, numbers, and the devices we use for representing and manipulating numbers. The abacus was introduced as a way to represent and manipulate numbers for purposes of counting. On the other hand, we can play games with an abacus (the Swine in a Line games) that don’t immediately seem to be about numbers at all, but if we play with those games for long enough, we come to see that underlying the chaos of one configuration giving rise to another, and then another, there is a pattern, and this pattern is most naturally expressed in the language of number.

number-theory
mathematical-recreations
math
pedagogy
ludics
to-write-about
sandpiles
complexology
4 weeks ago

Prof. Engel’s Marvelously Improbable Machines |

4 weeks ago

When the path from a simple question to a simple answer leads you through swamps of computation, you can accept that some amount of tromping through swamps is unavoidable in math and in life, or you can think harder and try to find a different route. This is a story of someone who thought harder.

His name is Arthur Engel. Back in the 1970s this German mathematician was in Illinois, teaching probability theory and other topics to middle-school and high-school students. He taught kids in grades 7 and up how to answer questions like “If you roll a fair die, how long on average should you expect to wait until the die shows a three?” The questions are simple, and the answers also tend to be simple: whole numbers, or fractions with fairly small numerators and denominators. You can solve these problems using fraction arithmetic (in the simpler cases) or small systems of linear equations (for more complicated problems), and those are the methods that Engel taught his students up through the end of 1973.

mathematical-recreations
math
computation
to-write-about
see-also:exploding-dots
His name is Arthur Engel. Back in the 1970s this German mathematician was in Illinois, teaching probability theory and other topics to middle-school and high-school students. He taught kids in grades 7 and up how to answer questions like “If you roll a fair die, how long on average should you expect to wait until the die shows a three?” The questions are simple, and the answers also tend to be simple: whole numbers, or fractions with fairly small numerators and denominators. You can solve these problems using fraction arithmetic (in the simpler cases) or small systems of linear equations (for more complicated problems), and those are the methods that Engel taught his students up through the end of 1973.

4 weeks ago

ShadowCon 2017- Math Play - Kassia Wedekind on Vimeo

4 weeks ago

ShadowCon 2017- Math Play - Kassia Wedekind

lecture
mathematics
ludic
mathematical-recreations
to-watch
4 weeks ago

[1711.02450] Shape Representation by Zippable Ribbons

4 weeks ago

Shape fabrication from developable parts is the basis for arts such as papercraft and needlework, as well as modern architecture and CAD in general, and it has inspired much research. We observe that the assembly of complex 3D shapes created by existing methods often requires first fabricating many small flat parts and then carefully following instructions to assemble them together. Despite its significance, this error prone and tedious process is generally neglected in the discussion. We propose an approach for shape representation through a single developable part that attaches to itself and requires no assembly instructions. Our inspiration comes from the so-called zipit bags, which are made of a single, long ribbon with a zipper around its boundary. In order to "assemble" the bag, one simply needs to zip up the ribbon. Our method operates in the same fashion, but it can be used to approximate any shape. Given a 3D model, our algorithm produces plans for a single 2D shape that can be laser cut in few parts from flat fabric or paper. We can then attach a zipper along the boundary for quick assembly and disassembly, or apply more traditional approaches, such as gluing and stitching. We show physical and virtual results that demonstrate the capabilities of our method and the ease with which shapes can be assembled.

via:gigasquid
computational-geometry
construction
manufacturability
representation
algorithms
to-write-about
via:twitter
topology
4 weeks ago

The Global Roots of Exploding Dots - YouTube

4 weeks ago

Exploding Dots, an exciting approach to teaching K-12 math that over a million schoolchildren learned as part of Global Math Week 2017, is the brainchild of James Tanton. But he didn't create it in a vacuum. In this video I give the backstory, taking you on a world-wide time-traveling tour of mathematical history from the ancient past to the near future.

mathematics
pedagogy
history
rather-interesting
have-watched
to-write-about
4 weeks ago

[1710.07179] Increasing Labelings, Generalized Promotion, and Rowmotion

4 weeks ago

We generalize Bender-Knuth promotion on linear extensions to an analogous action on increasing labelings of any finite poset, in which the restrictions on the values of the labels satisfy a natural consistency condition. We give an equivariant bijection between such increasing labelings under this generalized promotion and order ideals in an associated poset under rowmotion. Additionally, we give a criterion for when certain kinds of toggle group actions on order ideals of a finite poset will be conjugate to rowmotion. These results build upon work of O.\ Pechenik with the first two authors in the case of rectangular increasing tableaux and work of N.\ Williams with the second author relating promotion and rowmotion on ranked posets. We apply these results to posets embedded in the Cartesian product of ranked posets and increasing labelings with labels between 1 and q, in which case we obtain new instances of the resonance phenomenon.

partial-ordering
combinatorics
representation
rather-interesting
to-understand
to-write-about
to-simulate
algorithms
consider:fitness
consider:inverse-problem
4 weeks ago

[1710.06915] MatchPy: A Pattern Matching Library

4 weeks ago

Pattern matching is a powerful tool for symbolic computations, based on the well-defined theory of term rewriting systems. Application domains include algebraic expressions, abstract syntax trees, and XML and JSON data. Unfortunately, no lightweight implementation of pattern matching as general and flexible as Mathematica exists for Python Mathics,MacroPy,patterns,PyPatt. Therefore, we created the open source module MatchPy which offers similar pattern matching functionality in Python using a novel algorithm which finds matches for large pattern sets more efficiently by exploiting similarities between patterns.

programming
Python
programming-language
pattern-matching
library
to-understand
to-write-about
4 weeks ago

[1708.08319] Fast Access to Columnar, Hierarchically Nested Data via Code Transformation

4 weeks ago

Big Data query systems represent data in a columnar format for fast, selective access, and in some cases (e.g. Apache Drill), perform calculations directly on the columnar data without row materialization, avoiding runtime costs.

However, many analysis procedures cannot be easily or efficiently expressed as SQL. In High Energy Physics, the majority of data processing requires nested loops with complex dependencies. When faced with tasks like these, the conventional approach is to convert the columnar data back into an object form, usually with a performance price.

This paper describes a new technique to transform procedural code so that it operates on hierarchically nested, columnar data natively, without row materialization. It can be viewed as a compiler pass on the typed abstract syntax tree, rewriting references to objects as columnar array lookups.

We will also present performance comparisons between transformed code and conventional object-oriented code in a High Energy Physics context.

databases
data-modeling
rather-interesting
algorithms
representation
to-understand
big-data
However, many analysis procedures cannot be easily or efficiently expressed as SQL. In High Energy Physics, the majority of data processing requires nested loops with complex dependencies. When faced with tasks like these, the conventional approach is to convert the columnar data back into an object form, usually with a performance price.

This paper describes a new technique to transform procedural code so that it operates on hierarchically nested, columnar data natively, without row materialization. It can be viewed as a compiler pass on the typed abstract syntax tree, rewriting references to objects as columnar array lookups.

We will also present performance comparisons between transformed code and conventional object-oriented code in a High Energy Physics context.

4 weeks ago

[1711.00963] The Computational Complexity of Finding Separators in Temporal Graphs

4 weeks ago

Vertex separators, that is, vertex sets whose deletion disconnects two distinguished vertices in a graph, play a pivotal role in algorithmic graph theory. For instance, the concept of tree decompositions of graphs is tightly connected to the separator concept. For many realistic models of the real world, however, it is necessary to consider graphs whose edge set changes with time. More specifically, the edges are labeled with time stamps. In the literature, these graphs are referred to as temporal graphs, temporal networks, time-varying networks, edge-scheduled networks, etc. While there is an extensive literature on separators in "static" graphs, much less is known for the temporal setting. Building on previous work (e.g., Kempe et al. [STOC '00]), for the first time we systematically investigate the (parameterized) complexity of finding separators in temporal graphs. Doing so, we discover a rich landscape of computationally (fixed-parameter) tractable and intractable cases. In particular, we shed light on the so far seemingly overlooked fact that two frequently used models of temporal separation may lead to quite significant differences in terms of computational complexity. More specifically, considering paths in temporal graphs one may distinguish between strict paths (the time stamps along a path are strictly increasing) and non-strict paths (the time stamps along a path are monotonically non-decreasing). We observe that the corresponding strict case of temporal separators leads to several computationally much easier to handle cases than the non-strict case does.

graph-theory
combinatorics
dynamical-systems
robustness
nudge-targets
heuristics
algorithms
to-write-about
4 weeks ago

[1602.03311] Efficient weight vectors from pairwise comparison matrices

4 weeks ago

Pairwise comparison matrices are frequently applied in multi-criteria decision making. A weight vector is called efficient if no other weight vector is at least as good in approximating the elements of the pairwise comparison matrix, and strictly better in at least one position. A weight vector is weakly efficient if the pairwise ratios cannot be improved in all non-diagonal positions. We show that the principal eigenvector is always weakly efficient, but numerical examples show that it can be inefficient. The linear programs proposed test whether a given weight vector is (weakly) efficient, and in case of (strong) inefficiency, an efficient (strongly) dominating weight vector is calculated. The proposed algorithms are implemented in Pairwise Comparison Matrix Calculator, available at pcmc.online.

optimization
numerical-methods
multiobjective-optimization
heuristics
matrices
inference
rather-interesting
try-not-to-do-this
to-write-about
consider:inverse-problem
consider:robustness
4 weeks ago

[1609.07531] Popular Matchings with Multiple Partners

4 weeks ago

Our input is a bipartite graph G=(A∪B,E) where each vertex in A∪B has a preference list strictly ranking its neighbors. The vertices in A and in B are called students and courses, respectively. Each student a seeks to be matched to 𝖼𝖺𝗉(a)≥1 courses while each course b seeks 𝖼𝖺𝗉(b)≥1 many students to be matched to it. The Gale-Shapley algorithm computes a pairwise-stable matching (one with no blocking edge) in G in linear time. We consider the problem of computing a popular matching in G -- a matching M is popular if M cannot lose an election to any matching where vertices cast votes for one matching versus another. Our main contribution is to show that a max-size popular matching in G can be computed by the 2-level Gale-Shapley algorithm in linear time. This is an extension of the classical Gale-Shapley algorithm and we prove its correctness via linear programming.

operations-research
combinatorics
optimization
computational-complexity
algorithms
heuristics
nudge-targets
consider:looking-to-see
to-write-about
consider:comparing-to-random
4 weeks ago

[1710.00104] Small Satellite Constellation Separation using Linear Programming based Differential Drag Commands

4 weeks ago

We study the optimal control of an arbitrarily large constellation of small satellites operating in low Earth orbit. Simulating the lack of on-board propulsion, we limit our actuation to the use of differential drag maneuvers to make in-plane changes to the satellite orbits. We propose an efficient method to separate a cluster of satellites into a desired constellation shape while respecting actuation constraints and maximizing the operational lifetime of the constellation. By posing the problem as a linear program, we solve for the optimal drag commands for each of the satellites on a daily basis with a shrinking-horizon model predictive control approach. We then apply this control strategy in a nonlinear orbital dynamics simulation with a simple, varying atmospheric density model. We demonstrate the ability to control a cluster of 100+ satellites starting at the same initial conditions in a circular low Earth orbit to form an equally spaced constellation (with a relative angular separation error tolerance of one-tenth a degree). The constellation separation task can be executed in 71 days, a time frame that is competitive for the state-of-the-practice. This method allows us to trade the time required to converge to the desired constellation with a sacrifice in the overall constellation lifetime, measured as the maximum altitude loss experienced by one of the satellites in the group after the separation maneuvers.

nonlinear-dynamics
control-theory
rather-interesting
simulation
nudge-targets
consider:coordination
consider:looking-to-see
to-write-about
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
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
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
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