recentpopularlog in
« earlier  
Instant Pot Collard Greens | Simply Happy Foodie
Instant Pot Collard Greens cooked with a ham hock and a few seasonings ends up being a delicious and nutritious dish that to me, is synonymous with the South. What used to take hours to cook in my dutch oven now takes a little over an hour! If you haven’t tried pressure cooker collard greens, I highly recommend it!
recipes  cooking  instant-pot  have-made 
3 days ago
[1811.01491] Discrepancy in random hypergraph models
We study hypergraph discrepancy in two closely related random models of hypergraphs on n vertices and m hyperedges. The first model, 1, is when every vertex is present in exactly t randomly chosen hyperedges. The premise of this is closely tied to, and motivated by the Beck-Fiala conjecture. The second, perhaps more natural model, 2, is when the entries of the m×n incidence matrix is sampled in an i.i.d. fashion, each with probability p. We prove the following:
1. In 1, when log10n≪t≪n‾√, and m=n, we show that the discrepancy of the hypergraph is almost surely at most O(t√). This improves upon a result of Ezra and Lovett for this range of parameters.
2. In 2, when p=12, and n=Ω(mlogm), we show that the discrepancy is almost surely at most 1. This answers an open problem of Hoberg and Rothvoss.
hypergraphs  graph-theory  random-graphs  rather-interesting  sampling  generative-models  algorithms  looking-to-see  to-write-about  to-simulate  consider:performance-measures 
17 days ago
[1812.07270] AVATAR : Fixing Semantic Bugs with Fix Patterns of Static Analysis Violations
Fix pattern-based patch generation is a promising direction in Automated Program Repair (APR). Notably, it has been demonstrated to produce more acceptable and correct patches than the patches obtained with mutation operators through genetic programming. The performance of pattern-based APR systems, however, depends on the fix ingredients mined from fix changes in development histories. Unfortunately, collecting a reliable set of bug fixes in repositories can be challenging. In this paper, we propose to investigate the possibility in an APR scenario of leveraging code changes that address violations by static bug detection tools. To that end, we build the AVATAR APR system, which exploits fix patterns of static analysis violations as ingredients for patch generation. Evaluated on the Defects4J benchmark, we show that, assuming a perfect localization of faults, AVATAR can generate correct patches to fix 34/39 bugs. We further find that AVATAR yields performance metrics that are comparable to that of the closely-related approaches in the literature. While AVATAR outperforms many of the state-of-the-art pattern-based APR systems, it is mostly complementary to current approaches. Overall, our study highlights the relevance of static bug finding tools as indirect contributors of fix ingredients for addressing code defects identified with functional test cases.
refactoring  software-engineering  performance-measure  rather-interesting  rewriting-systems  to-download  to-simulate  consider:refactoring-as-such 
17 days ago
[1812.07999] Hausdorff measures and packing measures of the limit sets of CIFSs of generalized complex continued fractions
We consider a family of CIFSs of the generalized complex continued fractions with a complex parameter space. We show that for each CIFS of the family, the Hausdorff measure of the limit set of the CIFS with respect to the Hausdorff dimen/sion is zero and the packing measure of the limit set of the CIFS with respect to the Hausdorff dimension is positive (main result). This is a new phenomenon of infinite CIFSs which cannot hold in finite CIFSs. We prove the main result by showing some estimates for the unique conformal measure of each CIFS of the family and by using some geometric observations.
number-theory  fractals  continued-fractions  representation  rather-interesting  nonlinear-dynamics  to-write-about  to-simulate  consider:stability  consider:visualization 
17 days ago
[1901.02950] Spectral Approach to Verifying Non-linear Arithmetic Circuits
This paper presents a fast and effective computer algebraic method for analyzing and verifying non-linear integer arithmetic circuits using a novel algebraic spectral model. It introduces a concept of algebraic spectrum, a numerical form of polynomial expression; it uses the distribution of coefficients of the monomials to determine the type of arithmetic function under verification. In contrast to previous works, the proof of functional correctness is achieved by computing an algebraic spectrum combined with a local rewriting of word-level polynomials. The speedup is achieved by propagating coefficients through the circuit using And-Inverter Graph (AIG) datastructure. The effectiveness of the method is demonstrated with experiments including standard and Booth multipliers, and other synthesized non-linear arithmetic circuits up to 1024 bits containing over 12 million gates.
nonlinear-dynamics  electronics  engineering-design  rather-interesting  digital-circuits  verification  testing  simulation  to-write-about  to-simulate  consider:genetic-programming 
17 days ago
[1901.02998] Sentence Rewriting for Semantic Parsing
A major challenge of semantic parsing is the vocabulary mismatch problem between natural language and target ontology. In this paper, we propose a sentence rewriting based semantic parsing method, which can effectively resolve the mismatch problem by rewriting a sentence into a new form which has the same structure with its target logical form. Specifically, we propose two sentence-rewriting methods for two common types of mismatch: a dictionary-based method for 1-N mismatch and a template-based method for N-1 mismatch. We evaluate our entence rewriting based semantic parser on the benchmark semantic parsing dataset -- WEBQUESTIONS. Experimental results show that our system outperforms the base system with a 3.4% gain in F1, and generates logical forms more accurately and parses sentences more robustly.
natural-language-processing  rewriting-systems  artificial-intelligence  representation  algorithms  rather-interesting  to-write-about  to-simulate  consider:interactive-grammar 
17 days ago
An Algebraic Geometry Based Approach to Decentralized Control - Hyung Sik Shin - Google Books
Decentralized control has been one of the important problems in systems and control engineering. Computing an optimal decentralized controller for general linear systems, however, is known to be a very challenging task. In particular, designing an optimal decentralized controller in the standard framework of a linear system with quadratic cost and Gaussian noise is well known to be extremely hard even in very simple and small sized problems. Because of this fact, previous work has focused on characterizing several different classes of problems for which an optimal decentralized controller may be efficiently computed. The set of quadratically invariant problems is one of the largest known class of such problems. This dissertation provides a novel, general, and powerful framework for addressing decentralized control by introducing the idea of using rational elimination theory of algebraic geometry. We show that, in certain cases, this approach reduces the set of closed-loop maps of decentralized control to the solution set of a collection of linear equations. We show how to use these linear equations to find an optimal decentralized controller. We also prove that if a system is quadratically invariant then under an appropriate technical condition the resulting elimination set is affine. We further illustrate that our approach can be well applied to a strictly larger class of decentralized control problem than the quadratically invariant one by presenting a simple example: the example shows that there are problems which are not quadratically invariant but for which the resulting elimination description is affine.
thesis  control-theory  distributed-processing  collective-behavior  rather-interesting  to-write-about  to-simulate  to-animate 
17 days ago
More on sums of palindromes | The Math Less Traveled
In his email, Lewis Baxter also pointed me to an even more recent paper by Aayush Rajasekaran, Jeffrey Shallit, and Tim Smith which uses a completely different method to resolve the remaining questions: it turns out that the conjectures were correct; we now know that every positive integer can indeed be written as a sum of four binary palindromes, and only three palindromes in base 3 or base 4! Jeffrey Shallit has a nice blog post explaining their method here. It’s not clear to me whether their method can be used to produce an actual algorithm for finding base-2, -3, or -4 palindromes that sum to a given number, though it certainly should be possible.
number-theory  proof  rather-interesting  nudge-targets  consider:generators  to-write-about  to-simulate 
17 days ago
More on the Internet of Snails - Justin Erik Halldór Smith
This is a talk I gave last year in Marseille, under circumstances that, to be honest, I'm still not sure I understand. You'll notice anyhow that the production values are unusually high. 
philosophy  philosophy-of-engineering  to-watch  video 
18 days ago
[1809.05923] What is Applied Category Theory?
This is a collection of introductory, expository notes on applied category theory, inspired by the 2018 Applied Category Theory Workshop, and in these notes we take a leisurely stroll through two themes (functorial semantics and compositionality), two constructions (monoidal categories and decorated cospans) and two examples (chemical reaction networks and natural language processing) within the field.
category-theory  mathematics  to-understand  surveys  formalization 
18 days ago
[2001.08635] A Study of the Tasks and Models in Machine Reading Comprehension
To provide a survey on the existing tasks and models in Machine Reading Comprehension (MRC), this report reviews: 1) the dataset collection and performance evaluation of some representative simple-reasoning and complex-reasoning MRC tasks; 2) the architecture designs, attention mechanisms, and performance-boosting approaches for developing neural-network-based MRC models; 3) some recently proposed transfer learning approaches to incorporating text-style knowledge contained in external corpora into the neural networks of MRC models; 4) some recently proposed knowledge base encoding approaches to incorporating graph-style knowledge contained in external knowledge bases into the neural networks of MRC models. Besides, according to what has been achieved and what are still deficient, this report also proposes some open problems for the future research.
natural-language-processing  artificial-intelligence  rather-interesting  survey  to-write-about 
18 days ago
Open Call | Pop!
What do we imagine when we imagine open infrastructures? What does this concept entail, in its vision, and in its drive to realization? This issue of Pop! is devoted to both imaginative and empirical investigations into what open infrastructures might be and might provide for us. We invite submissions – from scholars, librarians, developers, and anyone else who is interested in this topic – that explore the possibilities and help clarify and articulate the opportunities, challenges, upsides, and pitfalls of re-thinking the infrastructure of scholarly communications.
openness  academic-culture  intellectual-property  CFP  to-watch 
18 days ago
Veblen’s Idea of Business Versus Industry | Ian Welsh
To Veblen the money economy was “institutional,” and not a natural requirement of humanity. He used “institution” in a broad and new sense, as a method of action arrived at by habituation and convention and generally agreed upon. Most “orthodox” economists would have agreed with this, but they presumed that “institutions,” in the ordinary sense of the term, arose in response to men’s needs and represented the state to which man had progressed in his struggle with nature. Veblen criticized this view as ignoring what the institution had become, an end rather than a means. To him “institutions” of price, property, and contract were active forces rather than passive embodiments of nature to which man adjusted himself by pleasure and pain. “Institutions” were themselves the embodiments and channels of the activity of man. Habits of thought were created by habits of action. Money, therefore, could not be viewed as a medium of exchange, and the successful large businessman ceased to be merely an intermediary in the efficient organization of industrial forces to satisfy men’s wants. With money and securities made ends in themselves, or, more accurately, with the complex of “institutions” comprising modern business given an active or creative role, corporation finance became the main character in the drama. On its side, the machine technology, which comprised the industrial “institutions,” could not be viewed merely as an element of production, different only in degree from artisan labor, but as a comprehensive and delicate process with a distinctive life of its own. Now the objective of the pecuniary experts was neither the supplying of goods to the consumer nor the efficiency of industry, but the accumulation of funded wealth, the making of money. Every step in the never-ceasing integration of industry, however, provided them with greater opportunities to achieve their ends, and these in their turn disturbed the arrangements of industry.
Veblen  political-economy  to-read  capitalism  economics  financial-crisis  finance 
18 days ago
Multidimensional quantitative analysis of mRNA expression within intact vertebrate embryos | bioRxiv
For decades, in situ hybridization methods have been essential tools for studies of vertebrate development and disease, as they enable qualitative analyses of mRNA expression in an anatomical context. Quantitative mRNA analyses typically sacrifice the anatomy, relying on embryo microdissection, dissociation, cell sorting, and/or homogenization. Here, we eliminate the tradeoff between quantitation and anatomical context, using multiplexed in situ hybridization chain reaction (HCR) to perform accurate and precise relative quantitation of mRNA expression with subcellular resolution within whole-mount vertebrate embryos. Gene expression can be queried in two directions: read-out from anatomical space to expression space reveals co-expression relationships in selected regions of the specimen; conversely, read-in from multidimensional expression space to anatomical space reveals those anatomical locations in which selected gene co-expression relationships occur. As we demonstrate by examining gene circuits underlying somitogenesis, quantitative read-out and read-in analyses provide the strengths of flow cytometry expression analyses, but by preserving subcellular anatomical context, they enable iterative bi-directional queries that open a new era for in situ hybridization.
evo-devo  developmental-biology  molecular-biology  indistinguishable-from-magic  visualization  experiment  rather-interesting  to-write-about  consider:analogs-in-Alife 
18 days ago
[2003.02320] Knowledge Graphs
In this paper we provide a comprehensive introduction to knowledge graphs, which have recently garnered significant attention from both industry and academia in scenarios that require exploiting diverse, dynamic, large-scale collections of data. After a general introduction, we motivate and contrast various graph-based data models and query languages that are used for knowledge graphs. We discuss the roles of schema, identity, and context in knowledge graphs. We explain how knowledge can be represented and extracted using a combination of deductive and inductive techniques. We summarise methods for the creation, enrichment, quality assessment, refinement, and publication of knowledge graphs. We provide an overview of prominent open knowledge graphs and enterprise knowledge graphs, their applications, and how they use the aforementioned techniques. We conclude with high-level future research directions for knowledge graphs.
representation  data-structures  ontology  to-understand  to-write-about  to-learn  software-development-is-not-programming 
18 days ago
Understanding Society: Non-action in times of catastrophe
One other aspect of the book bears mention, though only loosely related to the theory of collective action and abdication that is the primary content of the book. Ermakoff's discussion of the challenges that come along with defining "events" is excellent (chapter 1). He correctly observes that an event is a nominal construct, amenable to definition and selection by different observers depending on their theoretical and political interests.
Events are nominal constructs. Their referents are bundles of actions and decisions that analysts and commentators abstract from the flow of historical time. This abstraction is based on a variety of criteria—temporal contiguity, causal density, and significance for subsequent happenings—routinely mobilized by synthetic judgments about the past. Because events are temporal constructs, their temporal boundaries can never be taken for granted. They take on different values depending on whether we derive these boundaries from the subjective statements left by contemporary actors (Bearman et al. 1999) or construct them in light of an analytical relevance criterion derived from the problem at hand (Sewell 1996, 877).
history  it-rhymes  philosophy-of-history  political-economy  collective-behavior  culture  modernism  abdication  seems-salient 
19 days ago
Half-Truth Histories by Matthew Guzdial
This is a GM-less game for creating the contradictory histories and map of a game world. It is designed for play just before a tabletop RPG campaign to set up a world and the often contradictory things it’s people believe about it. 

