Finding suitable embeddings for connectomes (spatially embedded complex networks that map neural connections in the brain) is crucial for analyzing and understanding cognitive processes. Recent studies have found two-dimensional hyperbolic embeddings superior to Euclidean embeddings in modeling connectomes across species, especially human connectomes. However, those studies had limitations: geometries other than Euclidean, hyperbolic, or spherical were not considered. Following William Thurston’s suggestion that the networks of neurons in the brain could be successfully represented in Solv geometry, we study the goodness-of-fit of the embeddings for 21 connectome networks (8 species). To this end, we suggest an embedding algorithm based on Simulating Annealing that allows us to embed connectomes to Euclidean, Spherical, Hyperbolic, Solv, Nil, and product geometries. Our algorithm tends to find better embeddings than the state-of-the-art, even in the hyperbolic case. Our findings suggest that while three-dimensional hyperbolic embeddings yield the best results in many cases, Solv embeddings perform reasonably well.

Self-Organizing Maps (SOMs, Kohonen networks) belong to neural network models of the unsupervised class. In this paper, we present the generalized setup for non-Euclidean SOMs. Most data analysts take it for granted to use some subregions of a flat space as their data model; however, by the assumption that the underlying geometry is non-Euclidean we obtain a new degree of freedom for the techniques that translate the similarities into spatial neighborhood relationships. We improve the traditional SOM algorithm by introducing topology-related extensions. Our proposition can be successfully applied to dimension reduction, clustering or finding similarities in big data (both hierarchical and non-hierarchical).

The hyperbolic random graph model (HRG) has proven useful in the analysis of scale-free networks, which are ubiquitous in many fields, from social network analysis to biology. However, working with this model is algorithmically and conceptually challenging because of the nature of the distances in the hyperbolic plane. In this paper, we propose a discrete variant of the HRG model where nodes are mapped to the vertices of a triangulation; our algorithms allow us to work with this model in a simple yet efficient way. We present experimental results conducted on networks, both real-world and simulated, to evaluate the practical benefits of DHRG in comparison to the HRG model.

We construct a first-order formula φ such that all finite models of φ are non-narrow rectangular grids without using any binary relations other than the grid neighborship relations. As a corollary, we prove that a set A ⊆ ℕ is a spectrum of a formula which has only planar models if numbers n ∈ A can be recognized by a non-deterministic Turing machine (or a one-dimensional cellular automaton) in time t(n) and space s(n), where t(n)s(n) ≤ n and t(n); s(n) = Ω(log(n)).

Gossip protocols deal with a group of communicating agents, each holding a private information, and aim at arriving at a situation in which all the agents know each other secrets. Distributed epistemic gossip protocols are particularly simple distributed programs that use formulas from an epistemic logic. Recently, the implementability of these distributed protocols was established (which means that the evaluation of these formulas is decidable), and the problems of their partial correctness and termination were shown to be decidable, but their exact computational complexity was left open. We show that for any monotonic type of calls the implementability of a distributed epistemic gossip protocol is a P^{NP}_{||}-complete problem, while the problems of its partial correctness and termination are in coNP^{NP}.

We present the semantics of an imperative programming language called LOIS (Looping Over Infinite Sets), which allows iterating through certain infinite sets, in finite time. Our semantics intuitively correspond to execution of infinitely many threads in parallel. This allows to merge the power of abstract mathematical constructions into imperative programming. Infinite sets are internally represented using first order formulas over some underlying logical structure, and SMT solvers are employed to evaluate programs.

This paper is an introduction to the computational complexity theory. I believe that the standard courses in complexity theory make some things much more important than they really are, while things which I find extremely interesting are marginalized. Thus, it can be seen as my subjective view on what is important and interesting in computational complexity, and what is not. We state the basic facts from computational complexity theory using the blackboard computations (one-dimensional cellular automata) as the standard computation model; we argue the benefits of such approach. This article is somewhat based on my series of talks from Warsztaty Logiczne 2014 in Białka Tatrzańska, although these talks covered more topics, such as NL=coNL, and links between BPP and the polynomial hierarchy.

The finite spectrum of a first-order sentence is the set of positive integers that are the sizes of its models. The class of finite spectra is known to be the same as the complexity class NE. We consider the spectra obtained by limiting models to be either planar (in the graph-theoretic sense) or by bounding the degree of elements. We show that the class of such spectra is still surprisingly rich by establishing that significant fragments of NE are included among them. At the same time, we establish non-trivial upper bounds showing that not all sets in NE are obtained as planar or bounded-degree spectra.

Context-free languages allow one to express data with hierarchical structure, at the cost of losing some of the useful properties of languages recognized by finite automata on words. However, it is possible to restore some of these properties by making the structure of the tree visible, such as is done by visibly pushdown languages, or finite automata on trees. In this paper, we show that the structure given by such approaches remains invisible when it is read by a finite automaton (on word). In particular, we show that separability with a regular language is undecidable for visibly pushdown languages, just as it is undecidable for general context-free languages.

First-order definable structures with atoms are infinite, but exhibit enough symmetry to be effectively manipulated. We study Constraint Satisfaction Problems (CSPs) where both the instance and the template are definable structures with atoms. As an initial step, we consider locally finite templates, which contain potentially infinitely many finite relations. We argue that such templates occur naturally in Descriptive Complexity Theory. We study CSPs over such templates for both finite and infinite, definable instances. In the latter case even decidability is not obvious, and to prove it we apply results from topological dynamics. For finite instances, we show that some central results from the classical algebraic theory of CSPs still hold: the complexity is determined by polymorphisms of the template, and the existence of certain polymorphisms, such as majority or Maltsev polymorphisms, guarantees the correctness of classical algorithms for solving finite CSP instances.

We consider sequences of vectors from ℕ d . Each coordinate of a vector can be reset or incremented by 1 with respect to the same coordinate of the preceding vector. We give an example of non-dominating sequence, like in Dickson’s Lemma, of length 2 2 θ( n) , what matches the previously known upper bound.

The spectrum of a first-order logic sentence is the set of natural numbers that are cardinalities of its finite models. In this paper we show that when restricted to using only two variables, but allowing counting quantifiers, the class of spectra of first-order logic sentences is exactly the class of semilinear sets and, hence, closed under complement. At the heart of our proof are semilinear characterizations for the existence of regular and biregular graphs, the class of graphs in which there are a priori bounds on the degrees of the vertices. Our proof also provides a simple characterization of models of two-variable logic with counting---that is, up to renaming and extending the relation names, they are simply a collection of regular and biregular graphs.

The spectrum of a first-order logic sentence is the set of natural numbers that are cardinalities of its finite models. In this article, we study the hierarchy of first-order spectra based on the number of variables. It has been conjectured that it collapses to three variables. We show the opposite: it forms an infinite hierarchy. However, despite the fact that more variables can express more spectra, we show that to establish whether the class of first-order spectra is closed under complement, it is sufficient to consider sentences using only three variables and binary relations.

We study the problem of acute triangulations of convex polyhedra and the space ℜn. Here an acute triangulation is a triangulation into simplices whose dihedral angles are acute. We prove that acute triangulations of the n-cube do not exist for n ≥ 4. Further, we prove that acute triangulations of the space ℜn do not exist for n ≥ 5. In the opposite direction, in ℜ3 we construct nontrivial acute triangulations of all Platonic solids. We also prove nonexistence of an acute triangulation of ℜ4 if all dihedral angles are bounded away from ϒ/2.

Parikh’s Theorem states that semilinear sets are effectively equivalent with the Parikh images of regular languages and those of context-free languages. In this paper, we study the complexity of Parikh’s Theorem over any fixed alphabet size d. We prove various normal form the oremsin the case of NFAs and CFGs. In particular, the normalform theorems ensure that a union of linear sets with dgenerators suffice to express such Parikh images, which in the case of NFAs can further be computed in polynomial time. We then apply apply our results to derive: (1) optimal complexity for decision problems concerning Parikh images(e.g. membership, universality, equivalence, and disjointness), (2) a new polynomial fragment of integer programming, (3) an answer to an open question about PAC-learnability of semilinear sets, and (4) an optimal algorithm for verifying LTL over discrete-timed reversal-bounded counter systems.