**Vaguery + to-write-about**
1396

[1904.01681] Augmented Neural ODEs

yesterday by Vaguery

We show that Neural Ordinary Differential Equations (ODEs) learn representations that preserve the topology of the input space and prove that this implies the existence of functions Neural ODEs cannot represent. To address these limitations, we introduce Augmented Neural ODEs which, in addition to being more expressive models, are empirically more stable, generalize better and have a lower computational cost than Neural ODEs.

neural-networks
machine-learning
representation
rather-interesting
generalization
numerical-methods
to-write-about
consider:genetic-programming
yesterday by Vaguery

[1904.01175] DeepLight: Learning Illumination for Unconstrained Mobile Mixed Reality

yesterday by Vaguery

We present a learning-based method to infer plausible high dynamic range (HDR), omnidirectional illumination given an unconstrained, low dynamic range (LDR) image from a mobile phone camera with a limited field of view (FOV). For training data, we collect videos of various reflective spheres placed within the camera's FOV, leaving most of the background unoccluded, leveraging that materials with diverse reflectance functions reveal different lighting cues in a single exposure. We train a deep neural network to regress from the LDR background image to HDR lighting by matching the LDR ground truth sphere images to those rendered with the predicted illumination using image-based relighting, which is differentiable. Our inference runs at interactive frame rates on a mobile device, enabling realistic rendering of virtual objects into real scenes for mobile mixed reality. Training on automatically exposed and white-balanced videos, we improve the realism of rendered objects compared to the state-of-the art methods for both indoor and outdoor scenes.

augmented-reality
deep-learning
image-processing
data-fusion
rather-interesting
generative-models
generative-art
algorithms
to-write-about
consider:performance-measures
yesterday by Vaguery

Lychrel number - Wikipedia

yesterday by Vaguery

A Lychrel number is a natural number that cannot form a palindrome through the iterative process of repeatedly reversing its digits and adding the resulting numbers. This process is sometimes called the 196-algorithm, after the most famous number associated with the process. In base ten, no Lychrel numbers have been yet proved to exist, but many, including 196, are suspected on heuristic[1] and statistical grounds. The name "Lychrel" was coined by Wade Van Landingham as a rough anagram of Cheryl, his girlfriend's first name.[2]

number-theory
mathematical-recreations
palindromes
rather-interesting
to-write-about
yesterday by Vaguery

Today I learned about Lychrel numbers. A Lychrel number is a natural number that cannot form a palindrome through the iterative process of repeatedly reversing its digits and adding the resulting numbers. For example 57+75 = 132, 132+231 = 363, a palindro

yesterday by Vaguery

Today I learned about Lychrel numbers. A Lychrel number is a natural number that cannot form a palindrome through the iterative process of repeatedly reversing its digits and adding the resulting numbers. For example 57+75 = 132, 132+231 = 363, a palindrome. There is no known sequence for 196

number-theory
mathematical-recreations
rather-interesting
to-write-about
yesterday by Vaguery

Solve a Very Old Problem | wild.maths.org

12 days ago by Vaguery

But we can trisect an angle if we use a different set of tools. Euclid’s axioms aren’t the only ones that describe what you can do on a flat piece of paper: we also have the axioms of origami. And it turns out that folding paper with one single flat fold at a time is more powerful than using a straight edge and compass.

mathematical-recreations
impossible-problems
origami
rather-interesting
out-of-the-box
tools
define-your-terms
to-write-about
consider:discovering-tools
consider:operator-algorithm-coevolution
nudge-targets
12 days ago by Vaguery

[1901.06758] A deep learning approach to real-time parking occupancy prediction in spatio-temporal networks incorporating multiple spatio-temporal data sources

12 days ago by Vaguery

A deep learning model is applied for predicting block-level parking occupancy in real time. The model leverages Graph-Convolutional Neural Networks (GCNN) to extract the spatial relations of traffic flow in large-scale networks, and utilizes Recurrent Neural Networks (RNN) with Long-Short Term Memory (LSTM) to capture the temporal features. In addition, the model is capable of taking multiple heterogeneously structured traffic data sources as input, such as parking meter transactions, traffic speed, and weather conditions. The model performance is evaluated through a case study in Pittsburgh downtown area. The proposed model outperforms other baseline methods including multi-layer LSTM and Lasso with an average testing MAPE of 10.6\% when predicting block-level parking occupancies 30 minutes in advance. The case study also shows that, in generally, the prediction model works better for business areas than for recreational locations. We found that incorporating traffic speed and weather information can significantly improve the prediction performance. Weather data is particularly useful for improving predicting accuracy in recreational areas.

machine-learning
city-planning
data-analysis
looking-to-see
prediction
deep-learning
to-write-about
consider:data-sourcing
12 days ago by Vaguery

[1807.03627] Modelling textile structures using bicontinuous surfaces

12 days ago by Vaguery

We present a method for modelling textile structures, such as weft knits, on families of bicontinuous surfaces. By developing a tangible interpretation of mathematical theory, we combine perspectives of art, design, engineering, and science to understand how the architecture of the knit relates to its physical and mathematical properties. While modelling and design tools have become ubiquitous in many industries, there is still a significant lack of predictive advanced manufacturing techniques available for the design and manufacture of textiles. We describe a mathematical structure as a system for dynamic modelling of textiles in the form of a physical prototype which may be used to inform and predict relevant textile parameters prior to fabrication. This includes dimensional changes due to yarn relaxation, which would streamline production of knit textiles for industry, makers and textile artists.

materials-science
models
rather-interesting
looking-to-see
textiles
origami
to-write-about
consider:simulation
12 days ago by Vaguery

[1107.2422] A Linear Time Algorithm for Seeds Computation

12 days ago by Vaguery

A seed in a word is a relaxed version of a period in which the occurrences of the repeating subword may overlap. We show a linear-time algorithm computing a linear-size representation of all the seeds of a word (the number of seeds might be quadratic). In particular, one can easily derive the shortest seed and the number of seeds from our representation. Thus, we solve an open problem stated in the survey by Smyth (2000) and improve upon a previous O(n log n) algorithm by Iliopoulos, Moore, and Park (1996). Our approach is based on combinatorial relations between seeds and subword complexity (used here for the first time in context of seeds). In the previous papers, the compact representation of seeds consisted of two independent parts operating on the suffix tree of the word and the suffix tree of the reverse of the word, respectively. Our second contribution is a simpler representation of all seeds which avoids dealing with the reversed word.

A preliminary version of this work, with a much more complex algorithm constructing the earlier representation of seeds, was presented at the 23rd Annual ACM-SIAM Symposium of Discrete Algorithms (SODA 2012).

strings
combinatorics
patterns
rather-interesting
algorithms
computational-complexity
nudge-targets
to-write-about
A preliminary version of this work, with a much more complex algorithm constructing the earlier representation of seeds, was presented at the 23rd Annual ACM-SIAM Symposium of Discrete Algorithms (SODA 2012).

12 days ago by Vaguery

[1811.01312] Adversarial Black-Box Attacks for Automatic Speech Recognition Systems Using Multi-Objective Genetic Optimization

12 days ago by Vaguery

Fooling deep neural networks with adversarial input have exposed a significant vulnerability in current state-of-the-art systems in multiple domains. Both black-box and white-box approaches have been used to either replicate the model itself or to craft examples which cause the model to fail. In this work, we use a multi-objective genetic algorithm based approach to perform both targeted and un-targeted black-box attacks on automatic speech recognition (ASR) systems. The main contribution of this research is the proposal of a generic framework which can be used to attack any ASR system, even if it's internal working is hidden.

During the un-targeted attacks, the Word Error Rates (WER) of the ASR degrades from 0.5 to 5.4, indicating the potency of our approach. In targeted attacks, our solution reaches a WER of 2.14. In both attacks, the adversarial samples maintain a high acoustic similarity of 0.98 and 0.97.

metaheuristics
adversarial-design
speech-recognition
algorithms
coevolution
evolutionary-algorithms
to-write-about
rather-interesting
During the un-targeted attacks, the Word Error Rates (WER) of the ASR degrades from 0.5 to 5.4, indicating the potency of our approach. In targeted attacks, our solution reaches a WER of 2.14. In both attacks, the adversarial samples maintain a high acoustic similarity of 0.98 and 0.97.

12 days ago by Vaguery

Ludus-Opuscula RMM

12 days ago by Vaguery

We investigate a type of a Sudoku variant called Sudo-Kurve, which allows bent rows and columns, and develop a new, yet equivalent, variant we call a Sudo-Cube. We examine the total number of distinct solution grids for this type with or without symmetry. We study other mathematical aspects of this puzzle along with the minimum number of clues needed and the number of ways to place individual symbols.

mathematical-recreations
puzzles
sudoku
out-of-the-box
to-write-about
to-read
12 days ago by Vaguery

Tanya Khovanova's Math Blog » Blog Archive » Cube Sudo-Kurve

12 days ago by Vaguery

We chose a particular shape of Sudo-Kurve for this project, which ended up being very rewarding. It is called Cube Sudo-Kurve. The Cube Sudo-Kurve consists of three square blocks. The gray bent lines indicate how rows and columns continue. For example, the first row of the top left block becomes the last column of the middle block and continues to the first row of the bottom right block. As usual each row, column, and square region has to have 9 distinct digits.

mathematical-recreations
puzzles
sudoku
out-of-the-box
creative-heuristics
to-write-about
nudge-targets
12 days ago by Vaguery

[1808.00626] Slender Origami with Complex 3D Folding Shapes

12 days ago by Vaguery

One-dimensional slender bodies can be deformed or shaped into spatially complex curves relatively easily due to their inherent compliance. However, traditional methods of fabricating complex spatial shapes are cumbersome, prone to error accumulation and not amenable to elegant programmability. In this letter, we introduce a one-dimensional origami based on attaching Miura-ori that can fold into various programmed two or three-dimensional shapes. We study the out-of-plane displacement characteristics of this origami and demonstrate with examples, design of slender bodies that conform to programmed complex spatial curves. Our study provides a new, accurate, and single actuation solution of shape programmability.

origami
engineering-design
nanotechnology
materials-science
self-assembly
rather-interesting
to-write-about
representation
out-of-the-box
constraint-satisfaction
constraint-sidestepping
12 days ago by Vaguery

[1605.02681] Programming complex shapes in thin nematic elastomer and glass sheets

12 days ago by Vaguery

Nematic elastomers and glasses are solids that display spontaneous distortion under external stimuli. Recent advances in the synthesis of sheets with controlled heterogeneities have enabled their actuation into non-trivial shapes with unprecedented energy density. Thus, these have emerged as powerful candidates for soft actuators. To further this potential, we introduce the key metric constraint which governs shape changing actuation in these sheets. We then highlight the richness of shapes amenable to this constraint through two broad classes of examples which we term nonisometric origami and lifted surfaces. Finally, we comment on the derivation of the metric constraint, which arises from energy minimization in the interplay of stretching, bending and heterogeneity in these sheets.

materials-science
engineering-design
origami
self-assembly
indistinguishable-from-magic
to-write-about
to-understand
12 days ago by Vaguery

[1810.05070] Crazy Sequential Representations of Numbers for Small Bases

12 days ago by Vaguery

Throughout history, recreational mathematics has always played a prominent role in advancing research. Following in this tradition, in this paper we extend some recent work with crazy sequential representations of numbers- equations made of sequences of one through nine (or nine through one) that evaluate to a number. All previous work on this type of puzzle has focused only on base ten numbers and whether a solution existed. We generalize this concept and examine how this extends to arbitrary bases, the ranges of possible numbers, the combinatorial challenge of finding the numbers, efficient algorithms, and some interesting patterns across any base. For the analysis, we focus on bases three through ten. Further, we outline several interesting mathematical and algorithmic complexity problems related to this area that have yet to be considered.

mathematical-recreations
number-theory
to-write-about
nudge-targets
consider:genetic-programming
consider:performance-measures
consider:ReQ-like-evaluation
12 days ago by Vaguery

climagic - LED Lights that you can control from the command line

20 days ago by Vaguery

While everyone jokes about turning off someone else's lights over the Internet, you can actually do it. Welcome to lights.climagic.com, where you and perhaps hundreds of others can use their command line skills to control these lights in interesting ways. You can also control the lights using the number keys on your keyboard on this webpage or by touching/clicking the lights, but that's boring and slow. A programming interface offers you a level of control that your hands can't match and the command line makes it quick and easy to write a complex program.

The 9 LED lights (numbered 1 to 9 from left to right) shown in the live video stream are sitting on a shelf in my house and are controlled by sending a UDP packet with a number to lights.climagic.com on port 45444. Sending a number will flip the state of the LED between on and off. There is only one set of lights and anyone can change the state of a light at any moment so your results may be unpredictable if others are also controlling the lights at the same time. It helps to shrink your browser window a bit and bring up a small terminal next to it. Have fun!

demo
social-psychology
learning-by-doing
rather-interesting
internet-of-intention
to-write-about
The 9 LED lights (numbered 1 to 9 from left to right) shown in the live video stream are sitting on a shelf in my house and are controlled by sending a UDP packet with a number to lights.climagic.com on port 45444. Sending a number will flip the state of the LED between on and off. There is only one set of lights and anyone can change the state of a light at any moment so your results may be unpredictable if others are also controlling the lights at the same time. It helps to shrink your browser window a bit and bring up a small terminal next to it. Have fun!

20 days ago by Vaguery

Why books don’t work | Andy Matuschak

5 weeks ago by Vaguery

My collaborator Michael Nielsen and I made an initial attempt with Quantum Country, a “book” on quantum computation. But reading this “book” doesn’t look like reading any other book. The explanatory text is tightly woven with brief interactive review sessions, meant to exploit the ideas we just introduced. Reading Quantum Country means reading a few minutes of text, then quickly testing your memory about everything you’ve just read, then reading for a few more minutes, or perhaps scrolling back to reread certain details, and so on. Reading Quantum Country also means repeating those quick memory tests in expanding intervals over the following days, weeks, and months. If you read the first chapter, then engage with the memory tests in your inbox over the following days, we expect your working memory will be substantially less taxed when reading the second chapter. What’s more, the interleaved review sessions lighten the metacognitive burden normally foisted onto the reader: they help readers see where they’re absorbing the material and where they’re not.

Quantum Country is just one piece of the memory puzzle, which itself is part a larger tapestry. How might we design mediums in which “readers” naturally form rich associations between the ideas being presented? How might we design mediums which “readers” naturally engage creatively with the material? How might we design mediums in which “readers” naturally contend with competing interpretations? If we pile together enough of these questions we’re left with: how might we design mediums in which “reading” is the same as “understanding”? A more detailed treatment of such a research program is beyond the scope of these brief notes, but I believe that the answers to questions like these can transform the pace of human knowledge, echoing the transformation which books themselves sparked so long ago.

pedagogy
books
rather-interesting
academic-culture
media
to-write-about
to-understand
Quantum Country is just one piece of the memory puzzle, which itself is part a larger tapestry. How might we design mediums in which “readers” naturally form rich associations between the ideas being presented? How might we design mediums which “readers” naturally engage creatively with the material? How might we design mediums in which “readers” naturally contend with competing interpretations? If we pile together enough of these questions we’re left with: how might we design mediums in which “reading” is the same as “understanding”? A more detailed treatment of such a research program is beyond the scope of these brief notes, but I believe that the answers to questions like these can transform the pace of human knowledge, echoing the transformation which books themselves sparked so long ago.

5 weeks ago by Vaguery

[1005.3466] Mathematical retroreflectors

7 weeks ago by Vaguery

Retroreflectors are optical devices that reverse the direction of incident beams of light. Here we present a collection of billiard type retroreflectors consisting of four objects; three of them are asymptotically perfect retroreflectors, and the fourth one is a retroreflector which is very close to perfect. Three objects of the collection have recently been discovered and published or submitted for publication. The fourth object - notched angle - is a new one; a proof of its retroreflectivity is given.

dynamical-systems
engineering-design
rather-interesting
performance-measure
approximation
to-write-about
to-simulate
consider:looking-to-see
nudge-targets
7 weeks ago by Vaguery

[1702.04199] The problem of camouflaging via mirror reflections

7 weeks ago by Vaguery

This work is related to billiards and their applications in geometric optics. It is known that perfectly invisible bodies with mirror surface do not exist. It is natural to search for bodies that are, in a sense, close to invisible. We introduce a {\it visibility index} of a body measuring the mean angle of deviation of incident light rays, and derive a lower estimate to this index. This estimate is a function of the body's volume and of the minimal radius of a ball containing the body. This result is far from being final and opens a possibility for further research.

billiards
optics
optimization
geometry
inverse-problems
rather-interesting
approximation
to-write-about
nudge-targets
consider:looking-to-see
7 weeks ago by Vaguery

[1312.5260] The Six Circles Theorem revisited

7 weeks ago by Vaguery

The Six Circles Theorem of C. Evelyn, G. Money-Coutts, and J. Tyrrell concerns chains of circles inscribed into a triangle: the first circle is inscribed in the first angle, the second circle is inscribed in the second angle and tangent to the first circle, the third circle is inscribed in the third angle and tangent to the second circle, and so on, cyclically. The theorem asserts that if all the circles touch the sides of the triangle, and not their extensions, then the chain is 6-periodic. We show that, in general, the chain is eventually 6-periodic but may have an arbitrarily long pre-period.

plane-geometry
looking-to-see
construction
rather-interesting
to-write-about
open-questions
out-of-the-box
nudge-targets
consider:looking-to-see
7 weeks ago by Vaguery

[1810.03053] Limiting Distributions in Generalized Zeckendorf Decompositions

7 weeks ago by Vaguery

An equivalent definition of the Fibonacci numbers is that they are the unique sequence such that every integer can be written uniquely as a sum of non-adjacent terms. We can view this as we have bins of length 1, we can take at most one element from a bin, and if we choose an element from a bin we cannot take one from a neighboring bin. We generalize to allowing bins of varying length and restrictions as to how many elements may be used in a decomposition. We derive conditions on when the resulting sequences have uniqueness of decomposition, and (similar to the Fibonacci case) when the number of summands converges to a Gaussian; the main tool in the proofs here is the Lyaponuv Central Limit Theorem.

number-theory
fibonacci
construction
combinatorics
proof
generalization
rather-interesting
to-write-about
7 weeks ago by Vaguery

[1607.04758] Projective configuration theorems: old wine into new wineskins

7 weeks ago by Vaguery

This is a survey of select recent results by a number of authors, inspired by the classical configuration theorems of projective geometry.

geometry
review
rather-interesting
computational-geometry
proof
mathematical-recreations
plane-geometry
to-write-about
to-simulate
consider:rediscovery
billiards
7 weeks ago by Vaguery

[1804.06483] On Rigid Origami II: Quadrilateral Creased Papers

7 weeks ago by Vaguery

This paper describes several new variations of large rigid-foldable quadrilateral creased papers, which are generated by "stitching" together rigid-foldable Kokotsakis quadrilaterals. These creased papers are constructed with the following additional requirements: (a) There is at least one rigid folding motion for which no folding angle remains constant. (b) The quadrilateral creased paper is infinitely extendable in both longitudinal and transverse directions. (c) The sector angles, which define the crease directions, can be solved quadrilateral by quadrilateral. This work is based on a nearly complete classification of rigid-foldable Kokotsakis quadrilaterals from Ivan Izmestiev. All quadrilateral creased papers described in this paper have one degree of freedom in each branch of their rigid folding motion.

origami
engineering-design
rather-interesting
geometry
materials-science
kinematics
planning
to-write-about
7 weeks ago by Vaguery

[1707.05033] Discrete Extremes

7 weeks ago by Vaguery

Our contribution is to widen the scope of extreme value analysis applied to discrete-valued data. Extreme values of a random variable X are commonly modeled using the generalized Pareto distribution, a method that often gives good results in practice. When X is discrete, we propose two other methods using a discrete generalized Pareto and a generalized Zipf distribution respectively. Both are theoretically motivated and we show that they perform well in estimating rare events in several simulated and real data cases such as word frequency, tornado outbreaks and multiple births.

extreme-values
statistics
probability-theory
rather-interesting
to-write-about
nudge-targets
consider:looking-to-see
7 weeks ago by Vaguery

[1902.10835] Keeping it Together: Interleaved Kirigami Extension Assembly

7 weeks ago by Vaguery

Traditional origami structures can be continuously deformed back to a flat sheet of paper, while traditional kirigami requires glue or seams in order to maintain its rigidity. In the former, non-trivial geometry can be created through overfolding paper while, in the latter, the paper topology is modified. Here we propose a hybrid approach that relies upon overlapped flaps that create in-plane compression resulting in the formation of "virtual" elastic shells. Not only are these structures self-supporting, but they have colossal load-to-weight ratios of order 10000.

origami
kirigami
engineering-design
rather-interesting
metamaterials
to-write-about
materials-science
7 weeks ago by Vaguery

[1809.03070] Rectangle Coincidences and Sweepouts

7 weeks ago by Vaguery

We prove an integral formula for continuous paths of rectangles inscribed in a piecewise smooth loop. We then use this integral formula to show that (with a very mild genericity hypothesis) the number of rectangle coincidences, informally described as the number of inscribed rectangles minus the number of isometry classes of inscribed rectangles, grows linearly with the number of positively oriented extremal chords -- a.k.a. diameters -- of the polygon

plane-geometry
planning
open-questions
approximation
rather-interesting
consider:simulation
to-write-about
7 weeks ago by Vaguery

[1701.04788] Width-$k$ Generalizations of Classical Permutation Statistics

7 weeks ago by Vaguery

We introduce new natural generalizations of the classical descent and inversion statistics for permutations, called width-k descents and width-k inversions. These variations induce generalizations of the excedance and major statistics, providing a framework in which the most well-known equidistributivity results for classical statistics are paralleled. We explore additional relationships among the statistics providing specific formulas in certain special cases. Moreover, we explore the behavior of these width-k statistics in the context of pattern avoidance.

permutations
combinatorics
feature-construction
rather-interesting
to-understand
patterns
to-simulate
to-write-about
7 weeks ago by Vaguery

[0909.5452] Palindromes in Different Bases: A Conjecture of J. Ernest Wilkins

7 weeks ago by Vaguery

We show that there exist exactly 203 positive integers N such that for some integer d≥2 this number is a d-digit palindrome base 10 as well as a d-digit palindrome for some base b different from 10. To be more precise, such N range from 22 to 9986831781362631871386899.

number-theory
palindromes
mathematical-recreations
open-questions
to-write-about
consider:feature-discovery
7 weeks ago by Vaguery

AIs are scapegoats and it’s us who end up bleeding – blog.rinesi.com

7 weeks ago by Vaguery

As Ted Chiang famously noted, Silicon Valley — and its global metastasis in politics and finance — projects its own philosophical foundations and instincts onto the technology it builds. They expect software will do what they would, which is a terrifying idea if you know as well as they do what that is. But we're also falling for our own form of projection, tempted by generations of sci-fi into wondering about rogue robot soldiers instead of unaccountable military deployments of poorly-tested machines. "Autonomous," for machines, is an engineering term, not a philosophical one. The confusion is a convenient one, though, if you want to be able to disavow their actions.

the-social-and-the-technical
artificial-intelligence
engineering-criticism
to-write-about
7 weeks ago by Vaguery

Divisive factorials! | bit-player

7 weeks ago by Vaguery

The list is full of curious patterns. It’s a double helix, with even numbers and odd numbers zigzagging in complementary strands. The even numbers are not just even; they are all powers of 2

2

. Also, they appear in pairs—first in the numerator, then in the denominator—and their sequence is nondecreasing. But there are gaps; not all powers of 2

2

are present. The odd strand looks even more complicated, with various small prime factors flitting in and out of the numbers. (The primes have to be small—smaller than n

n

, anyway.)

This outcome took me by surprise. I had really expected to see a much tamer sequence, like those I worked out with pencil and paper. All those jagged, jitterbuggy ups and downs made no sense. Nor did the overall trend of unbounded growth in the ratio. How could you keep dividing and dividing, and wind up with bigger and bigger numbers?

number-theory
out-of-the-box
looking-to-see
the-mangle-in-practice
mathematical-recreations
to-write-about
2

. Also, they appear in pairs—first in the numerator, then in the denominator—and their sequence is nondecreasing. But there are gaps; not all powers of 2

2

are present. The odd strand looks even more complicated, with various small prime factors flitting in and out of the numbers. (The primes have to be small—smaller than n

n

, anyway.)

This outcome took me by surprise. I had really expected to see a much tamer sequence, like those I worked out with pencil and paper. All those jagged, jitterbuggy ups and downs made no sense. Nor did the overall trend of unbounded growth in the ratio. How could you keep dividing and dividing, and wind up with bigger and bigger numbers?

7 weeks ago by Vaguery

Automatic sequence - Wikipedia

7 weeks ago by Vaguery

In mathematics and theoretical computer science, an automatic sequence (also called a k-automatic sequence or a k-recognizable sequence when one wants to indicate that the base of the numerals used is k) is an infinite sequence of terms characterized by a finite automaton. The n-th term of an automatic sequence a(n) is a mapping of the final state reached in a finite automaton accepting the digits of the number n in some fixed base k.[1][2]

An automatic set is a set of non-negative integers S for which the sequence of values of its characteristic function χS is an automatic sequence; that is, S is k-automatic if χS(n) is k-automatic, where χS(n) = 1 if n

formal-languages
number-theory
algorithms
to-write-about
to-learn
consider:complexity
consider:representation
An automatic set is a set of non-negative integers S for which the sequence of values of its characteristic function χS is an automatic sequence; that is, S is k-automatic if χS(n) is k-automatic, where χS(n) = 1 if n

7 weeks ago by Vaguery

Things about science (that you may have not considered yet).

7 weeks ago by Vaguery

THIS IS a draft of an introductory essay for the Open Scientist Handbook… I would love to know if it’s going in an interesting direction.

There are books and libraries of books that talk about science: its history, sociology, philosophy, politics, and practice. As a scientist, you’ve likely gotten this far in life without reading any of these. You probably don’t need to start now. In this essay, a few remarks about science will help anchor the (still being written) Open Scientist Handbook into a particular framework for science as a project, as an endeavor, and a lifeway.

You are already a scientist, so you don’t need a general introduction to “science.” Also, you can learn everything you need about open science as a practice by checking out the Open Science MOOC.

WHEN THE HANDBOOK is done, this essay will have live-links into several other essays/sections in the book that you can explore if you wish, when it’s convenient. (NOTE: This handbook follows the “mullet” logic: all the great stuff up front, and the ragged details in the back.) Here you will find several Richard Feynman quotes. Do you want a good example of an open scientist? Be like Richard Feynman (who died before open science became a meme):

Feynman quote (still looking for the source):

“Physics is like sex: sure, it may give some practical results, but that’s not why we do it.”

open-science
public-policy
drafts
rather-interesting
to-write-about
There are books and libraries of books that talk about science: its history, sociology, philosophy, politics, and practice. As a scientist, you’ve likely gotten this far in life without reading any of these. You probably don’t need to start now. In this essay, a few remarks about science will help anchor the (still being written) Open Scientist Handbook into a particular framework for science as a project, as an endeavor, and a lifeway.

You are already a scientist, so you don’t need a general introduction to “science.” Also, you can learn everything you need about open science as a practice by checking out the Open Science MOOC.

WHEN THE HANDBOOK is done, this essay will have live-links into several other essays/sections in the book that you can explore if you wish, when it’s convenient. (NOTE: This handbook follows the “mullet” logic: all the great stuff up front, and the ragged details in the back.) Here you will find several Richard Feynman quotes. Do you want a good example of an open scientist? Be like Richard Feynman (who died before open science became a meme):

Feynman quote (still looking for the source):

“Physics is like sex: sure, it may give some practical results, but that’s not why we do it.”

7 weeks ago by Vaguery

How We Analyzed the COMPAS Recidivism Algorithm — ProPublica

7 weeks ago by Vaguery

Our analysis found that:

Black defendants were often predicted to be at a higher risk of recidivism than they actually were. Our analysis found that black defendants who did not recidivate over a two-year period were nearly twice as likely to be misclassified as higher risk compared to their white counterparts (45 percent vs. 23 percent).

White defendants were often predicted to be less risky than they were. Our analysis found that white defendants who re-offended within the next two years were mistakenly labeled low risk almost twice as often as black re-offenders (48 percent vs. 28 percent).

The analysis also showed that even when controlling for prior crimes, future recidivism, age, and gender, black defendants were 45 percent more likely to be assigned higher risk scores than white defendants.

Black defendants were also twice as likely as white defendants to be misclassified as being a higher risk of violent recidivism. And white violent recidivists were 63 percent more likely to have been misclassified as a low risk of violent recidivism, compared with black violent recidivists.

The violent recidivism analysis also showed that even when controlling for prior crimes, future recidivism, age, and gender, black defendants were 77 percent more likely to be assigned higher risk scores than white defendants.

bias
algorithms
engineering-criticism
the-social-construction-of-algorithms
public-policy
the-mangle-of-journalism
to-write-about
to-promote
Black defendants were often predicted to be at a higher risk of recidivism than they actually were. Our analysis found that black defendants who did not recidivate over a two-year period were nearly twice as likely to be misclassified as higher risk compared to their white counterparts (45 percent vs. 23 percent).

White defendants were often predicted to be less risky than they were. Our analysis found that white defendants who re-offended within the next two years were mistakenly labeled low risk almost twice as often as black re-offenders (48 percent vs. 28 percent).

The analysis also showed that even when controlling for prior crimes, future recidivism, age, and gender, black defendants were 45 percent more likely to be assigned higher risk scores than white defendants.

Black defendants were also twice as likely as white defendants to be misclassified as being a higher risk of violent recidivism. And white violent recidivists were 63 percent more likely to have been misclassified as a low risk of violent recidivism, compared with black violent recidivists.

The violent recidivism analysis also showed that even when controlling for prior crimes, future recidivism, age, and gender, black defendants were 77 percent more likely to be assigned higher risk scores than white defendants.

7 weeks ago by Vaguery

Heesch Numbers — Numberphile

7 weeks ago by Vaguery

Another lovely enumeration problem that wants exploring.

enumeration
tiling
combinatorics
rather-interesting
to-write-about
consider:representation
consider:feature-discovery
to-simulate
7 weeks ago by Vaguery

[1806.03455] A Preliminary Exploration of Floating Point Grammatical Evolution

7 weeks ago by Vaguery

Current GP frameworks are highly effective on a range of real and simulated benchmarks. However, due to the high dimensionality of the genotypes for GP, the task of visualising the fitness landscape for GP search can be difficult. This paper describes a new framework: Floating Point Grammatical Evolution (FP-GE) which uses a single floating point genotype to encode an individual program. This encoding permits easier visualisation of the fitness landscape arbitrary problems by providing a way to map fitness against a single dimension. The new framework also makes it trivially easy to apply continuous search algorithms, such as Differential Evolution, to the search problem. In this work, the FP-GE framework is tested against several regression problems, visualising the search landscape for these and comparing different search meta-heuristics.

metaheuristics
grammatical-evolution
representation
horse-races
to-write-about
consider:robustness
7 weeks ago by Vaguery

[1804.02998] Anomaly Detection for Industrial Big Data

7 weeks ago by Vaguery

As the Industrial Internet of Things (IIoT) grows, systems are increasingly being monitored by arrays of sensors returning time-series data at ever-increasing 'volume, velocity and variety' (i.e. Industrial Big Data). An obvious use for these data is real-time systems condition monitoring and prognostic time to failure analysis (remaining useful life, RUL). (e.g. See white papers by this http URL, and output of the NASA Prognostics Center of Excellence (PCoE).) However, as noted by Agrawal and Choudhary 'Our ability to collect "big data" has greatly surpassed our capability to analyze it, underscoring the emergence of the fourth paradigm of science, which is data-driven discovery.' In order to fully utilize the potential of Industrial Big Data we need data-driven techniques that operate at scales that process models cannot. Here we present a prototype technique for data-driven anomaly detection to operate at industrial scale. The method generalizes to application with almost any multivariate dataset based on independent ordinations of repeated (bootstrapped) partitions of the dataset and inspection of the joint distribution of ordinal distances.

anomaly-detection
machine-learning
dimension-reduction
statistics
to-write-about
algorithms
7 weeks ago by Vaguery

[1810.08584] Reverse Quantum Annealing Approach to Portfolio Optimization Problems

7 weeks ago by Vaguery

We investigate a hybrid quantum-classical solution method to the mean-variance portfolio optimization problems. Starting from real financial data statistics and following the principles of the Modern Portfolio Theory, we generate parametrized samples of portfolio optimization problems that can be related to quadratic binary optimization forms programmable in the analog D-Wave Quantum Annealer 2000Q. The instances are also solvable by an industry-established Genetic Algorithm approach, which we use as a classical benchmark. We investigate several options to run the quantum computation optimally, ultimately discovering that the best results in terms of expected time-to-solution as a function of number of variables for the hardest instances set are obtained by seeding the quantum annealer with a solution candidate found by a greedy local search and then performing a reverse annealing protocol. The optimized reverse annealing protocol is found to be more than 100 times faster than the corresponding forward quantum annealing on average.

metaheuristics
quantums
portfolio-theory
optimization
algorithms
to-write-about
7 weeks ago by Vaguery

[1512.01289] Predicting and visualizing psychological attributions with a deep neural network

7 weeks ago by Vaguery

Judgments about personality based on facial appearance are strong effectors in social decision making, and are known to have impact on areas from presidential elections to jury decisions. Recent work has shown that it is possible to predict perception of memorability, trustworthiness, intelligence and other attributes in human face images. The most successful of these approaches require face images expertly annotated with key facial landmarks. We demonstrate a Convolutional Neural Network (CNN) model that is able to perform the same task without the need for landmark features, thereby greatly increasing efficiency. The model has high accuracy, surpassing human-level performance in some cases. Furthermore, we use a deconvolutional approach to visualize important features for perception of 22 attributes and demonstrate a new method for separately visualizing positive and negative features.

face-recognition
neural-networks
rather-interesting
cultural-norms
social-psychology
psychology
to-write-about
consider:feature-discovery
7 weeks ago by Vaguery

[1606.09402] Efficient Randomized Algorithms for the Fixed-Precision Low-Rank Matrix Approximation

7 weeks ago by Vaguery

Randomized algorithms for low-rank matrix approximation are investigated, with the emphasis on the fixed-precision problem and computational efficiency for handling large matrices. The algorithms are based on the so-called QB factorization, where Q is an orthonormal matrix. Firstly, a mechanism for calculating the approximation error in Frobenius norm is proposed, which enables efficient adaptive rank determination for large and/or sparse matrix. It can be combined with any QB-form factorization algorithm in which B's rows are incrementally generated. Based on the blocked randQB algorithm by P.-G. Martinsson and S. Voronin, this results in an algorithm called randQB EI. Then, we further revise the algorithm to obtain a pass-efficient algorithm, randQB FP, which is mathematically equivalent to the existing randQB algorithms and also suitable for the fixed-precision problem. Especially, randQB FP can serve as a single-pass algorithm for calculating leading singular values, under certain condition. With large and/or sparse test matrices, we have empirically validated the merits of the proposed techniques, which exhibit remarkable speedup and memory saving over the blocked randQB algorithm. We have also demonstrated that the single-pass algorithm derived by randQB FP is much more accurate than an existing single-pass algorithm. And with data from a scenic image and an information retrieval application, we have shown the advantages of the proposed algorithms over the adaptive range finder algorithm for solving the fixed-precision problem.

numerical-methods
approximation
constraint-satisfaction
algorithms
performance-measure
matrices
to-write-about
7 weeks ago by Vaguery

[1709.07662] Estimating the maximum possible earthquake magnitude using extreme value methodology: the Groningen case

8 weeks ago by Vaguery

The area-characteristic, maximum possible earthquake magnitude TM is required by the earthquake engineering community, disaster management agencies and the insurance industry. The Gutenberg-Richter law predicts that earthquake magnitudes M follow a truncated exponential distribution. In the geophysical literature several estimation procedures were proposed, see for instance Kijko and Singh (Acta Geophys., 2011) and the references therein. Estimation of TM is of course an extreme value problem to which the classical methods for endpoint estimation could be applied. We argue that recent methods on truncated tails at high levels (Beirlant et al., Extremes, 2016; Electron. J. Stat., 2017) constitute a more appropriate setting for this estimation problem. We present upper confidence bounds to quantify uncertainty of the point estimates. We also compare methods from the extreme value and geophysical literature through simulations. Finally, the different methods are applied to the magnitude data for the earthquakes induced by gas extraction in the Groningen province of the Netherlands.

power-laws
geology
rather-interesting
natural-experiments
statistics
prediction
extreme-values
to-write-about
8 weeks ago by Vaguery

Constructive analysis, types and exact real numbers | Mathematical Structures in Computer Science | Cambridge Core

8 weeks ago by Vaguery

In this paper we will discuss various aspects of computable/constructive analysis, namely semantics, proofs and computations. We will present some of the problems and solutions of exact real arithmetic varying from concrete implementations, representation and algorithms to various models for real computation. We then put these models in a uniform framework using realisability, which opens the door to the use of type theoretic and coalgebraic constructions both in computing and reasoning about these computations. We will indicate that it is often natural to use constructive logic to reason about these computations.

representation
number-theory
formal-languages
algebra
rather-interesting
to-write-about
consider:representation
consider:genetic-programming
8 weeks ago by Vaguery

[0807.3322] A characterization of substitutive sequences using return words

8 weeks ago by Vaguery

We prove that a sequence is primitive substitutive if and only if the set of its derived sequences is finite; we defined these sequences here.

rewriting-systems
proof
to-understand
number-theory
mathematical-recreations
to-write-about
8 weeks ago by Vaguery

[math/0511674] On the complexity of algebraic number I. Expansions in integer bases

8 weeks ago by Vaguery

Let b≥2 be an integer. We prove that the b-adic expansion of every irrational algebraic number cannot have low complexity. Furthermore, we establish that irrational morphic numbers are transcendental, for a wide class of morphisms. In particular, irrational automatic numbers are transcendental. Our main tool is a new, combinatorial transcendence criterion.

number-theory
representation
rewriting-systems
computational-complexity
to-write-about
mathematical-recreations
8 weeks ago by Vaguery

The origins of combinatorics on words - ScienceDirect

8 weeks ago by Vaguery

We investigate the historical roots of the field of combinatorics on words. They comprise applications and interpretations in algebra, geometry and combinatorial enumeration. These considerations gave rise to early results such as those of Axel Thue at the beginning of the 20th century. Other early results were obtained as a by-product of investigations on various combinatorial objects. For example, paths in graphs are encoded by words in a natural way, and conversely, the Cayley graph of a group or a semigroup encodes words by paths. We give in this text an account of this two-sided interaction.

rewriting-systems
formal-languages
computational-complexity
combinatorics
mathematical-recreations
to-write-about
8 weeks ago by Vaguery

A generalization of automatic sequences - ScienceDirect

8 weeks ago by Vaguery

We generalize the uniform tag sequences of Cobham, which arise as images of fixed points of k-uniform homomorphisms, to the case where the homomorphism ϕ is not necessarily uniform, but rather satisfies the analogue of an algebraic equation. We show that these sequences coincide with

1.

(a) the class of sequences accepted by a finite automaton with “generalized digits” as input, and

2.

(b) generalizations of the “locally catenative formula” of Rozenberg and Lindenmayer.

Examples include the infinite Fibonacci word, which is generated as the fixed point of the homomorphism ϕ(a) = ab, ϕ(b) = a, and sequences of Rauzy and De Bruijn.

number-theory
rewriting-systems
Lindenmayer-systems
formal-languages
representation
continued-fractions
mathematical-recreations
to-write-about
1.

(a) the class of sequences accepted by a finite automaton with “generalized digits” as input, and

2.

(b) generalizations of the “locally catenative formula” of Rozenberg and Lindenmayer.

Examples include the infinite Fibonacci word, which is generated as the fixed point of the homomorphism ϕ(a) = ab, ϕ(b) = a, and sequences of Rauzy and De Bruijn.

8 weeks ago by Vaguery

[1802.03719] Encoding and avoiding 2-connected patterns in polygon dissections and outerplanar graphs

8 weeks ago by Vaguery

Let Δ={δ1,δ2,...,δm} be a finite set of 2-connected patterns, i.e. graphs up to vertex relabelling. We study the generating function DΔ(z,u1,u2,...,um), which counts polygon dissections and marks subgraph copies of δi with the variable ui. We prove that this is always algebraic, through an explicit combinatorial decomposition depending on Δ. The decomposition also gives a defining system for DΔ(z,0), which encodes polygon dissections that restrict these patterns as subgraphs. In this way, we are able to extract normal limit laws for the patterns when they are encoded, and perform asymptotic enumeration of the resulting classes when they are avoided. The results can be directly transferred in the case of labelled outerplanar graphs. We give examples and compute the relevant constants when the patterns are small cycles or dissections.

combinatorics
graph-theory
permutations
rather-interesting
constraint-satisfaction
enumeration
random-graphs
to-write-about
to-understand
8 weeks ago by Vaguery

[1705.04544] Distance-preserving graph contractions

8 weeks ago by Vaguery

Compression and sparsification algorithms are frequently applied in a preprocessing step before analyzing or optimizing large networks/graphs. In this paper we propose and study a new framework contracting edges of a graph (merging vertices into super-vertices) with the goal of preserving pairwise distances as accurately as possible. Formally, given an edge-weighted graph, the contraction should guarantee that for any two vertices at distance d, the corresponding super-vertices remain at distance at least φ(d) in the contracted graph, where φ is a tolerance function bounding the permitted distance distortion. We present a comprehensive picture of the algorithmic complexity of the contraction problem for affine tolerance functions φ(x)=x/α−β, where α≥1 and β≥0 are arbitrary real-valued parameters. Specifically, we present polynomial-time algorithms for trees as well as hardness and inapproximability results for different graph classes, precisely separating easy and hard cases. Further we analyze the asymptotic behavior of contractions, and find efficient algorithms to compute (non-optimal) contractions despite our hardness results.

approximation
graph-theory
algorithms
summarization
rather-interesting
performance-measure
tolerances
to-write-about
to-simulate
8 weeks ago by Vaguery

[1509.00488] The Tournament Scheduling Problem with Absences

8 weeks ago by Vaguery

We study time scheduling problems with allowed absences as a new kind of graph coloring problem. One may think of a sport tournament where each player (each team) is permitted a certain number t of absences. We then examine how many rounds are needed to schedule the whole tournament in the worst case. This upper limit depends on t and on the structure of the graph G whose edges represent the games that have to be played, but also on whether or not the absences are announced before the tournament starts. Therefore, we actually have two upper limits for the number of required rounds. We have χt(G) for pre-scheduling if all absences are pre-fixed, and we have χtOL(G) for on-line scheduling if we have to stay flexible and deal with absences when they occur. We conjecture that χt(G)=Δ(G)+2t and that χtOL(G)=χ′(G)+2t. The first conjecture is stronger than the Total Coloring Conjecture while the second is weaker than the On-Line List Edge Coloring Conjecture. Our conjectures hold for all bipartite graphs. For complete graphs, we prove them partially. Lower and upper bounds to χt(G) and χtOL(G) for general multigraphs G are established, too.

combinatorics
graph-theory
graph-coloring
enumeration
queueing-theory
constraint-satisfaction
to-simulate
to-write-about
consider:looking-to-see
consider:feature-discovery
8 weeks ago by Vaguery

[1608.03145] Physical model of the genotype-to-phenotype map of proteins

8 weeks ago by Vaguery

How DNA is mapped to functional proteins is a basic question of living matter. We introduce and study a physical model of protein evolution which suggests a mechanical basis for this map. Many proteins rely on large-scale motion to function. We therefore treat protein as learning amorphous matter that evolves towards such a mechanical function: Genes are binary sequences that encode the connectivity of the amino acid network that makes a protein. The gene is evolved until the network forms a shear band across the protein, which allows for long-range, soft modes required for protein function. The evolution reduces the high-dimensional sequence space to a low-dimensional space of mechanical modes, in accord with the observed dimensional reduction between genotype and phenotype of proteins. Spectral analysis of the space of 106 solutions shows a strong correspondence between localization around the shear band of both mechanical modes and the sequence structure. Specifically, our model shows how mutations of the gene and their correlations occur at amino acids whose interactions determine the functional mode.

complexology
rather-interesting
theoretical-biology
abstract-models
combinatorics
bioinformatics
structural-biology
structure-function-cartoons
to-write-about
to-simulate
lattice-polymers
8 weeks ago by Vaguery

[1904.04610] Buckling Soft Tensegrities: Fickle Elasticity and Configurational Switching in Living Cells

8 weeks ago by Vaguery

Tensegrity structures are special architectures made by floating compressed struts kept together by a continuous system of tensed cables. The multiplicity of shapes that tensegrity structures can assume and their intrinsic capability to be deployable and assembled, so storing (and releasing) elastic energy, have motivated their success as paradigm -pioneeringly proposed by Donald E. Ingber- to explain some underlying mechanisms regulating dynamics of living cells. The interlaced structure of the cell cytoskeleton, constituted by actin and intermediate filaments and microtubules which continuously change their spatial organization and pre-stresses through polymerization/depolymerization, seems to steer migration, adhesion and cell division by obeying the tensegrity construct. Even though rough calculations lead to estimate discrepancies when comparing axial stiffness of actin filaments and microtubules and recent works have shown bent microtubules, no one has yet tried to remove the hypothesis of rigid struts in tensegrities when used to idealize the cytoskeleton mechanics. With reference to the 30-element tensegrity cell paradigm, we introduce both compressibility and bendability of the struts and rewrite the theory to take into account nonlinear elasticity of both tendons and bars, so abandoning the classical linear stress-strain assumptions. By relaxing the hypothesis of rigidity of the struts, we demonstrate that some quantitative confirmations and many extreme and somehow counterintuitive mechanical behaviors actually exploited by cells for storing/releasing energy, resisting to applied loads and deforming by modulating their overall elasticity and shape through pre-stress changes and instability-guided configurational switching, can be all theoretically found.

theoretical-biology
cell-biology
structural-biology
tensegrity
statics
dynamics
mechanical-engineering
mechanical-design
rather-interesting
to-write-about
to-do
to-simulate
consider:genetic-programming
cytoskeleton
8 weeks ago by Vaguery

[1811.05437] Argumentation for Explainable Scheduling (Full Paper with Proofs)

8 weeks ago by Vaguery

Mathematical optimization offers highly-effective tools for finding solutions for problems with well-defined goals, notably scheduling. However, optimization solvers are often unexplainable black boxes whose solutions are inaccessible to users and which users cannot interact with. We define a novel paradigm using argumentation to empower the interaction between optimization solvers and users, supported by tractable explanations which certify or refute solutions. A solution can be from a solver or of interest to a user (in the context of 'what-if' scenarios). Specifically, we define argumentative and natural language explanations for why a schedule is (not) feasible, (not) efficient or (not) satisfying fixed user decisions, based on models of the fundamental makespan scheduling problem in terms of abstract argumentation frameworks (AFs). We define three types of AFs, whose stable extensions are in one-to-one correspondence with schedules that are feasible, efficient and satisfying fixed decisions, respectively. We extract the argumentative explanations from these AFs and the natural language explanations from the argumentative ones.

explaining-how
argumentation
formal-languages
rather-interesting
optimization
constraint-satisfaction
to-write-about
to-understand
8 weeks ago by Vaguery

[1710.04459] Arguing Machines: Human Supervision of Black Box AI Systems That Make Life-Critical Decisions

8 weeks ago by Vaguery

We consider the paradigm of a black box AI system that makes life-critical decisions. We propose an "arguing machines" framework that pairs the primary AI system with a secondary one that is independently trained to perform the same task. We show that disagreement between the two systems, without any knowledge of underlying system design or operation, is sufficient to arbitrarily improve the accuracy of the overall decision pipeline given human supervision over disagreements. We demonstrate this system in two applications: (1) an illustrative example of image classification and (2) on large-scale real-world semi-autonomous driving data. For the first application, we apply this framework to image classification achieving a reduction from 8.0% to 2.8% top-5 error on ImageNet. For the second application, we apply this framework to Tesla Autopilot and demonstrate the ability to predict 90.4% of system disengagements that were labeled by human annotators as challenging and needing human supervision.

argumentation
collective-intelligence
rather-interesting
adversarial-behavior
robotics
performance-measure
to-write-about
to-understand
coevolution
8 weeks ago by Vaguery

[1606.01305] Zoneout: Regularizing RNNs by Randomly Preserving Hidden Activations

8 weeks ago by Vaguery

We propose zoneout, a novel method for regularizing RNNs. At each timestep, zoneout stochastically forces some hidden units to maintain their previous values. Like dropout, zoneout uses random noise to train a pseudo-ensemble, improving generalization. But by preserving instead of dropping hidden units, gradient information and state information are more readily propagated through time, as in feedforward stochastic depth networks. We perform an empirical investigation of various RNN regularizers, and find that zoneout gives significant performance improvements across tasks. We achieve competitive results with relatively simple models in character- and word-level language modelling on the Penn Treebank and Text8 datasets, and combining with recurrent batch normalization yields state-of-the-art results on permuted sequential MNIST.

machine-learning
tweakers-and-knob-fiddlers
algorithms
stochastic-resonance
a-dash-of-noise
horse-races
rather-interesting
to-write-about
8 weeks ago by Vaguery

[1801.08379] DeepWriting: Making Digital Ink Editable via Deep Generative Modeling

8 weeks ago by Vaguery

Digital ink promises to combine the flexibility and aesthetics of handwriting and the ability to process, search and edit digital text. Character recognition converts handwritten text into a digital representation, albeit at the cost of losing personalized appearance due to the technical difficulties of separating the interwoven components of content and style. In this paper, we propose a novel generative neural network architecture that is capable of disentangling style from content and thus making digital ink editable. Our model can synthesize arbitrary text, while giving users control over the visual appearance (style). For example, allowing for style transfer without changing the content, editing of digital ink at the word level and other application scenarios such as spell-checking and correction of handwritten text. We furthermore contribute a new dataset of handwritten text with fine-grained annotations at the character level and report results from an initial user evaluation.

generative-models
feature-transfer
style-transfer
deep-learning
neural-networks
rather-interesting
nonlinear-dynamics
interpolation
dimension-reduction
to-write-about
consider:representation
handwriting
algorithms
8 weeks ago by Vaguery

[1206.2231] Triangle Tiling I: The tile is similar to ABC or has a right angle

8 weeks ago by Vaguery

An N -tiling of triangle ABC by triangle T is a way of writing ABC as a union of N triangles congruent to T, overlapping only at their boundaries. The triangle T is the "tile'".

The tile may or may not be similar to ABC . This paper is the first of several papers, which together seek a complete characterization of the triples (ABC,N,T) such that ABC can be N -tiled by T . In this paper, we consider the case in which the tile is similar to ABC, the case in which the tile is a right triangle, and the case when ABC is equilateral.