In-fiction the game is a conversation around a fire between a number of travellers, somewhere in the game world, sometime before the game takes place. The exact details of when and where need not be decided until after the game is done, if ever.

Half-Truth Histories makes no assumption of setting. 

Mechanically, the game is a bit like the card games UNO or War, but played much more slowly and without any reflex requirement. The closest games to Half-Truth Histories are the Quiet Year, Microscope, and The Extraordinary Adventures of Baron Munchausen, which are direct inspirations. But where the Quiet Year creates the history of the fall of one settlement and it’s map, Half-Truth Histories focuses on the contradictory stories of a whole game world and it’s map.
ttRPG  roleplaying-games  collaboration  storytelling  rather-interesting 
19 days ago
[1801.06924] Hyperuniform States of Matter
Hyperuniform states of matter are correlated systems that are characterized by an anomalous suppression of long-wavelength (i.e., large-length-scale) density fluctuations compared to those found in garden-variety disordered systems, such as ordinary fluids and amorphous solids. All perfect crystals, perfect quasicrystals and special disordered systems are hyperuniform. Thus, the hyperuniformity concept enables a unified framework to classify and structurally characterize crystals, quasicrystals and the exotic disordered varieties. While disordered hyperuniform systems were largely unknown in the scientific community over a decade ago, now there is a realization that such systems arise in a host of contexts across the physical, materials, chemical, mathematical, engineering, and biological sciences, including disordered ground states, glass formation, jamming, Coulomb systems, spin systems, photonic and electronic band structure, localization of waves and excitations, self-organization, fluid dynamics, number theory, stochastic point processes, integral and stochastic geometry, the immune system, and photoreceptor cells. Such unusual amorphous states can be obtained via equilibrium or nonequilibrium routes, and come in both quantum-mechanical and classical varieties. The connections of hyperuniform states of matter to many different areas of fundamental science appear to be profound and yet our theoretical understanding of these unusual systems is only in its infancy. The purpose of this review article is to introduce the reader to the theoretical foundations of hyperuniform ordered and disordered systems. Special focus will be placed on fundamental and practical aspects of the disordered kinds, including our current state of knowledge of these exotic amorphous systems as well as their formation and novel physical properties.
statistical-mechanics  materials-science  models  rather-interesting  probability-theory  emergent-design  to-write-about  to-simulate  consider:heuristics  consider:boundary-conditions  consider:optimization 
20 days ago
There is an Antidote to Demagoguery – it’s Called Political Rewilding - Resilience
The same applies to politics. Mainstream politics, controlled by party machines, has sought to reduce the phenomenal complexity of human society into a simple, linear model that can be controlled from the centre. The political and economic systems it creates are simultaneously highly unstable and lacking in dynamism; susceptible to collapse, as many northern towns can testify, while unable to regenerate themselves. They become vulnerable to the toxic, invasive forces of ethno-nationalism and supremacism.
political-economy  anarchism  localism  yeah-well 
28 days ago
[1902.07404] The Provability of Consistency
Hilbert's program of establishing consistency of theories like Peano arithmetic PA using only finitary tools has long been considered impossible. The standard reference here is Goedel's Second Incompleteness Theorem by which a theory T, if consistent, cannot prove the arithmetical formula ConT, 'for all x, x is not a code of a proof of a contradiction in T.' We argue that such arithmetization of consistency distorts the problem. ConT is stronger than the original notion of consistency, hence Goedel's theorem does not yield impossibility of proving consistency by finitary tools. We consider consistency in its standard form 'no sequence of formulas S is a derivation of a contradiction.' Using partial truth definitions, for each derivation S in PA we construct a finitary proof that S does not contain 0=1. This establishes consistency for PA by finitary means and vindicates, to some extent, Hilbert's consistency program. This also suggests that in the arithmetical form, consistency, similar to induction, reflection, truth, should be represented by a scheme rather than by a single formula.
formal-logic  mathematics  representation  proof  philosophy  rather-interesting  the-mangle-in-practice 
29 days ago
[1608.02638] Asymptotic laws for random knot diagrams
We study random knotting by considering knot and link diagrams as decorated, (rooted) topological maps on spheres and pulling them uniformly from among sets of a given number of vertices n, as first established in recent work with Cantarella and Mastin. The knot diagram model is an exciting new model which captures both the random geometry of space curve models of knotting as well as the ease of computing invariants from diagrams.
We prove that unknot diagrams are asymptotically exponentially rare, an analogue of Sumners and Whittington's landmark result for self-avoiding walks. Our proof uses the same key idea: We first show that knot diagrams obey a pattern theorem, which describes their fractal structure. We examine how quickly this behavior occurs in practice. As a consequence, almost all diagrams are asymmetric, simplifying sampling from this model. We conclude with experimental data on knotting in this model. This model of random knotting is similar to those studied by Diao et al., and Dunfield et al.
knot-theory  probability-theory  rather-interesting  generative-models  representation  to-write-about  to-simulate  consider:sampling  consider:feature-discovery 
29 days ago
[1911.01547] On the Measure of Intelligence
To make deliberate progress towards more intelligent and more human-like artificial systems, we need to be following an appropriate feedback signal: we need to be able to define and evaluate intelligence in a way that enables comparisons between two systems, as well as comparisons with humans. Over the past hundred years, there has been an abundance of attempts to define and measure intelligence, across both the fields of psychology and AI. We summarize and critically assess these definitions and evaluation approaches, while making apparent the two historical conceptions of intelligence that have implicitly guided them. We note that in practice, the contemporary AI community still gravitates towards benchmarking intelligence by comparing the skill exhibited by AIs and humans at specific tasks such as board games and video games. We argue that solely measuring skill at any given task falls short of measuring intelligence, because skill is heavily modulated by prior knowledge and experience: unlimited priors or unlimited training data allow experimenters to "buy" arbitrary levels of skills for a system, in a way that masks the system's own generalization power. We then articulate a new formal definition of intelligence based on Algorithmic Information Theory, describing intelligence as skill-acquisition efficiency and highlighting the concepts of scope, generalization difficulty, priors, and experience. Using this definition, we propose a set of guidelines for what a general AI benchmark should look like. Finally, we present a benchmark closely following these guidelines, the Abstraction and Reasoning Corpus (ARC), built upon an explicit set of priors designed to be as close as possible to innate human priors. We argue that ARC can be used to measure a human-like form of general fluid intelligence and that it enables fair general intelligence comparisons between AI systems and humans.
machine-learning  deep-learning  philosophy  philosophy-of-science  a-quick-way-to-start-an-argument  Geralt-says-hm 
29 days ago
[1909.04791] A Survey of Techniques All Classifiers Can Learn from Deep Networks: Models, Optimizations, and Regularization
Deep neural networks have introduced novel and useful tools to the machine learning community. Other types of classifiers can potentially make use of these tools as well to improve their performance and generality. This paper reviews the current state of the art for deep learning classifier technologies that are being used outside of deep neural networks. Non-network classifiers can employ many components found in deep neural network architectures. In this paper, we review the feature learning, optimization, and regularization methods that form a core of deep network technologies. We then survey non-neural network learning algorithms that make innovative use of these methods to improve classification. Because many opportunities and challenges still exist, we discuss directions that can be pursued to expand the area of deep learning for a variety of classification algorithms.
machine-learning  stamp-collecting  algorithms  heuristics  geralt-says-hm 
29 days ago
[1801.01143] Coins and Logic
We establish fun parallels between coin-weighing puzzles and knights-and-knaves puzzles.
mathematical-recreations  puzzles  logic  constraint-satisfaction  to-write-about  to-simulate  consider:sampling 
29 days ago
[1801.01570] How Many Rounds Should You Expect in Urn Solitaire?
As I've mentioned...

"Peter Winkler’s book is full of challenging problems that (smart) humans can do all by themselves, but take any of these problems, and tweak it ever-so-slightly, and then humans are hopeless, but luckily they can ask computer-kind to do their work."
probability-theory  open-questions  rather-interesting  to-simulate  to-write-about  consider:symbolic-regression  winkler-project 
29 days ago
p5.js 1.0 is Here! - Processing Foundation - Medium
Today we are excited to announce the 1.0 Release of p5.js! p5.js is a JavaScript library that aims to make creative expression and coding on the web accessible and inclusive for artists, designers, educators, and beginners. While it’s been nearly seven years since p5.js began, we intentionally embarked on the path to reach 1.0 a year ago when Kate Hollenbach worked on a first version of a roadmap for this. From there, the effort was led by Stalgia Grigg and Evelyn Masso, working with Lauren McCarthy, Cassie Tarakajian, Kenneth Lim, and the thousands of contributors from around the world that joined in working on everything including code, documentation, teaching, outreach, writing, art making, and more. Reflecting the p5.js project values, 1.0 is not just a code-based milestone, but one that is grounded by significant work on the documentation and community.
processing  javascript  library  generative-art  to-use  to-write-about  consider:quil 
29 days ago
SciCloj: About
Scicloj is an open, free and dynamic hub for building the Clojure ecosystem for data science, scientific computing and data engineering.

In short, it is for anyone who is interested in using Clojure to work with data.

There are various places where activities move forward (for more info check the Where section), and they are all open to discussion and contribution.
Clojure  scientific-computing  rather-interesting  to-watch 
29 days ago
[1907.08121] On Arrangements of Orthogonal Circles
In this paper, we study arrangements of orthogonal circles, that is, arrangements of circles where every pair of circles must either be disjoint or intersect at a right angle. Using geometric arguments, we show that such arrangements have only a linear number of faces. This implies that orthogonal circle intersection graphs have only a linear number of edges. When we restrict ourselves to orthogonal unit circles, the resulting class of intersection graphs is a subclass of penny graphs (that is, contact graphs of unit circles). We show that, similarly to penny graphs, it is NP-hard to recognize orthogonal unit circle intersection graphs.
computational-geometry  computational-complexity  geometric-graphs  rather-interesting  to-simulate  to-write-about  consider:relaxations  consider:sampling 
29 days ago
[1907.01218] Representing fitness landscapes by valued constraints to understand the complexity of local search
Local search is widely used to solve combinatorial optimisation problems and to model biological evolution, but the performance of local search algorithms on different kinds of fitness landscapes is poorly understood. Here we introduce a natural approach to modelling fitness landscapes using valued constraints. This allows us to investigate minimal representations (normal forms) and to consider the effects of the structure of the constraint graph on the tractability of local search. First, we show that for fitness landscapes representable by binary Boolean valued constraints there is a minimal necessary constraint graph that can be easily computed. Second, we consider landscapes as equivalent if they allow the same (improving) local search moves; we show that a minimal normal form still exists, but is NP-hard to compute. Next we consider the complexity of local search on fitness landscapes modelled by valued constraints with restricted forms of constraint graph. In the binary Boolean case, we prove that a tree-structured constraint graph gives a tight quadratic bound on the number of improving moves made by any local search; hence, any landscape that can be represented by such a model will be tractable for local search. We build two families of examples to show that both the conditions in our tractability result are essential. With domain size three, even just a path of binary constraints can model a landscape with an exponentially long sequence of improving moves. With a treewidth two constraint graph, even with a maximum degree of three, binary Boolean constraints can model a landscape with an exponentially long sequence of improving moves.
fitness-landscapes  combinatorics  metaheuristics  representation  rather-interesting  to-write-about  to-simulate  consider:no-free-lunch  consider:side-steps 
29 days ago
Data Structures for Mobile Data - ScienceDirect
Akinetic data structure(KDS) maintains an attribute of interest in a system of geometric objects undergoing continuous motion. In this paper we develop a concentual framework for kinetic data structures, we propose a number of criteria for the quality of such structures, and we describe a number of fundamental techniques for their design. We illustrate these general concepts by presenting kinetic data structures for maintaining the convex hull and the closest pair of moving points in the plane; these structures behave well according to the proposed quality criteria for KDSs.
data-structures  rather-interesting  to-simulate  to-write-about  consider:processing-sims  modeling  dynamical-systems 
29 days ago
[1303.1279] Equilateral L-Contact Graphs
We consider {\em L-graphs}, that is contact graphs of axis-aligned L-shapes in the plane, all with the same rotation. We provide several characterizations of L-graphs, drawing connections to Schnyder realizers and canonical orders of maximally planar graphs. We show that every contact system of L's can always be converted to an equivalent one with equilateral L's. This can be used to show a stronger version of a result of Thomassen, namely, that every planar graph can be represented as a contact system of square-based cuboids.
We also study a slightly more restricted version of equilateral L-contact systems and show that these are equivalent to homothetic triangle contact representations of maximally planar graphs. We believe that this new interpretation of the problem might allow for efficient algorithms to find homothetic triangle contact representations, that do not use Schramm's monster packing theorem.
geometric-graphs  rather-interesting  generative-models  graph-theory  to-write-about  to-simulate  consider:dynamics 
29 days ago
[1311.2032] A Simple, Faster Method for Kinetic Proximity Problems
For a set of n points in the plane, this paper presents simple kinetic data structures (KDS's) for solutions to some fundamental proximity problems, namely, the all nearest neighbors problem, the closest pair problem, and the Euclidean minimum spanning tree (EMST) problem. Also, the paper introduces KDS's for maintenance of two well-studied sparse proximity graphs, the Yao graph and the Semi-Yao graph.
We use sparse graph representations, the Pie Delaunay graph and the Equilateral Delaunay graph, to provide new solutions for the proximity problems. Then we design KDS's that efficiently maintain these sparse graphs on a set of n moving points, where the trajectory of each point is assumed to be an algebraic function of constant maximum degree s. We use the kinetic Pie Delaunay graph and the kinetic Equilateral Delaunay graph to create KDS's for maintenance of the Yao graph, the Semi-Yao graph, all the nearest neighbors, the closest pair, and the EMST. Our KDS's use O(n) space and O(nlogn) preprocessing time.
We provide the first KDS's for maintenance of the Semi-Yao graph and the Yao graph. Our KDS processes O(n2β2s+2(n)) (resp. O(n3β22s+2(n)logn)) events to maintain the Semi-Yao graph (resp. the Yao graph); each event can be processed in time O(logn) in an amortized sense. Here, βs(n) is an extremely slow-growing function.
Our KDS for maintenance of all the nearest neighbors and the closest pair processes O(n2β22s+2(n)logn) events. For maintenance of the EMST, our KDS processes O(n3β22s+2(n)logn) events. For all three of these problems, each event can be handled in time O(logn) in an amortized sense.
We improve the previous randomized kinetic algorithm for maintenance of all the nearest neighbors by Agarwal, Kaplan, and Sharir, and the previous EMST KDS by Rahmati and Zarei.
computational-geometry  data-structures  simulation  rather-interesting  to-understand  to-simulate  to-write-about 
29 days ago
[1410.0540] Matching in Gabriel Graphs
Given a set P of n points in the plane, the order-k Gabriel graph on P, denoted by k-GG, has an edge between two points p and q if and only if the closed disk with diameter pq contains at most k points of P, excluding p and q. We study matching problems in k-GG graphs. We show that a Euclidean bottleneck perfect matching of P is contained in 10-GG, but 8-GG may not have any Euclidean bottleneck perfect matching. In addition we show that 0-GG has a matching of size at least n−14 and this bound is tight. We also prove that 1-GG has a matching of size at least 2(n−1)5 and 2-GG has a perfect matching. Finally we consider the problem of blocking the edges of k-GG.
geometric-graphs  graph-theory  generative-models  computational-geometry  rather-interesting  to-simulate  to-write-about  consider:revisit-Sokal 
29 days ago
[1405.3527] On word-representability of polyomino triangulations
A graph G=(V,E) is word-representable if there exists a word w over the alphabet V such that letters x and y alternate in w if and only if (x,y) is an edge in E. Some graphs are word-representable, others are not. It is known that a graph is word-representable if and only if it accepts a so-called semi-transitive orientation.
The main result of this paper is showing that a triangulation of any convex polyomino is word-representable if and only if it is 3-colorable. We demonstrate that this statement is not true for an arbitrary polyomino. We also show that the graph obtained by replacing each 4-cycle in a polyomino by the complete graph K4 is word-representable. We employ semi-transitive orientations to obtain our results.
graph-theory  combinatorics  rather-interesting  to-understand  representation  formal-languages  automata  feature-construction  consider:group-theory 
29 days ago
[1307.1810] New results on word-representable graphs
A graph G=(V,E) is word-representable if there exists a word w over the alphabet V such that letters x and y alternate in w if and only if (x,y)∈E for each x≠y. The set of word-representable graphs generalizes several important and well-studied graph families, such as circle graphs, comparability graphs, 3-colorable graphs, graphs of vertex degree at most 3, etc. By answering an open question from [M. Halldorsson, S. Kitaev and A. Pyatkin, Alternation graphs, Lect. Notes Comput. Sci. 6986 (2011) 191--202. Proceedings of the 37th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2011, Tepla Monastery, Czech Republic, June 21-24, 2011.], in the present paper we show that not all graphs of vertex degree at most 4 are word-representable. Combining this result with some previously known facts, we derive that the number of n-vertex word-representable graphs is 2n23+o(n2).
graph-theory  enumeration  combinatorics  representation  to-understand  to-write-about  to-simulate 
29 days ago
[1503.08002] Word-representability of subdivisions of triangular grid graphs
A graph G=(V,E) is word-representable if there exists a word w over the alphabet V such that letters x and y alternate in w if and only if (x,y)∈E. A triangular grid graph is a subgraph of a tiling of the plane with equilateral triangles defined by a finite number of triangles, called cells. A subdivision of a triangular grid graph is replacing some of its cells by plane copies of the complete graph K4.
Inspired by a recent elegant result of Akrobotu et al., who classified word-representable triangulations of grid graphs related to convex polyominoes, we characterize word-representable subdivisions of triangular grid graphs. A key role in the characterization is played by smart orientations introduced by us in this paper. As a corollary to our main result, we obtain that any subdivision of boundary triangles in the Sierpiński gasket graph is word-representable.
graph-theory  feature-construction  formal-languages  rather-interesting  to-simulate  to-animate  to-write-about 
29 days ago
[1512.02356] Approximation algorithms for the two-center problem of convex polygon
iven a convex polygon P with n vertices, the two-center problem is to find two congruent closed disks of minimum radius such that they completely cover P. We propose an algorithm for this problem in the streaming setup, where the input stream is the vertices of the polygon in clockwise order. It produces a radius r satisfying r≤2ropt using O(1) space, where ropt is the optimum solution. Next, we show that in non-streaming setup, we can improve the approximation factor by r≤1.84ropt, maintaining the time complexity of the algorithm to O(n), and using O(1) extra space in addition to the space required for storing the input.
computational-geometry  online-algorithms  algorithms  rather-interesting  planning  approximation  to-simulate  to-write-about  consider:nonconvex 
4 weeks ago
[1606.08824] Towards Plane Spanners of Degree 3
Let S be a finite set of points in the plane that are in convex position. We present an algorithm that constructs a plane 3+4π3-spanner of S whose vertex degree is at most 3. Let Λ be the vertex set of a finite non-uniform rectangular lattice in the plane. We present an algorithm that constructs a plane 32‾√-spanner for Λ whose vertex degree is at most 3. For points that are in the plane and in general position, we show how to compute plane degree-3 spanners with a linear number of Steiner points.
computational-geometry  constraint-satisfaction  algorithms  computational-complexity  to-understand  to-write-about  to-simulate  geometric-graphs 
4 weeks ago
[1609.04148] Color Spanning Annulus: Square, Rectangle and Equilateral Triangle
In this paper, we study different variations of minimum width color-spanning annulus problem among a set of points P={p1,p2,…,pn} in IR2, where each point is assigned with a color in {1,2,…,k}. We present algorithms for finding a minimum width color-spanning axis parallel square annulus (CSSA), minimum width color spanning axis parallel rectangular annulus (CSRA), and minimum width color-spanning equilateral triangular annulus of fixed orientation (CSETA). The time complexities of computing (i) a CSSA is O(n3+n2klogk) which is an improvement by a factor n over the existing result on this problem, (ii) that for a CSRA is O(n4logn), and for (iii) a CSETA is O(n3k). The space complexity of all the algorithms is O(k).
constraint-satisfaction  optimization  operations-research  computational-geometry  algorithms  rather-interesting  to-simulate  to-write-about  consider:edge-cases 
4 weeks ago
[1610.06457] Matchings in Geometric Graphs
A geometric graph is a graph whose vertex set is a set of points in the plane and whose edge set contains straight-line segments. A matching in a graph is a subset of edges of the graph with no shared vertices. A matching is called perfect if it matches all the vertices of the underling graph. A geometric matching is a matching in a geometric graph. In this thesis, we study matching problems in various geometric graphs. Among the family of geometric graphs we look at complete graphs, complete bipartite graphs, complete multipartite graphs, Delaunay graphs, Gabriel graphs, and Θ-graphs. The classical matching problem is to find a matching of maximum size in a given graph. We study this problem as well as some of its variants on geometric graphs. The bottleneck matching problem is to find a maximum matching that minimizes the length of the longest edge. The plane matching problem is to find a maximum matching so that the edges in the matching are pairwise non-crossing. A geometric matching is strong with respect to a given shape S if we can assign to each edge in the matching a scaled version of S such that the shapes representing the edges are pairwise disjoint. The strong matching problem is to find a maximum strong matching with respect to a given shape. The matching packing problem is to pack as many edge-disjoint perfect matchings as possible into a geometric graph. We study these problems and establish lower and upper bounds on the size of different kinds of matchings in various geometric graphs. We also present algorithms for computing such matchings. Some of the presented bounds are tight, while the others need to be sharpened.
thesis  computational-geometry  graph-theory  geometric-graphs  rather-interesting  to-simulate  to-write-about  consider:generalizations  consider:approximation 
5 weeks ago
[1610.08407] On the Exact Amount of Missing Information that makes Finding Possible Winners Hard
We consider election scenarios with incomplete information, a situation that arises often in practice. There are several models of incomplete information and accordingly, different notions of outcomes of such elections. In one well-studied model of incompleteness, the votes are given by partial orders over the candidates. In this context we can frame the problem of finding a possible winner, which involves determining whether a given candidate wins in at least one completion of a given set of partial votes for a specific voting rule.
The possible winner problem is well-known to be NP-complete in general, and it is in fact known to be NP-complete for several voting rules where the number of undetermined pairs in every vote is bounded only by some constant. In this paper, we address the question of determining precisely the smallest number of undetermined pairs for which the possible winner problem remains NP-complete. In particular, we find the exact values of t for which the possible winner problem transitions to being NP-complete from being in P, where t is the maximum number of undetermined pairs in every vote. We demonstrate tight results for a broad subclass of scoring rules which includes all the commonly used scoring rules (such as plurality, veto, Borda, k-approval, and so on), Copelandα for every α∈[0,1], maximin, and Bucklin voting rules. A somewhat surprising aspect of our results is that for many of these rules, the possible winner problem turns out to be hard even if every vote has at most one undetermined pair of candidates.
game-theory  voting  rather-interesting  information-theory  constraint-satisfaction  algorithms  uncertainty  to-simulate  to-write-about  consider:variability  consider:feature-discovery  consider:heuristics 
5 weeks ago
[1705.09346] Range Assignment of Base-Stations Maximizing Coverage Area without Interference
We study the problem of assigning non-overlapping geometric objects centered at a given set of points such that the sum of area covered by them is maximized. If the points are placed on a straight-line and the objects are disks, then the problem is solvable in polynomial time. However, we show that the problem is NP-hard even for simplest objects like disks or squares in ℝ2. Eppstein [CCCG, pages 260--265, 2016] proposed a polynomial time algorithm for maximizing the sum of radii (or perimeter) of non-overlapping balls or disks when the points are arbitrarily placed on a plane. We show that Eppstein's algorithm for maximizing sum of perimeter of the disks in ℝ2 gives a 2-approximation solution for the sum of area maximization problem. We propose a PTAS for our problem. These approximation results are extendible to higher dimensions. All these approximation results hold for the area maximization problem by regular convex polygons with even number of edges centered at the given points.
packing  covering  rather-interesting  computational-geometry  computational-complexity  to-write-about  to-simulate  algorithms  consider:performance-measures  consider:feature-discovery 
5 weeks ago
[1711.10227] On Structural Parameterizations of Firefighting
The Firefighting problem is defined as follows. At time t=0, a fire breaks out at a vertex of a graph. At each time step t≥0, a firefighter permanently defends (protects) an unburned vertex, and the fire then spread to all undefended neighbors from the vertices on fire. This process stops when the fire cannot spread anymore. The goal is to find a sequence of vertices for the firefighter that maximizes the number of saved (non burned) vertices.
The Firefighting problem turns out to be NP-hard even when restricted to bipartite graphs or trees of maximum degree three. We study the parameterized complexity of the Firefighting problem for various structural parameterizations. All our parameters measure the distance to a graph class (in terms of vertex deletion) on which the firefighting problem admits a polynomial time algorithm. Specifically, for a graph class  and a graph G, a vertex subset S is called a modulator to  if G∖S belongs to . The parameters we consider are the sizes of modulators to graph classes such as threshold graphs, bounded diameter graphs, disjoint unions of stars, and split graphs.
To begin with, we show that the problem is W[1]-hard when parameterized by the size of a modulator to diameter at most two graphs and split graphs. In contrast to the above intractability results, we show that Firefighting is fixed parameter tractable (FPT) when parameterized by the size of a modulator to threshold graphs and disjoint unions of stars, which are subclasses of diameter at most two graphs. We further investigate the kernelization complexity of these problems to find that firefighting admits a polynomial kernel when parameterized by the size of a modulator to a clique, while it is unlikely to admit a polynomial kernel when parameterized by the size of a modulator to a disjoint union of stars.
graph-theory  game-theory  algorithms  rather-interesting  to-write-about  to-simulate  computational-complexity  feature-construction  consider:geometric-graphs 
5 weeks ago
[1801.08565] Rollercoasters and Caterpillars
A rollercoaster is a sequence of real numbers for which every maximal contiguous subsequence, that is increasing or decreasing, has length at least three. By translating this sequence to a set of points in the plane, a rollercoaster can be defined as a polygonal path for which every maximal sub-path, with positive- or negative-slope edges, has at least three points. Given a sequence of distinct real numbers, the rollercoaster problem asks for a maximum-length subsequence that is a rollercoaster. It was conjectured that every sequence of n distinct real numbers contains a rollercoaster of length at least ⌈n/2⌉ for n>7, while the best known lower bound is Ω(n/logn). In this paper we prove this conjecture. Our proof is constructive and implies a linear-time algorithm for computing a rollercoaster of this length. Extending the O(nlogn)-time algorithm for computing a longest increasing subsequence, we show how to compute a maximum-length rollercoaster within the same time bound. A maximum-length rollercoaster in a permutation of {1,…,n} can be computed in O(nloglogn) time.
The search for rollercoasters was motivated by orthogeodesic point-set embedding of caterpillars. A caterpillar is a tree such that deleting the leaves gives a path, called the spine. A top-view caterpillar is one of degree 4 such that the two leaves adjacent to each vertex lie on opposite sides of the spine. As an application of our result on rollercoasters, we are able to find a planar drawing of every n-node top-view caterpillar on every set of 253n points in the plane, such that each edge is an orthogonal path with one bend. This improves the previous best known upper bound on the number of required points, which is O(nlogn). We also show that such a drawing can be obtained in linear time, provided that the points are given in sorted order.
computational-complexity  computational-geometry  algorithms  permutations  rather-interesting  to-write-about  to-simulate  consider:looking-to-see  nudge-targets  consider:representation  search-algorithms 
5 weeks ago
[1802.09505] Faster Algorithms for some Optimization Problems on Collinear Points
We propose faster algorithms for the following three optimization problems on n collinear points, i.e., points in dimension one. The first two problems are known to be NP-hard in higher dimensions.
1- Maximizing total area of disjoint disks: In this problem the goal is to maximize the total area of nonoverlapping disks centered at the points. Acharyya, De, and Nandy (2017) presented an O(n2)-time algorithm for this problem. We present an optimal Θ(n)-time algorithm.
2- Minimizing sum of the radii of client-server coverage: The n points are partitioned into two sets, namely clients and servers. The goal is to minimize the sum of the radii of disks centered at servers such that every client is in some disk, i.e., in the coverage range of some server. Lev-Tov and Peleg (2005) presented an O(n3)-time algorithm for this problem. We present an O(n2)-time algorithm, thereby improving the running time by a factor of Θ(n).
3- Minimizing total area of point-interval coverage: The n input points belong to an interval I. The goal is to find a set of n disks of minimum total area, covering I, such that every disk contains at least one input point. We present an algorithm that solves this problem in O(n2) time.
computational-complexity  computational-geometry  rather-interesting  algorithms  nudge-targets  operations-research  optimization  combinatorics  constraint-satisfaction 
5 weeks ago
Debugging distributed systems with why-across-time provenance – the morning paper
This value is 17 here, and it shouldn’t be. Why did the get request return 17?

Sometimes the simplest questions can be the hardest to answer. As the opening sentence of this paper states:

Debugging distributed systems is hard.

The kind of why questions we’re interested in for this paper are questions of provenance. What are the causes of this output? Provenance has been studied in the context of relational databases and dataflow systems, but here we’re interested in general distributed systems. (Strictly, those where the behaviour of each node can be modelled by a deterministic state machine: non-deterministic behaviour is left to future work).
distributed-processing  WAT-provenance  wtf-functions  rather-interesting  to-understand  to-do  consider:Push  consider:ReQ  debugging  software-development-is-not-programming 
5 weeks ago
Instant Pot® Shredded Flank Steak Recipe -
"A great way to make a tough cut of beef flank tender and flavorful using an Instant Pot®. Serve it over crusty buns or mashed potatoes; either way, enjoy!"
have-made  recipes  Instant-Pot  rather-good  "cheap-cuts"-ain't-cheap-tho 
5 weeks ago
rbenv/rbenv: Groom your app’s Ruby environment
Use rbenv to pick a Ruby version for your application and guarantee that your development environment matches production. Put rbenv to work with Bundler for painless Ruby upgrades and bulletproof deployments.
do-use  Ruby  dev-setup  software-development-is-not-programming  for-reference 
5 weeks ago
Emergent Tool Use from Multi-Agent Interaction
We’ve observed agents discovering progressively more complex tool use while playing a simple game of hide-and-seek. Through training in our new simulated hide-and-seek environment, agents build a series of six distinct strategies and counterstrategies, some of which we did not know our environment supported. The self-supervised emergent complexity in this simple environment further suggests that multi-agent co-adaptation may one day produce extremely complex and intelligent behavior.
agent-based  artificial-life  machine-learning  collective-behavior  looking-to-see  rather-interesting  to-write-about  to-simulate  consider:a-sufficiently-complex-environment 
6 weeks ago
Hugging Face GPT With Clojure - Squid's Blog
You can now interop with ANY python library.

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

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

Right now, that library is Hugging Face Transformers.

Get ready. We will wrap that sweet hugging face code in Clojure parens!
machine-learning  Clojure  interop  natural-language-processing  rather-interesting  library  to-understand  to-follow-along  to-write-about  consider:scraping-for-data 
6 weeks ago
Integrating Deep Learning With clojure.spec - Squid's Blog
clojure.spec allows you to write specifications for data and use them for validation. It also provides a generative aspect that allows for robust testing as well as an additional way to understand your data through manual inspection. The dual nature of validation and generation is a natural fit for deep learning models that consist of paired discriminator/generator models.
Clojure  clojure.spec  machine-learning  to-understand  to-do  consider:representation  consider:structural-types 
6 weeks ago
Accelerate | Apple Developer Documentation
Make large-scale mathematical computations and image calculations, optimized for high performance and low-energy consumption.
swift  library  to-understand  image-processing  GPU  programming 
6 weeks ago
The King vs. Pawn Game of UI Design – A List Apart
If you want to improve your UI design skills, have you tried looking at chess? I know it sounds contrived, but hear me out. I’m going to take a concept from chess and use it to build a toolkit of UI design strategies. By the end, we’ll have covered color, typography, lighting and shadows, and more.
graphic-design  the-mangle-in-practice  pedagogy  rather-good  isolation-of-concepts  to-write-about  consider:testing  consider:unit-tests-as-lessons  consider:Oulipo 
6 weeks ago
Regularization Improves the Robustness of Learned Sequence-to-Expression Models | bioRxiv
Understanding of the gene regulatory activity of enhancers is a major problem in regulatory biology. The nascent field of sequence-to-expression modelling seeks to create quantitative models of gene expression based on regulatory DNA (cis) and cellular environmental (trans) contexts. All quantitative models are defined partially by numerical parameters, and it is common to fit these parameters to data provided by existing experimental results. However, the relative paucity of experimental data appropriate for this task, and lacunae in our knowledge of all components of the systems, results in problems often being under-specified, which in turn may lead to a situation where wildly different model parameterizations perform similarly well on training data. It may also lead to models being fit to the idiosyncrasies of the training data, without representing the more general process (overfitting).

In other contexts where parameter-fitting is performed, it is common to apply regularization to reduce overfitting. We systematically evaluated the efficacy of three types of regularization in improving the generalizability of trained sequence-to-expression models. The evaluation was performed in two types of cross-validation experiments: one training on D. melanogaster data and predicting on orthologous enhancers from related species, and the other cross-validating between four D. melanogaster neurogenic ectoderm enhancers, which are thought to be under control of the same transcription factors. We show that training with a combination of noise-injection, L1, and L2 regularization can drastically reduce overfitting and improve the generalizability of learned sequence-to-expression models. These results suggest that it may be possible to mitigate the tendency of sequence-to-expression models to overfit available data, thus improving predictive power and potentially resulting in models that provide better insight into underlying biological processes.
bioinformatics  systems-biology  nonlinear-dynamics  machine-learning  regularization  statistics  numerical-methods  heuristics  to-write-about  to-simulate  consider:symbolic-regression  consider:robustness 
6 weeks ago
What Proof Is Best? |
A great illustration of this “Let a hundred proofs bloom” point of view is provided by an article by Stan Wagon called “Fourteen Proofs of a Result About Tiling a Rectangle”. Here’s the result his title refers to (a puzzle posed and solved by Nicolaas de Bruijn): Whenever a rectangle can be cut up into smaller rectangles each of which has at least one integer side, then the big rectangle has at least one integer side too. (Here “at least one integer side” is tantamount to “at least two integer sides”, since the opposite sides of a rectangle always have the same length.)
mathematics  philosophy  solution-spaces  diversity  proof  to-write-about  to-simulate  consider:surprise 
6 weeks ago
Specify a secondary axis — sec_axis • ggplot2
This function is used in conjunction with a position scale to create a secondary axis, positioned opposite of the primary axis. All secondary axes must be based on a one-to-one transformation of the primary axes.
R  dataviz  ggplot2  secondary-x-axis  tricks 
6 weeks ago
[1710.04554] Lattice point visibility on generalized lines of sight
For a fixed b∈ℕ={1,2,3,…} we say that a point (r,s) in the integer lattice ℤ×ℤ is b-visible from the origin if it lies on the graph of a power function f(x)=axb with a∈ℚ and no other integer lattice point lies on this curve (i.e., line of sight) between (0,0) and (r,s). We prove that the proportion of b-visible integer lattice points is given by 1/ζ(b+1), where ζ(s) denotes the Riemann zeta function. We also show that even though the proportion of b-visible lattice points approaches 1 as b approaches infinity, there exist arbitrarily large rectangular arrays of b-invisible lattice points for any fixed b. This work specialized to b=1 recovers original results from the classical lattice point visibility setting where the lines of sight are given by linear functions with rational slope through the origin.
number-theory  have-considered  rather-interesting  to-write-about  to-simulate  consider:visualization  consider:agents-who-see-this-way 
7 weeks ago
[1807.06414] Combining a Context Aware Neural Network with a Denoising Autoencoder for Measuring String Similarities
Measuring similarities between strings is central for many established and fast growing research areas including information retrieval, biology, and natural language processing. The traditional approach for string similarity measurements is to define a metric over a word space that quantifies and sums up the differences between characters in two strings. The state-of-the-art in the area has, surprisingly, not evolved much during the last few decades. The majority of the metrics are based on a simple comparison between character and character distributions without consideration for the context of the words. This paper proposes a string metric that encompasses similarities between strings based on (1) the character similarities between the words including. Non-Standard and standard spellings of the same words, and (2) the context of the words. Our proposal is a neural network composed of a denoising autoencoder and what we call a context encoder specifically designed to find similarities between the words based on their context. The experimental results show that the resulting metrics succeeds in 85.4\% of the cases in finding the correct version of a non-standard spelling among the closest words, compared to 63.2\% with the established Normalised-Levenshtein distance. Besides, we show that words used in similar context are with our approach calculated to be similar than words with different contexts, which is a desirable property missing in established string metrics.
feature-construction  machine-learning  clustering  natural-language-processing  rather-interesting  to-simulate  to-write-about  consider:feature-discovery 
7 weeks ago
[1812.08434] Graph Neural Networks: A Review of Methods and Applications
Lots of learning tasks require dealing with graph data which contains rich relation information among elements. Modeling physics system, learning molecular fingerprints, predicting protein interface, and classifying diseases require a model to learn from graph inputs. In other domains such as learning from non-structural data like texts and images, reasoning on extracted structures, like the dependency tree of sentences and the scene graph of images, is an important research topic which also needs graph reasoning models. Graph neural networks (GNNs) are connectionist models that capture the dependence of graphs via message passing between the nodes of graphs. Unlike standard neural networks, graph neural networks retain a state that can represent information from its neighborhood with arbitrary depth. Although the primitive GNNs have been found difficult to train for a fixed point, recent advances in network architectures, optimization techniques, and parallel computation have enabled successful learning with them. In recent years, systems based on variants of graph neural networks such as graph convolutional network (GCN), graph attention network (GAT), gated graph neural network (GGNN) have demonstrated ground-breaking performance on many tasks mentioned above. In this survey, we provide a detailed review over existing graph neural network models, systematically categorize the applications, and propose four open problems for future research.
machine-learning  representation  review  rather-interesting  to-write-about  to-simulate  consider:genetic-programming  consider:functional-transformations 
7 weeks ago
[1809.02836] Context-Free Transductions with Neural Stacks
This paper analyzes the behavior of stack-augmented recurrent neural network (RNN) models. Due to the architectural similarity between stack RNNs and pushdown transducers, we train stack RNN models on a number of tasks, including string reversal, context-free language modelling, and cumulative XOR evaluation. Examining the behavior of our networks, we show that stack-augmented RNNs can discover intuitive stack-based strategies for solving our tasks. However, stack RNNs are more difficult to train than classical architectures such as LSTMs. Rather than employ stack-based strategies, more complex networks often find approximate solutions by using the stack as unstructured memory.
neural-networks  artificial-life  representation  time-series  automata  to-write-about  to-simulate  unconventional-computing 
7 weeks ago
[1906.01615] Sequential Neural Networks as Automata
This work attempts to explain the types of computation that neural networks can perform by relating them to automata. We first define what it means for a real-time network with bounded precision to accept a language. A measure of network memory follows from this definition. We then characterize the classes of languages acceptable by various recurrent networks, attention, and convolutional networks. We find that LSTMs function like counter machines and relate convolutional networks to the subregular hierarchy. Overall, this work attempts to increase our understanding and ability to interpret neural networks through the lens of theory. These theoretical insights help explain neural computation, as well as the relationship between neural networks and natural language grammar.
neural-networks  rather-interesting  update-dynamics  representation  via:cshalizi  to-read  to-write-about  to-simulate  automata  unconventional-computation  but-is-it-really? 
7 weeks ago
Does art compute? – Symptoms Of The Universe
As Cory Simon explains so well in his “Voronoi cookies and the post office problem” post, the Voronoi algorithm is an easy-to-understand method in computational geometry, especially in two dimensions: take a point, join it up to its nearest neighbours, and get the perpendicular bisectors of those lines. The intersections of the bisectors define a Voronoi cell. If the points form an ordered mesh on the plane — as, for example, in the context of the atoms on a crystal plane in solid state physics — then the Voronoi cell is called a Wigner-Seitz unit cell. (As an undergrad, I didn’t realise that the Wigner-Seitz unit cells I studied in my solid state lectures were part of the much broader Voronoi class — another example of limiting thinking due to disciplinary boundaries.)
unconventional-computing  generative-art  interdisciplinary  artificial-life  heavily-linked  to-walk-from 
7 weeks ago
High-dimensional Time Series Clustering via Cross-Predictability
The key to time series clustering is how to characterize the similarity between any two time series. In this paper, we explore a new similarity metric called “cross-predictability”: the degree to which a future value in each time series is predicted by past values of the others. However, it is challenging to estimate such cross-predictability among time series in the high-dimensional regime, where the number of time series is much larger than the length of each time series. We address this challenge with a sparsity assumption: only time series in the same cluster have significant cross-predictability with each other. We demonstrate that this approach is computationally attractive, and provide a theoretical proof that the proposed algorithm will identify the correct clustering structure with high probability under certain conditions. To the best of our knowledge, this is the first practical high-dimensional time series clustering algorithm with a provable guarantee. We evaluate with experiments on both synthetic data and real-world data, and results indicate that our method can achieve more than 80% clustering accuracy on real-world data, which is 20% higher than the state-of-art baselines.
performance-networks  clustering  time-series  yeah-I-probably-shoulda-published-in-1999  machine-learning  feature-construction  ah-well 
7 weeks ago
Modeling Minds
Embodied Cognition (EC) is an approach in cognitive science that distinguishes itself from more traditional approaches (such as the computational view on cognition) by both a set of commitments on what cognition is and a set of ideas on how it should be studied and what kind of explanations of cognition are acceptable. While pluralism in science can be beneficial, the breadth and depth of the differences between embodied and non-embodied approaches results in two distinct bodies of research that cannot be easily compared and evaluated side by side. Being still a minority view, the losing side of such a situation is EC.
In this workshop, we focus on the different explanatory methodologies in cognitive science specifically in relation to explaining social cognition. We will examine different ways of conceptualizing the explanatory target phenomena in the social domain and different ways of framing explanations thereof, such as the focus on the social experience, the autonomy of the supra-personal level of explanation or the interdependence between social activity and the embedding of cognitive systems in their shared physical environment.
cognition  extended-cognition  rather-interesting  conference  to-read  to-watch-for-papers 
7 weeks ago
Puzzle 864. 10958, the only hole...
Brazilian mathematician Inder J. Taneja has found (Jan 2014) a way to render every number from 1 to 11,111 by starting with either of these ordered strings.

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

applying any of the following:

a) arithmetical operations permitted: addition, subtraction, multiplication, division, and exponentiation.
b) string operation permitted: concatenation.
c) auxiliary symbols permitted: brackets "(" and ")".
puzzles  mathematical-recreations  arithmetic  constraint-satisfaction  to-write-about  nudge-targets  consider:looking-to-see  to-simulate  consider:generalizations 
7 weeks ago
The Stanford Natural Language Processing Group
Tregex is a utility for matching patterns in trees, based on tree relationships and regular expression matches on nodes (the name is short for "tree regular expressions"). Tregex comes with Tsurgeon, a tree transformation language. Also included from version 2.0 on is a similar package which operates on dependency graphs (class SemanticGraph, called semgrex.
pattern-matching  library  software-development  algorithms  rather-interesting  consider:in-gp-apps  consider:classification  to-understand  to-complain-about-docs  data-structures 
7 weeks ago
Robustness of the two-sample t-test
It is fairly well known that the t-test is robust to departures from a normal distribution, as long as the actual distribution is symmetric. That is, the test works more or less as advertised as long as the distribution is symmetric like a normal distribution, but it may not work as expected if the distribution is asymmetric.

This post will explore the robustness of the t-test via simulation. How far can you be from a normal distribution and still do OK? Can you have any distribution as long as it’s symmetric? Does a little asymmetry ruin everything? If something does go wrong, how does it go wrong?
statistics  looking-to-see  rather-interesting  algorithms  robustness  to-do  to-write-about  consider:animation 
7 weeks ago
Running Cargo - Futility Closet
This passage is from Rudyard Kipling’s 1910 story “Brother Square-Toes.” What’s notable about the bolded section?
feature-construction  rather-interesting  digital-humanities  to-write-about  consider:looking-to-see 
7 weeks ago
asciinema - Record and share your terminal sessions, the right way
asciinema [as-kee-nuh-muh] is a free and open source solution for recording terminal sessions and sharing them on the web. Read about how it works.
collaboration  screencasting  rather-interesting  software  open-source  to-understand  to-try 
7 weeks ago
[PDF] Extended circularity: a new puzzle for extended cognition | Semantic Scholar
Mainstream epistemology has typically taken for granted a traditional picture of the metaphysics of mind, according to which cognitive processes (e.g. memory storage and retrieval) play out entirely within the bounds of the skull and skin. But this simple ‘intracranial’ picture is falling in- creasingly out of step with contemporary thinking in the philosophy of mind and cognitive science. Likewise, though, proponents of active exter- nalist approaches to the mind—e.g. the hypothesis of extended cognitition (HEC)—have proceeded by and large without asking what epistemological ramifications should arise once cognition is understood as criss-crossing the bounds of brain and world. This paper aims to motivate a puzzle that arises only once these two strands of thinking are brought in contact with one another. In particular, we want to first highlight a kind of con- dition of epistemological adequacy that should be accepted by proponents of extended cognition; once this condition is motivated, the remainder of the paper demonstrates how attempts to satisfy this condition seem to inevitably devolve into a novel kind of epistemic circularity. At the end of the day, proponents of extended cognition have a novel epistemological puzzle on their hands.
the-mangle-in-practice  psychology  cognition  individuation  philosophy-of-mind  to-write-about  consider:not-worrying-about-it 
7 weeks ago
[1305.1958] The Dynamically Extended Mind -- A Minimal Modeling Case Study
The extended mind hypothesis has stimulated much interest in cognitive science. However, its core claim, i.e. that the process of cognition can extend beyond the brain via the body and into the environment, has been heavily criticized. A prominent critique of this claim holds that when some part of the world is coupled to a cognitive system this does not necessarily entail that the part is also constitutive of that cognitive system. This critique is known as the "coupling-constitution fallacy". In this paper we respond to this reductionist challenge by using an evolutionary robotics approach to create a minimal model of two acoustically coupled agents. We demonstrate how the interaction process as a whole has properties that cannot be reduced to the contributions of the isolated agents. We also show that the neural dynamics of the coupled agents has formal properties that are inherently impossible for those neural networks in isolation. By keeping the complexity of the model to an absolute minimum, we are able to illustrate how the coupling-constitution fallacy is in fact based on an inadequate understanding of the constitutive role of nonlinear interactions in dynamical systems theory.
the-mangle-in-practice  rather-interesting  philosophy  philosophy-of-science  to-write-about  to-wander-its-citations 
7 weeks ago
The Stanford Literary Lab’s Narrative | Public Books
Experiment is presented here not just as a test of reliable knowledge but as a style of intellectual growth: “By frustrating our expectations, failed experiments ‘estrange’ our natural habits of thought, offering a chance to transcend them.” At moments, the point of experiment seems to become entirely aesthetic. In the book’s introduction, Moretti admits that he set out to write “a scientific essay, composed like a Mahler symphony: discordant registers that barely manage to coexist; a forward movement endlessly diverted; the easiest of melodies, followed by leaps into the unknown.”
This account of the book’s aesthetic achievement is candid, immodest, and accurate. The essays within are unified by a deliberately wandering structure, which keeps its distance both from scientists’ predictable sequences (methods → results → conclusions), and from the thesis-driven template that prevails in the humanities (counter-intuitive claim → evidence → I was right after all). Instead, these essays become stories of progressive disorientation, written in the first-person plural, and arriving at theses that were only dimly foreshadowed.
digital-humanities  literary-criticism  rather-interesting  this-quote  to-write-about  consider:the-creative-system 
7 weeks ago
RNA design algorithm takes an RNA secondary structure description as input and then try to identify an RNA strand that folds into this function-specific target structure. With new advances in biotechnology and synthetic biology, a reliable RNA design algorithm can be crucial steps to create new biochemical components. Our lab is interested in employing various computational intelligence techniques to propose the new paradigm to help with the RNA design problem. Recently, we have designed an algorithm SIMARD, which is based on the simulated annealing paradigm.
structural-biology  polymer-folding  biochemistry  biophysics  simulation  metaheuristics  energy-landscapes  rather-interesting  to-write-about  to-simulate  to-visualize 
8 weeks ago
Short How-To guides — GROMACS 2019 documentation
A number of short guides are presented here to help users getting started with simulations. More detailed tutorials are available for example at the
structural-biology  simulation  software  open-source  rather-interesting  to-simulate  to-write-about  consider:looking-to-see 
8 weeks ago
[1902.07277] A systematic classification of knotoids on the plane and on the sphere
In this paper we generate and systematically classify all prime planar knotoids with up to 5 crossings. We also extend the existing list of knotoids in S2 and add all knotoids with 6 crossings.
knot-theory  combinatorics  enumeration  rather-interesting  stamp-collecting  to-understand  to-write-about  to-simulate  consider:classification  consider:representation 
8 weeks ago
[1803.07114] Slipknotting in Random Diagrams
The presence of slipknots in configurations of proteins and DNA has been shown to affect their functionality, or alter it entirely. Historically, polymers are modeled as polygonal chains in space. As an alternative to space curves, we provide a framework for working with subknots inside of knot diagrams via knotoid diagrams. We prove using a pattern theorem for knot diagrams that not only are almost all knot diagrams slipknotted, almost all unknot diagrams are slipknotted. This proves in the random diagram model a conjecture yet unproven in random space curve models. We also discuss conjectures on the enumeration of knotoid diagrams.
knot-theory  combinatorics  sampling  random-walks  structural-biology  rather-interesting  theoretical-biology  to-simulate  to-write-about  consider:representation 
8 weeks ago
[1810.07970] Inglenook Shunting Puzzles
An inglenook puzzle is a classic shunting (switching) puzzle often found on model railway layouts. A collection of wagons sits in a fan of sidings with a limited length headshunt (lead track). The aim of the puzzle is to rearrange the wagons into a desired order (often a randomly chosen order). This article answers the question: When can you be sure this can always be done? The problem of finding a solution in a minimum number of moves is also addressed.
puzzles  mathematical-recreations  combinatorics  rather-interesting  to-write-about  to-simulate  consider:genetic-programming  consider:data-structures 
8 weeks ago
[1011.4034] Dense packing crystal structures of physical tetrahedra
We present a method for discovering dense packings of general convex hard particles and apply it to study the dense packing behavior of a one-parameter family of particles with tetrahedral symmetry representing a deformation of the ideal mathematical tetrahedron into a less ideal, physical, tetrahedron and all the way to the sphere. Thus, we also connect the two well studied problems of sphere packing and tetrahedron packing on a single axis. Our numerical results uncover a rich optimal-packing behavior, compared to that of other continuous families of particles previously studied. We present four structures as candidates for the optimal packing at different values of the parameter, providing an atlas of crystal structures which might be observed in systems of nano-particles with tetrahedral symmetry.
packing  granular-materials  optimization  geometry  rather-interesting  to-simulate  consider:looking-to-see  consider:particle-sims 
8 weeks ago
[1803.09607] Murder at the Asylum
I describe a puzzle I wrote for the 2018 MIT Mystery Hunt which introduced new types of people in logic puzzles. I discuss the puzzle itself, the solution, and the mathematics behind it.
puzzles  logic  mathematical-recreations  rather-good  constraint-satisfaction  to-write-about  to-simulate  consider:sampling 
8 weeks ago
« earlier      
per page:    204080120160

Copy this bookmark:

to read