**dynamical-systems**264

[1710.05183] Inferring Mesoscale Models of Neural Computation

11 days ago by Vaguery

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

dynamical-systems
machine-learning
deep-learning
representation
temporal-models
rather-interesting
inference
to-write-about
11 days ago by Vaguery

Understanding LSTM Networks -- colah's blog

11 days ago by Vaguery

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

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

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

11 days ago by Vaguery

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

14 days ago by Vaguery

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

graph-theory
combinatorics
dynamical-systems
robustness
nudge-targets
heuristics
algorithms
to-write-about
14 days ago by Vaguery

[1310.1166] Flipping Edge-Labelled Triangulations

4 weeks ago by Vaguery

Flips in triangulations have received a lot of attention over the past decades. However, the problem of tracking where particular edges go during the flipping process has not been addressed. We examine this question by attaching unique labels to the triangulation edges. We introduce the concept of the orbit of an edge e, which is the set of all edges reachable from e via flips.

We establish the first upper and lower bounds on the diameter of the flip graph in this setting. Specifically, we prove tight Θ(nlogn) bounds for edge-labelled triangulations of n-vertex convex polygons and combinatorial triangulations, contrasting with the Θ(n) bounds in their respective unlabelled settings. The Ω(nlogn) lower bound for the convex polygon setting might be of independent interest, as it generalizes lower bounds on certain sorting models. When simultaneous flips are allowed, the upper bound for convex polygons decreases to O(log2n), although we no longer have a matching lower bound.

Moving beyond convex polygons, we show that edge-labelled triangulated polygons with a single reflex vertex can have a disconnected flip graph. This is in sharp contrast with the unlabelled case, where the flip graph is connected for any triangulated polygon. For spiral polygons, we provide a complete characterization of the orbits. This allows us to decide connectivity of the flip graph of a spiral polygon in linear time. We also prove an upper bound of O(n2) on the diameter of each connected component, which is optimal in the worst case. We conclude with an example of a non-spiral polygon whose flip graph has diameter Ω(n3).

combinatorics
dynamical-systems
computational-complexity
rather-interesting
consider:looking-to-see
consider:simulation
to-write-about
to-draw
We establish the first upper and lower bounds on the diameter of the flip graph in this setting. Specifically, we prove tight Θ(nlogn) bounds for edge-labelled triangulations of n-vertex convex polygons and combinatorial triangulations, contrasting with the Θ(n) bounds in their respective unlabelled settings. The Ω(nlogn) lower bound for the convex polygon setting might be of independent interest, as it generalizes lower bounds on certain sorting models. When simultaneous flips are allowed, the upper bound for convex polygons decreases to O(log2n), although we no longer have a matching lower bound.

Moving beyond convex polygons, we show that edge-labelled triangulated polygons with a single reflex vertex can have a disconnected flip graph. This is in sharp contrast with the unlabelled case, where the flip graph is connected for any triangulated polygon. For spiral polygons, we provide a complete characterization of the orbits. This allows us to decide connectivity of the flip graph of a spiral polygon in linear time. We also prove an upper bound of O(n2) on the diameter of each connected component, which is optimal in the worst case. We conclude with an example of a non-spiral polygon whose flip graph has diameter Ω(n3).

4 weeks ago by Vaguery

[1208.2762] Computing by Temporal Order: Asynchronous Cellular Automata

4 weeks ago by Vaguery

Our concern is the behaviour of the elementary cellular automata with state set 0,1 over the cell set Z/nZ (one-dimensional finite wrap-around case), under all possible update rules (asynchronicity).

Over the torus Z/nZ (n<= 11),we will see that the ECA with Wolfram rule 57 maps any v in F_2^n to any w in F_2^n, varying the update rule.

We furthermore show that all even (element of the alternating group) bijective functions on the set F_2^n = 0,...,2^n-1, can be computed by ECA57, by iterating it a sufficient number of times with varying update rules, at least for n <= 10. We characterize the non-bijective functions computable by asynchronous rules.

cellular-automata
rather-interesting
asynchronous
collective-behavior
out-of-the-box
dynamical-systems
representation
to-write-about
Over the torus Z/nZ (n<= 11),we will see that the ECA with Wolfram rule 57 maps any v in F_2^n to any w in F_2^n, varying the update rule.

We furthermore show that all even (element of the alternating group) bijective functions on the set F_2^n = 0,...,2^n-1, can be computed by ECA57, by iterating it a sufficient number of times with varying update rules, at least for n <= 10. We characterize the non-bijective functions computable by asynchronous rules.

4 weeks ago by Vaguery

[1208.2762v1] Computing by Temporal Order: Asynchronous Cellular Automata

4 weeks ago by Vaguery

Our concern is the behaviour of the elementary cellular automata with state set 0,1 over the cell set Z/nZ (one-dimensional finite wrap-around case), under all possible update rules (asynchronicity).

Over the torus Z/nZ (n<= 11),we will see that the ECA with Wolfram rule 57 maps any v in F_2^n to any w in F_2^n, varying the update rule.

We furthermore show that all even (element of the alternating group) bijective functions on the set F_2^n = 0,...,2^n-1, can be computed by ECA57, by iterating it a sufficient number of times with varying update rules, at least for n <= 10. We characterize the non-bijective functions computable by asynchronous rules.

cellular-automata
rather-interesting
out-of-the-box
asynchronous
collective-behavior
dynamical-systems
nudge-targets
consider:looking-to-see
to-write-about
Over the torus Z/nZ (n<= 11),we will see that the ECA with Wolfram rule 57 maps any v in F_2^n to any w in F_2^n, varying the update rule.