We use (only) techniques from linear algebra and elementary field theory, as well as elementary geometry and trigonometry.

Our results (in this paper) are as follows: When the tile is similar to ABC, we always have "quadratic tilings'" when N is a square. If the tile is similar to ABC and is not a right triangle, then N is a square. If N is a sum of two squares, N = e^2 + f^2, then a right triangle with legs e and f can be N -tiled by a tile similar to ABC ; these tilings are called "biquadratic". If the tile and ABC are 30-60-90 triangles, then N can also be three times a square. If T is similar to ABC, these are all the possible triples (ABC, T, N) .

If the tile is a right triangle, of course it can tile a certain isosceles triangle when N is twice a square, and in some cases when N is six times a square.

Equilateral triangles can be 3-tiled and 6-tiled and hence they can also be 3n^2 and 6n^2 tiled for any n . We also discovered a family of tilings when N is 3 times a square, which we call the "hexagonal tilings." These tilings exhaust all the possible triples (ABC, T, N) in case T is a right triangle or is similar to ABC . Other cases are treated in subsequent papers.

tiling
plane-geometry
dissection-problems
constraint-satisfaction
rather-interesting
to-do
enumeration
combinatorics
to-write-about
The tile may or may not be similar to ABC . This paper is the first of several papers, which together seek a complete characterization of the triples (ABC,N,T) such that ABC can be N -tiled by T . In this paper, we consider the case in which the tile is similar to ABC, the case in which the tile is a right triangle, and the case when ABC is equilateral.

We use (only) techniques from linear algebra and elementary field theory, as well as elementary geometry and trigonometry.

Our results (in this paper) are as follows: When the tile is similar to ABC, we always have "quadratic tilings'" when N is a square. If the tile is similar to ABC and is not a right triangle, then N is a square. If N is a sum of two squares, N = e^2 + f^2, then a right triangle with legs e and f can be N -tiled by a tile similar to ABC ; these tilings are called "biquadratic". If the tile and ABC are 30-60-90 triangles, then N can also be three times a square. If T is similar to ABC, these are all the possible triples (ABC, T, N) .

If the tile is a right triangle, of course it can tile a certain isosceles triangle when N is twice a square, and in some cases when N is six times a square.

Equilateral triangles can be 3-tiled and 6-tiled and hence they can also be 3n^2 and 6n^2 tiled for any n . We also discovered a family of tilings when N is 3 times a square, which we call the "hexagonal tilings." These tilings exhaust all the possible triples (ABC, T, N) in case T is a right triangle or is similar to ABC . Other cases are treated in subsequent papers.

8 weeks ago by Vaguery

[1206.1974] Tilings of an Isosceles Triangle

8 weeks ago by Vaguery

An N-tiling of triangle ABC by triangle T is a way of writing ABC as a union of N trianglescongruent to T, overlapping only at their boundaries. The triangle T is the "tile". The tile may or may not be similar to ABC. In this paper we study the case of isosceles (but not equilateral) ABC. There are three possible forms of the tile: right-angled, or with one angle double another, or with a 120 degree angle. We study all three cases. In the case of a right-angled tile, we give a complete characterization of the tilings. In the latter two cases we prove the ratios of the sides of the tile are rational, and give a necessary condition for the existence of an N-tiling. For the case when the tile has one angle double another, we prove N cannot be prime.

tiling
constraint-satisfaction
plane-geometry
dissection-problems
rather-interesting
to-do
to-write-about
consider:looking-to-see
consider:expanded-dissections
consider:algorithms
8 weeks ago by Vaguery

[1811.09723] No triangle can be cut into seven congruent triangles

8 weeks ago by Vaguery

We give a short and direct proof of the theorem in the title, and prove the theorem for 11 as well as 7.

tiling
constraint-satisfaction
proof
combinatorics
plane-geometry
to-write-about
to-do
consider:genetic-programming
consider:feature-discovery
consider:rediscovery
talk-about:dominoes
8 weeks ago by Vaguery

[1812.07014] Tiling an Equilateral Triangle

8 weeks ago by Vaguery

Let ABC be an equilateral triangle. For certain triangles T (the "tile") and certain N, it is possible to cut ABC into N copies of T. It is known that only certain shapes of T are possible, but until now very little was known about the possible values of N. Here we prove that for N>3, N cannot be prime.

tiling
combinatorics
constraint-satisfaction
plane-geometry
rather-interesting
to-write-about
to-do
to-simulate
consider:looking-to-see
consider:genetic-programming
consider:rediscovery
consider:feature-discovery
8 weeks ago by Vaguery

[1206.2229] Triangle Tiling: The case $3α+ 2β= π$

8 weeks ago by Vaguery

