1,722,828 research outputs found
A Linear Upper Bound on the Weisfeiler-Leman Dimension of Graphs of Bounded Genus (Track B: Automata, Logic, Semantics, and Theory of Programming)
Full text linkThe Weisfeiler-Leman (WL) dimension of a graph is a measure for the inherent descriptive complexity of the graph. While originally derived from a combinatorial graph isomorphism test called the Weisfeiler-Leman algorithm, the WL dimension can also be characterised in terms of the number of variables that is required to describe the graph up to isomorphism in first-order logic with counting quantifiers.
It is known that the WL dimension is upper-bounded for all graphs that exclude some fixed graph as a minor [M. Grohe, 2017]. However, the bounds that can be derived from this general result are astronomic. Only recently, it was proved that the WL dimension of planar graphs is at most 3 [S. Kiefer et al., 2017].
In this paper, we prove that the WL dimension of graphs embeddable in a surface of Euler genus g is at most 4g+3. For the WL dimension of graphs embeddable in an orientable surface of Euler genus g, our approach yields an upper bound of 2g + 3
Infinite Probabilistic Databases
Full text linkProbabilistic databases (PDBs) are used to model uncertainty in data in a quantitative way. In the standard formal framework, PDBs are finite probability spaces over relational database instances. It has been argued convincingly that this is not compatible with an open-world semantics (Ceylan et al., KR 2016) and with application scenarios that are modeled by continuous probability distributions (Dalvi et al., CACM 2009).
We recently introduced a model of PDBs as infinite probability spaces that addresses these issues (Grohe and Lindner, PODS 2019). While that work was mainly concerned with countably infinite probability spaces, our focus here is on uncountable spaces. Such an extension is necessary to model typical continuous probability distributions that appear in many applications. However, an extension beyond countable probability spaces raises nontrivial foundational issues concerned with the measurability of events and queries and ultimately with the question whether queries have a well-defined semantics.
It turns out that so-called finite point processes are the appropriate model from probability theory for dealing with probabilistic databases. This model allows us to construct suitable (uncountable) probability spaces of database instances in a systematic way. Our main technical results are measurability statements for relational algebra queries as well as aggregate queries and Datalog queries
The Parameterized Complexity of Learning Monadic Second-Order Logic
Full text linkWithin the model-theoretic framework for supervised learning introduced by Grohe and Turán (TOCS 2004), we study the parameterized complexity of learning concepts definable in monadic second-order logic (MSO). We show that the problem of learning an MSO-definable concept from a training sequence of labeled examples is fixed-parameter tractable on graphs of bounded clique-width, and that it is hard for the parameterized complexity class para-NP on general graphs.
It turns out that an important distinction to be made is between 1-dimensional and higher-dimensional concepts, where the instances of a k-dimensional concept are k-tuples of vertices of a graph. For the higher-dimensional case, we give a learning algorithm that is fixed-parameter tractable in the size of the graph, but not in the size of the training sequence, and we give a hardness result showing that this is optimal. By comparison, in the 1-dimensional case, we obtain an algorithm that is fixed-parameter tractable in both
Analysis of GROHE Baltic representation's marketing communications
No full textMaģistra darbs ar nosaukumu – „Grohe Baltijas pārstāvniecības mārketinga komunikāciju analīze” ir izstrādāts, balstoties uz teorētisko literatūru par mārketinga komunikācijām: to instrumentiem, plānošanas vadlīnijām un integrācijas iespējām. Darbā tiek analizētas uzņēmuma „Grohe” Baltijas pārstāvniecības mārketinga komunikācijas ar mērķi noteikt pielietoto mārketinga komunikācijas instrumentu lietderīgumu un izstrādāt iespējamos uzlabošanas virzienus. Rezultātu iegūšanai tika izmantoti pieejami uzņēmuma sekundārie dati, kā arī pētniecības metodes: daļēji strukturētā intervija un kvalitatīvā kontentanalīze. Darbā iegūtie rezultāti kļuva par pamatu pārstāvniecības mārketinga komunikāciju plānošanas procesa pārskatam un uzlabošanas risinājumu piedāvājumam.The master’s thesis titled “Analysis of Grohe Baltic representation's marketing communications” has been developed on the basis of theoretical literature on marketing communications: their tools, planning guidelines and integration possibilities. Marketing communications of the “Grohe” representation in the Baltic States have been analysed within this thesis aimed at determination of the usefulness of the marketing communication tools and development of the possible directions for improvement. Available secondary data of the company were used for the achievement of results, as well as research methods: partially structured interview and the quality content analysis. Results acquired within this thesis became basis for the review of the planning process of marketing communications of the representation and offer of the improvement solutions
Colour Refinement: A Simple Partitioning Algorithm with Applications From Graph Isomorphism Testing to Machine Learning (Invited Talk)
Full text linkColour refinement is a simple algorithm that partitions the vertices
of a graph according their "iterated degree sequence." It has very efficient implementations, running in quasilinear time, and a surprisingly wide range of applications. The algorithm has been designed in the context of graph isomorphism testing, and it is used an important subroutine in almost all practical graph isomorphism tools. Somewhat surprisingly, other applications in machine learning, probabilistic inference, and linear programming have surfaced recently.
In the first part of my talk, I will introduce the basic algorithm as well as higher dimensional extensions known as the k-dimensional Weisfeiler-Lehman algorithm. I will also discuss an unexpected connection between colour refinement and a natural linear programming approach to graph isomorphism testing. In the second part of my talk, I will discuss various applications of colour refinement
Symmetry and Similarity (Invited Talk)
No full textDeciding if two graphs are isomorphic, or equivalently, computing the symmetries of a graph, is a fundamental algorithmic problem. It has many interesting applications, and it is one of the few natural problems in the class NP whose complexity status is still unresolved. Three years ago, Babai (STOC 2016) gave a quasi-polynomial time isomorphism algorithm. Despite of this breakthrough, the question for a polynomial algorithm remains wide open.
Related to the isomorphism problem is the problem of determining the similarity between graphs. Variations of this problems are known as robust graph isomorphism or graph matching (the latter in the machine learning and computer vision literature). This problem is significantly harder than the isomorphism problem, both from a complexity theoretical and from a practical point of view, but for many applications it is the more relevant problem.
My talk will be a survey of recent progress on the isomorphism and on the similarity problem. I will focus on generic algorithmic strategies (as opposed to algorithms tailored towards specific graph classes) that have proved to be useful and interesting in various context, both theoretical and practical
Santa Caterina da Siena, san Josemaría Escrivá e l’“apostolato dell’opinione pubblica” / Saint Catherine of Siena, Saint Josemaría Escrivá and “apostolate of public opinion”
No full textThe article presents the veneration -dating back to the thirties- that Saint Josemaría had for Saint Catherine of Siena. It shows the knowledge that Saint Josemaría had of the works of the saint, and historical circumstances of the time -within the Church, and specifically, in Opus Dei- which culminated in her being named intercessor for the apostolate carried out in the area of public opinion, in 1964. The author has investigated about the search for a relic of the saint and the choice of adequate iconography
A Deep Dive into the Weisfeiler-Leman Algorithm (Invited Talk)
No full textThe Weisfeiler-Leman algorithm is a well-known combinatorial graph isomorphism test going back to work of Weisfeiler and Leman in the late 1960s. The algorithm has a surprising number of seemingly unrelated characterisations in terms of logic, algebra, linear and semi-definite programming, and graph homomorphisms. Due to its simplicity and efficiency, it is an important subroutine of all modern graph isomorphism tools. In recent years, further applications in linear optimisation, probabilistic inference, and machine learning have surfaced.
In my talk, I will introduce the Weisfeiler-Leman algorithm and some extensions. I will discuss its expressiveness and the various characterisations, and I will speak about its applications
- …