We furthermore show that all even (element of the alternating group) bijective functions on the set F_2^n = 0,...,2^n-1, can be computed by ECA57, by iterating it a sufficient number of times with varying update rules, at least for n <= 10. We characterize the non-bijective functions computable by asynchronous rules.

4 weeks ago by Vaguery

New Shapes Solve Infinite Pool-Table Problem | Quanta Magazine

6 weeks ago by Vaguery

Two “rare jewels” have illuminated a mysterious multidimensional object that connects a huge variety of mathematical work.

dynamical-systems
geometry
rather-interesting
mathematical-recreations
nudge-targets
consider:looking-to-see
consider:feature-discovery
6 weeks ago by Vaguery

[1703.07695] Selfish Cops and Adversarial Robber: Multi-Player Pursuit Evasion on Graphs

7 weeks ago by Vaguery

We introduce and study the game of Selfish Cops and Adversarial Robber (SCAR) which is an N-player generalization of the classic two-player cops and robbers (CR) game. We prove that SCAR has a Nash equilibrium in deterministic strategies.

game-theory
graph-theory
dynamical-systems
feature-construction
to-write-about
to-simulate
nudge-targets
consider:looking-to-see
7 weeks ago by Vaguery

[1404.6238] Recurrence and transience for the frog model on trees

7 weeks ago by Vaguery

The frog model is a growing system of random walks where a particle is added whenever a new site is visited. A longstanding open question is how often the root is visited on the infinite d-ary tree. We prove the model undergoes a phase transition, finding it recurrent for d=2 and transient for d≥5. Simulations suggest strong recurrence for d=2, weak recurrence for d=3, and transience for d≥4. Additionally, we prove a 0-1 law for all d-ary trees, and we exhibit a graph on which a 0-1 law does not hold.

To prove recurrence when d=2, we construct a recursive distributional equation for the number of visits to the root in a smaller process and show the unique solution must be infinity a.s. The proof of transience when d=5 relies on computer calculations for the transition probabilities of a large Markov chain. We also include the proof for d≥6, which uses similar techniques but does not require computer assistance.

probability-theory
graph-theory
random-walks
dynamical-systems
rather-interesting
to-understand
to-write-about
consider:feature-discovery
consider:classification
To prove recurrence when d=2, we construct a recursive distributional equation for the number of visits to the root in a smaller process and show the unique solution must be infinity a.s. The proof of transience when d=5 relies on computer calculations for the transition probabilities of a large Markov chain. We also include the proof for d≥6, which uses similar techniques but does not require computer assistance.

7 weeks ago by Vaguery

[1610.01369] Self-referential Functions

7 weeks ago by Vaguery

We introduce the concept of fractels for functions and discuss their analytic and algebraic properties. We also consider the representation of polynomials and analytic functions using fractels, and the consequences of these representations in numerical analysis.

fractals
algebra
representation
dynamical-systems
to-understand
define-your-terms
to-write-about
nudge
consider:fractel-type-in-Klapaucius
7 weeks ago by Vaguery

[1611.02218] Self-Similar Polygonal Tiling

7 weeks ago by Vaguery

The purpose of this paper is to give the flavor of the subject of self-similar tilings in a relatively elementary setting, and to provide a novel method for the construction of such polygonal tilings.

tiling
aperiodic-tiling
self-similarity
rather-interesting
generative-processes
dynamical-systems
to-write-about
plane-geometry
7 weeks ago by Vaguery

[1709.09325] Self-Similar Tilings of Fractal Blow-Ups

7 weeks ago by Vaguery

New tilings of certain subsets of ℝM are studied, tilings associated with fractal blow-ups of certain similitude iterated function systems (IFS). For each such IFS with attractor satisfying the open set condition, our construction produces a usually infinite family of tilings that satisfy the following properties: (1) the prototile set is finite; (2) the tilings are repetitive (quasiperiodic); (3) each family contains self-similartilings, usually infinitely many; and (4) when the IFS is rigid in an appropriate sense, the tiling has no non-trivial symmetry; in particular the tiling is non-periodic.

fractals
IFS
rather-interesting
tiling
dynamical-systems
aperiodic-tiling
representation
to-understand
to-write-about
7 weeks ago by Vaguery

[1709.02171] On the stability and instability of finite dynamical systems with prescribed interaction graphs

8 weeks ago by Vaguery

The dynamical properties of finite dynamical systems (FDSs) have been investigated in the context of coding theoretic problems, such as network coding, and in the context of hat games, such as the guessing game and Winkler's hat game. The instability of an FDS is the minimum Hamming distance between a state and its image under the FDS, while the stability is the minimum of the reciprocal of the Hamming distance; they are both directly related to Winkler's hat game. In this paper, we study the value of the (in)stability of FDSs with prescribed interaction graphs. The first main contribution of this paper is the study of the maximum stability for interaction graphs with a loop on each vertex. We determine the maximum (in)stability for large enough alphabets and also prove some lower bounds for the Boolean alphabet. We also compare the maximum stability for arbitrary functions compared to monotone functions only. The second main contribution of the paper is the study of the average (in)stability of FDSs with a given interaction graph. We show that the average stability tends to zero with high alphabets, and we then investigate the average instability. In that study, we give bounds on the number of FDSs with positive instability (i.e fixed point free functions). We then conjecture that all non-acyclic graphs will have an average instability which does not tend to zero when the alphabet is large. We prove this conjecture for some classes of graphs, including cycles.

boolean-networks
cellular-automata
automata
combinatorics
graph-theory
representation
complexology
dynamical-systems
to-write
to-cartoon-about
8 weeks ago by Vaguery

**related tags**

Copy this bookmark: