Programme:
The workshop is mainly composed of invited lectures by guests and members of our Department of Theoretical Computer Science
for broader audience about current research trends, new interesting
results, and key open problems, providing a deeper insight into the
fields traditionally studied at our department including non-classical
logics, algebraic logic, extremal graph theory, neural networks, number
theory, which is enriched with a popular talk by a special guest on a
linguistic topic. The technical programme should inspire the
participants in their own research and lead to informal scientific
discussions that are an integral part of the workshop. Moreover, if you
have any interesting topics that can be shared with department members
please do not hesitate to send an annotation of your contribution to
Jirka Šíma (sima@cs.cas.cz).
Graph Neural Networks (GNNs) are effective models for representation
learning on relational data. Recently, their expressive power has been
characterized in terms of logic. The proof of this result employs the
fact that the computation process captured by GNNs follows tightly the
Weisfeiler-Leman algorithm (introduced as a heuristic for the graph
isomorphism problem). In the talk, I will survey these results and my
motivation to study them.
In the presentation, we will show some applications of Bernoulli numbers
in the number theory, from the sum of arithmetic sequences, through the
Fermat last theorem, Riemann's zeta function and the p-adic analysis.
Just as the real numbers arise as a completion of the space of the
rational numbers, around two decades ago, Benjamini and Schramm and
Borgs, Chayes, Lovász, Sós, Szegedy, and Vesztergombi worked out two
alternative completions of the space of finite graphs. Hence, in these
two respective theories, certain limit objects are assigned to
convergent sequences of graphs. This limit view allows to introduce
tools from mathematical analysis to the study of finite graphs, and has
led to breakthroughs in extremal graph theory and random graphs. I will
survey these basic concepts.
In
the overwhelming majority of contributions to multiagent epistemic,
doxastic, and coalition logic, a group is reduced to its extension,
i.e., the set of its members. This has a counterintuitive consequence
that groups change identity when their membership changes, and rules out
uncertainty regarding who is a member of a given group. Additionally,
this idealization does not reflect the structure of groups, or the
structured way in which collective epistemic attitudes emerge, in the
intended application of logical models.
We will outline an abstract framework in which we can indeed lift this
idealisation, namely replacing agent or group labels of epistemic
modalities with names, or providing them with an algebraic structure
relevant to types of collective epistemic attitudes in question.
(Joint work with Zoé Christoff, Olivier Roy, and Igor Sedlár.)
In many situations (e.g., when analyzing fictional discourse or building
predicate modal logic with variable domains of individuals in possible
worlds) it is advantageous to be able to deal with terms referring to
non-existent objects. Although the philosophy of non-existence has been
systematically developed ever since its exploration by the 19th century
thinker Alexius Meinong, the logical treatment of non-existent
referents, constituting so-called "free logic", is far from settled. I
will discuss the main approaches to free logic, point out some of its
problems, and sketch a system under development that aims to accommodate
indeterminate as well as contradictory properties of non-existent
objects.
A recurrent theme in mathematics is that spaces are profitably
understood in terms of some associated algebraic structures. Conversely,
abstract algebraic structures can be given a concrete interpretation as
algebras of continuous functions on a space. We show how to set up such
connections between algebraic and topological structures, focusing on
examples which arise in algebraic logic.
12:15 lunch
14:00 informal scientific discussions of project and working groups
This talk will
deal with examples of loanwords adopted into Czech from English and
vice versa. Based on this, some general conclusions will be drawn about
the role of loanwords in (any) language. The talk will be given in
English and will be generally comprehensible in this language even
without any knowledge of Czech, although some command of Czech could be
advantageous for detailed understanding.
The Brown-Erdős-Sós conjecture is a long-standing problem in extremal
(hyper-)graph theory, closely linked to Szemerédi's theorem on
arithmetic progressions. It goes back to 1973 but we still very far from
the complete solution. I will survey some new developments in this area
based on my recent work with Asaf Shapira.
Turán's theorem, considered as the foundation of extremal graph theory,
gives a tight lower bound on the number of edges a graph should have to
ensure it contains a clique of order r>2. This theorem has been
generalised by Erdős and Stone when the clique is replaced by any fixed
non-bipartite graph. The same question when we consider the containment
of a bipartite graph is still wide open. For trees, Erdős and Sós
conjectured that any graph with more than (k-1)n/2 edges contains any
tree of order k+1. In the talk I will present a result implying the
asymptotic version of the Erdős-Sós Conjecture when k is linear in n.
In
1932 Kolmogorov presented an interesting interpretation of
intuitionistic logic. According to this interpretation, formulas of the
formal language do not represent forms of statements but rather forms of
problems and valid formulas represent those forms of problems for which
there is a uniform solution of all their instances. Later on this idea
was made more precise and it was transformed into a well-defined
semantics but it turned out that the resulting logic is not
intuitionistic but intermediate between intuitionistic and classical
logic. There are some interesting results related to this logic but also
several interesting open questions. In my talk I will explain the
intuitive idea behind the logic of problems and provide a brief overview
of this research area.
Weighted programs are a recent generalization of probabilistic programs which can also be used to represent optimization problems and, in general, programs whose execution
traces carry some sort of weight. In this talk, I give a brief introduction to weighted programs and I outline my recent work on Kleene algebra for weighted programs.
12:30 lunch
14:00 departure by bus from Šámalova cottage
15:30 arrival at the Institute of Computer Science, Prague
Registration: The deadline for
registration has closed (about 30 registered participants) but there is a
possibility of a few more available places.
Please contact Katka Vacková via email (vackova@cs.cas.cz) if you want to attend.
Registration Fee:
6 000 CZK per person including accommodation, food, and transport by a small bus.