An N-tiling of triangle ABC by triangle T (the `tile') is a way of writing ABC as a union of N copies of T overlapping only at their boundaries. Let the tile T have angles (α,β,γ), and sides (a,b,c). This paper takes up the case when 3α+2β=π. Then there are (as was already known) exactly five possible shapes of ABC: either ABC is isosceles with base angles α, β, or α+β, or the angles of ABC are (2α,β,α+β), or the angles of ABC are (2α,α,2β). In each of these cases, we have discovered, and here exhibit, a family of previously unknown tilings. These are tilings that, as far as we know, have never been seen before. We also discovered, in each of the cases, a Diophantine equation involving N and the (necessarily rational) number s=a/c that has solutions if there is a tiling using tile T of some ABC not similar to T. By means of these Diophantine equations, some conclusions about the possible values of N are drawn; in particular there are no tilings possible for values of N of certain forms. We prove, for example, that there is no N-tiling with N prime when 3α+2β=π. These equations also imply that for each N, there is a finite set of possibilities for the tile (a,b,c) and the triangle ABC. (Usually, but not always, there is just one possible tile.) These equations provide necessary, and in three of the five cases sufficient, conditions for the existence of N-tilings.

tiling
combinatorics
constraint-satisfaction
rather-interesting
to-write-about
to-simulate
mathematical-recreations
consider:looking-to-see
consider:genetic-programming
consider:classification
8 weeks ago by Vaguery

[1801.09070] Fast cosmic web simulations with generative adversarial networks

8 weeks ago by Vaguery

Dark matter in the universe evolves through gravity to form a complex network of halos, filaments, sheets and voids, that is known as the cosmic web. Computational models of the underlying physical processes, such as classical N-body simulations, are extremely resource intensive, as they track the action of gravity in an expanding universe using billions of particles as tracers of the cosmic matter distribution. Therefore, upcoming cosmology experiments will face a computational bottleneck that may limit the exploitation of their full scientific potential. To address this challenge, we demonstrate the application of a machine learning technique called Generative Adversarial Networks (GAN) to learn models that can efficiently generate new, physically realistic realizations of the cosmic web. Our training set is a small, representative sample of 2D image snapshots from N-body simulations of size 500 and 100 Mpc. We show that the GAN-generated samples are qualitatively and quantitatively very similar to the originals. For the larger boxes of size 500 Mpc, it is very difficult to distinguish them visually. The agreement of the power spectrum Pk is 1-2\% for most of the range, between k=0.06 and k=0.4. An important advantage of generating cosmic web realizations with a GAN is the considerable gains in terms of computation time. Each new sample generated by a GAN takes a fraction of a second, compared to the many hours needed by traditional N-body techniques. We anticipate that the use of generative models such as GANs will therefore play an important role in providing extremely fast and precise simulations of cosmic web in the era of large cosmological surveys, such as Euclid and Large Synoptic Survey Telescope (LSST).

approximation
meta-modeling
rather-interesting
neural-networks
generative-models
to-write-about
really-quite-nice
to-do
8 weeks ago by Vaguery

[1804.03770] Tilings of Sphere by Congruent Pentagons I: Edge Combinations $a^2b^2c$ and $a^3bc$

8 weeks ago by Vaguery

We develop the basic tools for classifying edge-to-edge tilings of sphere by congruent pentagons. Then we prove such tilings for edge combination a2b2c are three families of pentagonal subdivisions of the platonic solids, with 12, 24 and 60 tiles. We also prove that such tilings for edge combination a3bc are two unique double pentagonal subdivisions, with 48 and 120 tiles.

tiling
geometry
topology
rather-interesting
enumeration
representation
to-write-about
to-do
consider:parameter-sweeps-and-animations
8 weeks ago by Vaguery

[1705.06640] DeepXplore: Automated Whitebox Testing of Deep Learning Systems

8 weeks ago by Vaguery

Deep learning (DL) systems are increasingly deployed in safety- and security-critical domains including self-driving cars and malware detection, where the correctness and predictability of a system's behavior for corner case inputs are of great importance. Existing DL testing depends heavily on manually labeled data and therefore often fails to expose erroneous behaviors for rare inputs.

We design, implement, and evaluate DeepXplore, the first whitebox framework for systematically testing real-world DL systems. First, we introduce neuron coverage for systematically measuring the parts of a DL system exercised by test inputs. Next, we leverage multiple DL systems with similar functionality as cross-referencing oracles to avoid manual checking. Finally, we demonstrate how finding inputs for DL systems that both trigger many differential behaviors and achieve high neuron coverage can be represented as a joint optimization problem and solved efficiently using gradient-based search techniques.

DeepXplore efficiently finds thousands of incorrect corner case behaviors (e.g., self-driving cars crashing into guard rails and malware masquerading as benign software) in state-of-the-art DL models with thousands of neurons trained on five popular datasets including ImageNet and Udacity self-driving challenge data. For all tested DL models, on average, DeepXplore generated one test input demonstrating incorrect behavior within one second while running only on a commodity laptop. We further show that the test inputs generated by DeepXplore can also be used to retrain the corresponding DL model to improve the model's accuracy by up to 3%.

fuzz-testing
stress-testing
machine-learning
neural-networks
rather-interesting
knobs-to-11
security
software-engineering
trustable-models
to-write-about
We design, implement, and evaluate DeepXplore, the first whitebox framework for systematically testing real-world DL systems. First, we introduce neuron coverage for systematically measuring the parts of a DL system exercised by test inputs. Next, we leverage multiple DL systems with similar functionality as cross-referencing oracles to avoid manual checking. Finally, we demonstrate how finding inputs for DL systems that both trigger many differential behaviors and achieve high neuron coverage can be represented as a joint optimization problem and solved efficiently using gradient-based search techniques.

DeepXplore efficiently finds thousands of incorrect corner case behaviors (e.g., self-driving cars crashing into guard rails and malware masquerading as benign software) in state-of-the-art DL models with thousands of neurons trained on five popular datasets including ImageNet and Udacity self-driving challenge data. For all tested DL models, on average, DeepXplore generated one test input demonstrating incorrect behavior within one second while running only on a commodity laptop. We further show that the test inputs generated by DeepXplore can also be used to retrain the corresponding DL model to improve the model's accuracy by up to 3%.

8 weeks ago by Vaguery

[1811.00612] Zipf's, Heaps' and Taylor's laws are determined by the expansion into the adjacent possible

8 weeks ago by Vaguery

Zipf's, Heaps' and Taylor's laws are ubiquitous in many different systems where innovation processes are at play. Together, they represent a compelling set of stylized facts regarding the overall statistics, the innovation rate and the scaling of fluctuations for systems as diverse as written texts and cities, ecological systems and stock markets. Many modeling schemes have been proposed in literature to explain those laws, but only recently a modeling framework has been introduced that accounts for the emergence of those laws without deducing the emergence of one of the laws from the others or without ad hoc assumptions. This modeling framework is based on the concept of adjacent possible space and its key feature of being dynamically restructured while its boundaries get explored, i.e., conditional to the occurrence of novel events. Here, we illustrate this approach and show how this simple modelling framework, instantiated through a modified Polya's urn model, is able reproduce Zipf's, Heaps' and Taylor's laws within a unique self-consistent scheme. In addition the same modelling scheme embraces other less common evolutionary laws (Hoppe's model and Dirichlet processes) as particular cases.

power-laws
Kauffmania
branching-processes
explanation
models-of-lots-of-stuff
Polya-erm-models-[sic]
probability-theory
OK-so-then-what?
to-write-about
8 weeks ago by Vaguery

[1807.05620] NEUZZ: Efficient Fuzzing with Neural Program Smoothing

8 weeks ago by Vaguery

Fuzzing has become the de facto standard technique for finding software vulnerabilities. However, even state-of-the-art fuzzers are not very efficient at finding hard-to-trigger software bugs. Most popular fuzzers use evolutionary guidance to generate inputs that can trigger different bugs. Such evolutionary algorithms, while fast and simple to implement, often get stuck in fruitless sequences of random mutations. Gradient-guided optimization presents a promising alternative to evolutionary guidance. Gradient-guided techniques have been shown to significantly outperform evolutionary algorithms at solving high-dimensional structured optimization problems in domains like machine learning by efficiently utilizing gradients or higher-order derivatives of the underlying function. However, gradient-guided approaches are not directly applicable to fuzzing as real-world program behaviors contain many discontinuities, plateaus, and ridges where the gradient-based methods often get stuck. We observe that this problem can be addressed by creating a smooth surrogate function approximating the discrete branching behavior of target program. In this paper, we propose a novel program smoothing technique using surrogate neural network models that can incrementally learn smooth approximations of a complex, real-world program's branching behaviors. We further demonstrate that such neural network models can be used together with gradient-guided input generation schemes to significantly improve the fuzzing efficiency. Our extensive evaluations demonstrate that NEUZZ significantly outperforms 10 state-of-the-art graybox fuzzers on 10 real-world programs both at finding new bugs and achieving higher edge coverage. NEUZZ found 31 unknown bugs that other fuzzers failed to find in 10 real world programs and achieved 3X more edge coverage than all of the tested graybox fuzzers for 24 hours running.

robustness
neural-all-the-things
neural-networks
fuzz-testing
stress-testing
software-development
performance-measure
ruthless-efficiency
to-write-about
I-told-him-we-already-had-one
8 weeks ago by Vaguery

[1811.08162] DeepZip: Lossless Data Compression using Recurrent Neural Networks

8 weeks ago by Vaguery

Sequential data is being generated at an unprecedented pace in various forms, including text and genomic data. This creates the need for efficient compression mechanisms to enable better storage, transmission and processing of such data. To solve this problem, many of the existing compressors attempt to learn models for the data and perform prediction-based compression. Since neural networks are known as universal function approximators with the capability to learn arbitrarily complex mappings, and in practice show excellent performance in prediction tasks, we explore and devise methods to compress sequential data using neural network predictors. We combine recurrent neural network predictors with an arithmetic coder and losslessly compress a variety of synthetic, text and genomic datasets. The proposed compressor outperforms Gzip on the real datasets and achieves near-optimal compression for the synthetic datasets. The results also help understand why and where neural networks are good alternatives for traditional finite context models

lolwut
neural-networks
machine-learning
neural-all-the-things
deep-learning
compression
algorithms
meta-algorithms
to-write-about
consider:genetic-programming
oh-wait-we-already-did
8 weeks ago by Vaguery

[1904.08658] Batch Tournament Selection for Genetic Programming

8 weeks ago by Vaguery

Lexicase selection achieves very good solution quality by introducing ordered test cases. However, the computational complexity of lexicase selection can prohibit its use in many applications. In this paper, we introduce Batch Tournament Selection (BTS), a hybrid of tournament and lexicase selection which is approximately one order of magnitude faster than lexicase selection while achieving a competitive quality of solutions. Tests on a number of regression datasets show that BTS compares well with lexicase selection in terms of mean absolute error while having a speed-up of up to 25 times. Surprisingly, BTS and lexicase selection have almost no difference in both diversity and performance. This reveals that batches and ordered test cases are completely different mechanisms which share the same general principle fostering the specialization of individuals. This work introduces an efficient algorithm that sheds light onto the main principles behind the success of lexicase, potentially opening up a new range of possibilities for algorithms to come.

genetic-programming
selection
algorithms
hey-I-know-this-guy
(I-wish-it-wasn't-always-a-guy)
to-write-about
to-do
8 weeks ago by Vaguery

[1902.04724] A characterisation of S-box fitness landscapes in cryptography

8 weeks ago by Vaguery

Substitution Boxes (S-boxes) are nonlinear objects often used in the design of cryptographic algorithms. The design of high quality S-boxes is an interesting problem that attracts a lot of attention. Many attempts have been made in recent years to use heuristics to design S-boxes, but the results were often far from the previously known best obtained ones. Unfortunately, most of the effort went into exploring different algorithms and fitness functions while little attention has been given to the understanding why this problem is so difficult for heuristics. In this paper, we conduct a fitness landscape analysis to better understand why this problem can be difficult. Among other, we find that almost each initial starting point has its own local optimum, even though the networks are highly interconnected.

evolutionary-algorithms
fitness-landscapes
rather-interesting
hard-problems
constructibility
representation
to-write-about
consider:looking-to-see
8 weeks ago by Vaguery

[1808.05850] Towards a Theory-Guided Benchmarking Suite for Discrete Black-Box Optimization Heuristics: Profiling $(1+λ)$ EA Variants on OneMax and LeadingOnes

8 weeks ago by Vaguery

Theoretical and empirical research on evolutionary computation methods complement each other by providing two fundamentally different approaches towards a better understanding of black-box optimization heuristics. In discrete optimization, both streams developed rather independently of each other, but we observe today an increasing interest in reconciling these two sub-branches. In continuous optimization, the COCO (COmparing Continuous Optimisers) benchmarking suite has established itself as an important platform that theoreticians and practitioners use to exchange research ideas and questions. No widely accepted equivalent exists in the research domain of discrete black-box optimization.

Marking an important step towards filling this gap, we adjust the COCO software to pseudo-Boolean optimization problems, and obtain from this a benchmarking environment that allows a fine-grained empirical analysis of discrete black-box heuristics. In this documentation we demonstrate how this test bed can be used to profile the performance of evolutionary algorithms. More concretely, we study the optimization behavior of several (1+λ) EA variants on the two benchmark problems OneMax and LeadingOnes. This comparison motivates a refined analysis for the optimization time of the (1+λ) EA on LeadingOnes.

evolutionary-algorithms
metaheuristics
horse-races
performance-measure
rather-interesting
to-write-about
consider:classification
benchmarking
consider:open-ended-problems
Marking an important step towards filling this gap, we adjust the COCO software to pseudo-Boolean optimization problems, and obtain from this a benchmarking environment that allows a fine-grained empirical analysis of discrete black-box heuristics. In this documentation we demonstrate how this test bed can be used to profile the performance of evolutionary algorithms. More concretely, we study the optimization behavior of several (1+λ) EA variants on the two benchmark problems OneMax and LeadingOnes. This comparison motivates a refined analysis for the optimization time of the (1+λ) EA on LeadingOnes.

8 weeks ago by Vaguery

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

9 weeks ago by Vaguery

The smallest non-trivial examples of 3-inflatable permutations are in size 17: E534BGA9HC2D1687F and B3CE1H76F5A49D2G8, where capital letters denote numbers greater than nine. Another cool property discovered in the paper is that the tensor product of two k-inflatable permutations is k-inflatable.

permutations
rather-interesting
combinatorics
to-write-about
to-simulate
consider:classification
9 weeks ago by Vaguery

[1307.0646] Square Turning Maps and their Compactifications

9 weeks ago by Vaguery

In this paper we introduce some infinite rectangle exchange transformations which are based on the simultaneous turning of the squares within a sequence of square grids. We will show that such noncompact systems have higher dimensional dynamical compactifications. In good cases, these compactifications are polytope exchange transformations based on pairs of Euclidean lattices. In each dimension 8m+4 there is a 4m+2 dimensional family of them. Here m=0,1,2,... The case m=0, which we studied in depth in an earlier paper, has close connections to the E4 Weyl group and the (2,4,∞) hyperbolic triangle group.

rewriting-systems
dynamical-systems
rather-interesting
consider:Lindenmayer-systems
to-simulate
to-write-about
consider:generative-models
9 weeks ago by Vaguery

[0910.1952] Elementary Surprises in Projective Geometry

9 weeks ago by Vaguery

We discuss eight new(?) configuration theorems of classical projective geometry in the spirit of the Pappus and Pascal theorems.

plane-geometry
rather-interesting
open-questions
looking-to-see
compass-and-straightedge
exploration
to-write-about
9 weeks ago by Vaguery

[0807.3498] Billiards in Nearly Isosceles Triangles

9 weeks ago by Vaguery

We prove that any sufficiently small perturbation of an isosceles triangle has a periodic billiard path. Our proof involves the analysis of certain infinite families of Fourier series that arise in connection with triangular billiards, and reveals some self-similarity phenomena in irrational triangular billiards. Our analysis illustrates the surprising fact that billiards on a triangle near a Veech triangle is extremely complicated even though Billiards on a Veech triangle is very well understood.

billiards
dynamical-systems
visualization
plane-geometry
rather-interesting
generative-models
to-simulate
to-write-about
9 weeks ago by Vaguery

[math/0702073] Unbounded Orbits for Outer Billiards

9 weeks ago by Vaguery

Outer billiards is a basic dynamical system, defined relative to a planar convex shape. This system was introduced in the 1950's by B.H. Neumann and later popularized in the 1970's by J. Moser. All along, one of the central questions has been: is there an outer billiards system with an unbounded orbit. We answer this question by proving that outer billiards defined relative to the Penrose Kite has an unbounded orbit. The Penrose kite is the quadrilateral that appears in the famous Penrose tiling. We also analyze some of the finer orbit structure of outer billiards on the penrose kite. This analysis shows that there is an uncountable set of unbounded orbits. Our method of proof relates the problem to self-similar tilings, polygon exchange maps, and arithmetic dynamics.

billiards
mathematical-recreations
generative-models
geometry
dynamical-systems
rather-interesting
chaos
to-simulate
to-write-about
9 weeks ago by Vaguery

[1811.01229] Farey boat I. Continued fractions and triangulations, modular group and polygon dissections

9 weeks ago by Vaguery

We reformulate several known results about continued fractions in combinatorial terms. Among them the theorem of Conway and Coxeter and that of Series, both relating continued fractions and triangulations. More general polygon dissections appear when extending these theorems for elements of the modular group PSL(2,ℤ). These polygon dissections are interpreted as walks in the Farey tessellation. The combinatorial model of continued fractions can be further developed to obtain a canonical presentation of elements of PSL(2,ℤ).

continued-fractions
combinatorics
number-theory
representation
rather-interesting
to-write-about
to-simulate
algorithms
nudge-targets
9 weeks ago by Vaguery

[1206.5223] Outer Billiards, Digital Filters and Kicked Hamiltonians

9 weeks ago by Vaguery

In 1978 Jurgen Moser suggested the outer billiards map (Tangent map) as a discontinuous model of Hamiltonian dynamics. A decade earlier, J.B. Jackson and his colleagues at Bell Labs were trying to understand the source of self-sustaining oscillations in digital filters. Some of the discrete mappings used to describe these filters show a remarkable ability to 'shadow' the Tangent map when the polygon in question is regular.

In this paper we describe a specific digital filter map (Df) that appears to have dynamics which are conjugate to the Tangent map for a regular N-gon with N even. When N is odd, there is evidence of another conjugacy between the Tangent map dynamics of N and the matching 2N-gon, so a case like N = 7 can be studied with the Df map in the context of N = 14. This provides a many-fold increase in efficiency, and also allows us to generalize the Tangent map to obtain 'step-k' versions - which have dynamics that are unexplored.

We also present some related maps, including Chua and Lin's 3-dimensional version of Df, an Analog to Digital Converter from Orla Feely, a sawtooth version of the Standard Map by Peter Ashwin and various kicked harmonic oscillators. All of these seem to shadow the Tangent map in some form. Mathematica code is provided for all mappings both here and at this http URL.

billiards
dynamical-systems
chaos
rather-interesting
purdy-pitchers
to-do
to-write-about
physics!
In this paper we describe a specific digital filter map (Df) that appears to have dynamics which are conjugate to the Tangent map for a regular N-gon with N even. When N is odd, there is evidence of another conjugacy between the Tangent map dynamics of N and the matching 2N-gon, so a case like N = 7 can be studied with the Df map in the context of N = 14. This provides a many-fold increase in efficiency, and also allows us to generalize the Tangent map to obtain 'step-k' versions - which have dynamics that are unexplored.

We also present some related maps, including Chua and Lin's 3-dimensional version of Df, an Analog to Digital Converter from Orla Feely, a sawtooth version of the Standard Map by Peter Ashwin and various kicked harmonic oscillators. All of these seem to shadow the Tangent map in some form. Mathematica code is provided for all mappings both here and at this http URL.

9 weeks ago by Vaguery

[1805.03476] Tight bounds for undirected graph exploration with pebbles and multiple agents

9 weeks ago by Vaguery

We study the problem of deterministically exploring an undirected and initially unknown graph with n vertices either by a single agent equipped with a set of pebbles, or by a set of collaborating agents. The vertices of the graph are unlabeled and cannot be distinguished by the agents, but the edges incident to a vertex have locally distinct labels. The graph is explored when all vertices have been visited by at least one agent. In this setting, it is known that for a single agent without pebbles Θ(logn) bits of memory are necessary and sufficient to explore any graph with at most n vertices. We are interested in how the memory requirement decreases as the agent may mark vertices by dropping and retrieving distinguishable pebbles, or when multiple agents jointly explore the graph. We give tight results for both questions showing that for a single agent with constant memory Θ(loglogn) pebbles are necessary and sufficient for exploration. We further prove that the same bound holds for the number of collaborating agents needed for exploration.

For the upper bound, we devise an algorithm for a single agent with constant memory that explores any n-vertex graph using (loglogn) pebbles, even when n is unknown. The algorithm terminates after polynomial time and returns to the starting vertex. Since an additional agent is at least as powerful as a pebble, this implies that (loglogn) agents with constant memory can explore any n-vertex graph. For the lower bound, we show that the number of agents needed for exploring any graph of size n is already Ω(loglogn) when we allow each agent to have at most (logn1−ε) bits of memory for any ε>0. This also implies that a single agent with sublogarithmic memory needs Θ(loglogn) pebbles to explore any n-vertex graph.

graph-theory
planning
algorithms
heuristics
computational-complexity
swarms
collective-intelligence
to-write-about
to-simulate
For the upper bound, we devise an algorithm for a single agent with constant memory that explores any n-vertex graph using (loglogn) pebbles, even when n is unknown. The algorithm terminates after polynomial time and returns to the starting vertex. Since an additional agent is at least as powerful as a pebble, this implies that (loglogn) agents with constant memory can explore any n-vertex graph. For the lower bound, we show that the number of agents needed for exploring any graph of size n is already Ω(loglogn) when we allow each agent to have at most (logn1−ε) bits of memory for any ε>0. This also implies that a single agent with sublogarithmic memory needs Θ(loglogn) pebbles to explore any n-vertex graph.

9 weeks ago by Vaguery

[1806.03857] Deep Learning for Classification Tasks on Geospatial Vector Polygons

9 weeks ago by Vaguery

In this paper, we evaluate the accuracy of deep learning approaches on geospatial vector geometry classification tasks. The purpose of this evaluation is to investigate the ability of deep learning models to learn from geometry coordinates directly. Previous machine learning research applied to geospatial polygon data did not use geometries directly, but derived properties thereof. These are produced by way of extracting geometry properties such as Fourier descriptors. Instead, our introduced deep neural net architectures are able to learn on sequences of coordinates mapped directly from polygons. In three classification tasks we show that the deep learning architectures are competitive with common learning algorithms that require extracted features.

representation
deep-learning
rather-interesting
machine-learning
to-write-about
the-mangle-in-practice
consider:what-gets-missed
9 weeks ago by Vaguery

[1810.07800] Alignments as Compositional Structures

9 weeks ago by Vaguery

Alignments, i.e., position-wise comparisons of two or more strings or ordered lists are of utmost practical importance in computational biology and a host of other fields, including historical linguistics and emerging areas of research in the Digital Humanities. The problem is well-known to be computationally hard as soon as the number of input strings is not bounded. Due to its prac- tical importance, a huge number of heuristics have been devised, which have proved very successful in a wide range of applications. Alignments nevertheless have received hardly any attention as formal, mathematical structures. Here, we focus on the compositional aspects of alignments, which underlie most algo- rithmic approaches to computing alignments. We also show that the concepts naturally generalize to finite partially ordered sets and partial maps between them that in some sense preserve the partial orders.

discrete-mathematics
optimization
alignments
combinatorics
hey-I-know-this-guy
bioinformatics
rather-interesting
formalization
to-write-about
consider:multiobjective-optimization
consider:fitness-landscapes
question:transitivity
9 weeks ago by Vaguery

[1903.08889] Node Embedding over Temporal Graphs

9 weeks ago by Vaguery

In this work, we present a method for node embedding in temporal graphs. We propose an algorithm that learns the evolution of a temporal graph's nodes and edges over time and incorporates this dynamics in a temporal node embedding framework for different graph prediction tasks. We present a joint loss function that creates a temporal embedding of a node by learning to combine its historical temporal embeddings, such that it optimizes per given task (e.g., link prediction). The algorithm is initialized using static node embeddings, which are then aligned over the representations of a node at different time points, and eventually adapted for the given task in a joint optimization. We evaluate the effectiveness of our approach over a variety of temporal graphs for the two fundamental tasks of temporal link prediction and multi-label node classification, comparing to competitive baselines and algorithmic alternatives. Our algorithm shows performance improvements across many of the datasets and baselines and is found particularly effective for graphs that are less cohesive, with a lower clustering coefficient.

via:twitter
graph-layout
dimension-reduction
visualization
time-series
planning
optimization
rather-interesting
to-write-about
consider:performance-measures
9 weeks ago by Vaguery

[1807.06498] Multistable Kirigami for Tunable Architected Materials

10 weeks ago by Vaguery

In nature, materials such as ferroelastics and multiferroics can switch their microstructure in response to external stimuli, and this reconfiguration causes a simultaneous modulation of its material properties. Rapid prototyping technologies have enabled origami and kirigami-inspired architected materials to provide a means for designing shape-shifting structures, and here we show how multistable structures inspired by kirigami provide novel design criteria for preparing mechanical metamaterials with tunable properties. By changing the geometry of kirigami unit cells, we obtain multistable kirigami lattice structures endowed with a bistable snap-through mechanism. We demonstrate the precise control of material stiffness, along with the ability to tune this property in situ by locally and reversibly switching the unit cell configurations. We anticipate these mechanical metamaterials will provide a platform to achieve in situ tunable electrical, optical, and mechanical properties for a variety of applications in multifunctional materials, two-dimensional materials, and soft robotics.

materials-science
metamaterials
origami
rather-interesting
engineering-design
looking-to-see
nonlinear-dynamics
kinetics
to-write-about
consider:simulation
10 weeks ago by Vaguery

**related tags**

Copy this bookmark: