Seminar talks fall 2022
Talks during the fall term 2022
Wed 7.9.2022 12-14, Zoom
Miguel Moreno: Indestructibility and characterization of filter reflection
Abstract: Filter reflection is a natural generalization of the stationary reflection. It was introduced by Fernandes-Moreno-Rinot when studying the generalized-Borel-reducibility. It was shown that it has deep implications in the generalized Baire space and Cantor space. It is known that filter reflection is independent from ZFC, it doesn't require large cardinals, and it is consistent that filter reflection holds at any uncountable regular cardinal. In this talk we will go through some recent results about filter reflection, including indestructibility results. We will also show that filter reflection is equivalent to the existence of continuous reductions in the generalized Baire spaces.
Wed 14.9.2022 14-16, Zoom PLEASE NOTE TIME CHANGE
Andres Villaveces
Around Definability in AECs: Logics and Patterns
Abstract: Definability in Abstract Elementary Classes has been both central and elusive. The possibility itself of the development of a good stability theory (now solidly established) was made possible early by the Shelah Presentation Theorem. Yet, in spite of the centrality of this theorem for the start of the theory, definability questions were never at the center of the model theory of AECs, at least not in a direct way. Later, results by Kueker et al. started capturing better definitions (not second order) of some AECs. In 2020, with Saharon Shelah, we provided a way to define arbitrary AECs with no expansion of the vocabulary. Leung improved the bound of the logic, at the expense of an infinitary game quantifier. We later improved Leung's bound, removing the use of that game quantifier. More recently, in joint work with Nájar, we have started doing classification theory using our newly gained definability; recasting older results and capturing issues around definability of types. I will discuss this line of research, as well as possible connections with Hrushovski's recent work on "definability patterns" aimed at balancing the Galois theory of (first order) model theory.
Wed 21.9.2022 12-14, C124
Matilda Häggblom
Title: Axiomatizing modal inclusion logic
Abstract: Modal inclusion logic is team-based modal logic extended with inclusion atoms. The talk will cover the main result of my master's thesis: A complete axiomatization of modal inclusion logic. We begin by recalling that modal inclusion logic is expressively complete for classes that have the empty team property, are closed under unions and closed under k-bisimulation for some k. Through the expressive completeness proof, we obtain a normal form for the logic. In the talk, we suggest a simplified version of the normal form compered to the one currently in the literature. We then introduce a natural deduction proof system and show completeness using the normal form.
Wed 28.9.2022 12-14, C124
cancelled
Wed 5.10.2022 12-14, C124 ONLINE (Zoom)
Tuomas Hakoniemi: Ideal Refutations of Knapsack Contradictions
Abstract: The Ideal Proof System (IPS), introduced by Grochow and Pitassi, is a strong algebraic proof system with close connections to central questions in algebraic circuit complexity. In this talk we present superpolynomial lower bounds in a constant-depth subsystem of IPS for a variant of Knapsack. Our argument builds on the recent breakthrough lower bounds for constant-depth algebraic circuits by Limaye, Srinivasan and Tavenas.
This talk is based on joint work with Nashlen Govindasamy and Iddo Tzameret.
Wed 12.10.2022 14-16, Zoom
Jouko Väänänen: Inner models from extended logics Slides of the talk
Abstract:
If we replace first order logic by second order logic in the
original definition of Gödel's inner model L, we obtain HOD. In this
talk we consider inner models that arise if we replace first order
logic by a logic that has some, but not all, of the strength of
second order logic. Typical examples are the extensions of first
order logic by generalized quantifiers, such as the Magidor-Malitz
quantifier, the cofinality quantifier, or stationary logic. It can
be shown that both L and HOD manifest some amount of formalism
freeness in the sense that they are not very sensitive to the choice
of the underlying logic.
On the other hand, the cofinality quantifier gives rise to a new
robust inner model between L and HOD. Assuming a proper class of
Woodin cardinals the regular cardinals above aleph-1 of V are weakly
compact in the inner model arising from the cofinality quantifier
and the theory of that model is (set) forcing absolute and
independent of the cofinality in question. Assuming three Woodin
cardinals and a measurable above them, if the construction is
relativized to a real, then on a cone of reals the Continuum
Hypothesis is true in the relativized model.
A potentially bigger inner model C(aa) arises from stationary logic.
Assuming a proper class of Woodin cardinals, or alternatively MM-
plus-plus, the regular uncountable cardinals of V are measurable in
the inner model C(aa), the theory of C(aa) is (set) forcing
absolute, and C(aa) satisfies CH. We introduce an auxiliary concept
that we call club determinacy, which simplifies the construction of
C(aa) greatly but may have also independent interest. Based on club
determinacy, we introduce the concept of aa-mouse which we use to
prove CH and other properties of the inner model C(aa). Finally, we
discuss a delicate matter related to the Axiom of Choice in the
inner model C(aa) and in inner models of the same kind.
This is joint work with Juliette Kennedy and Menachem Magidor.
Wed 19.10.2022 12-14, C124
Davide Quadrellaro: Weak Dependence Logic
Abstract: We introduce and study a fragment of dependence logic which we call weak dependence logic. The interest in this fragment lays in the fact that, although it is much less expressive than full dependence logic, it has three desirable features:
a strong form of compactness;
(ii) the De Jongh property w.r.t. propositional dependence logic;
(iii) it admits a notion of model-theoretic type which gives rise to Esakia spaces.
We show these properties and establish connections to the algebraic and topological semantics of propositional dependence logic.
Wed 26.10.2022 12-14, C124
Exam week
Wed 2.11.2022 12-14, C124
Miika Hannula: Dependencies and information inequalities
Abstract: Dependence and independence can be interpreted as inequalities over Shannon entropies. In fact, basic principles about dependencies are already at work at the more abstract level of polymatroids, which encapsulate the elementary properties of the entropy function. In this talk we investigate these connections and survey some basic facts about information-theoretic inequalities.
Wed 9.11.2022 12-14, C124 + Zoom (hybrid)
Vadim Weinstein: BLURRY FILTERS AND CLASSIFICATION BY COUNTABLE STRUCTURES
(Joint work with Martina Iannella)
Abstract: The Stone duality gives a neat way to go back-and-forth between totally disconnected Polish spaces and countable Boolean algebras. The main ingredient is the Stone space of all ultrafilters on a Boolean algebra. In this talk we introduce a weaker concept which we call the “blurry filter”. Using blurry filters instead of ultrafilters enables one to extend the class of spaces under consideration from totally disconnected ones to a larger class. As an application of this method, we show that the following are completely classifiable by countable structures: the homeomorphism on 3-manifolds (also applicable to 2-manifolds; but this was known since 1971), and wild embeddings of Cantor sets in R³. By "classification" in this talk we mean classical Borel-reducibility.
Wed 16.11.2022 12-14, C124
Tobias Boege: Incidence geometry, conditional independence and the existential theory of the reals
Abstract: Deciding whether a system of polynomial equations and inequalities has a solution over the real numbers is a basic task in computational geometry, optimization and algebraic statistics. Under polynomial-time many-one reductions, this problem generates the complexity class $\exists\mathbb{R}$. I will briefly recall a geometric technique, due to von Staudt, for obtaining completeness results for this complexity class and apply it to the implication problem for conditional independence among jointly normal random variables.
Wed 23.11.2022 12-14, C124 + Zoom (hybrid)
Balthasar Grabmayr
Title: Fixing Montague's Problem
Abstract: Turing machines only operate directly on strings. Turing computation over any other domain therefore requires a notation system for the domain. Ever since Montague's (1960) observation that different notation systems in general yield different notions of Turing computability, the task of distinguishing those notation systems that are admissible for computation from those that are not continues to be a much debated and open problem in the philosophy of computation. In the first part of this talk, I will introduce a generalized version of Montague's problem. In the second part, I will formulate and defend a solution to this problem.
Wed 30.11.2022 12-14, C124
Miika Hannula: Dependencies and information inequalities II
Abstract: Linear inequalities over joint entropies of finitely distributed random variables (called information inequalities) are often characterized as the laws of information theory. Unfortunately, verifying such laws is not an easy task. The information inequality problem (IIP), which is to decide whether a given information inequality is valid, is only known to be co-recursively enumerable. The conditional variant of this problem is undecidable, as a direct corollary of a recent undecidability result for the implication problem of conditional independence over random variables.
In this talk we are interested in approximating IIP. For instance, as every entropic function is a polymatroid, one obtains a sound approximation of IIP by considering the validity of information inequalities over polymatroids. This problem can be decided in exponential time through linear programming, but the exact complexity seems to be unknown. The aim of this talk is to locate some tractability boundaries for sound (or complete) approximation of IIP.
Wed 7.12.2022 12-14, C124
Aleksi Anttila: A remark on the dual negation in propositional/modal team semantics
Wed 14.12.2022 12-14, C124
12-13
Nina Pardal: An epistemic approach to model uncertainty in data-graphs
Abstract:
Graph databases are becoming widely successful as data models that allow to effectively represent and process complex relationships among various types of data. Data-graphs are particular types of graph databases whose representation allows both data values in the paths and in the nodes to be treated as first class citizens by the query language.
As with any other type of data repository, data-graphs may suffer from errors and discrepancies with respect to the real-world data they intend to represent.
In this talk, we explore the notion of probabilistic unclean data-graphs, in order to capture the idea that the observed (unclean) data-graph is actually the noisy version of a clean one that correctly models the world, but that we know of partially.
As the factors that yield to such observation may be the result of different types of clerical errors or unintended transformations of the data, and depend heavily on the application domain, we consider an epistemic probabilistic model that describes the distribution over all possible ways inwhich the clean (uncertain) data-graph could have been polluted.
Based on this model we define and study data cleaning and probabilistic query answering for this framework, yielding complexity results when the transformation of the data-graph can be caused by either removing (subset), adding (superset), or modifying (update) nodes and edges.
13-14
Timon Barlag: Logical Characterizations of Algebraic Circuit Classes over Rings
Abstract:
We present an adapted construction of algebraic circuits over rings introduced by Blum, Shub and Smale to arbitrary integral domains and generalize the AC$_R$-classes for this setting. For integral domains we give a theorem in the style of Immerman's Theorem and show that families of such circuits of polynomial size and constant depth decide exactly those sets of vectors of ring elements that can be defined in first-order logic on R-structures as a generalization of $\mathbb{R}$-structures in the sense of Cucker and Meer.
Additionally, we discuss a generalization of the guarded predicative logic by Durand, Haak and Vollmer and we show characterizations for the AC$_R$ and NC$_R$ hierarchy.
Furthermore, we compare some of the aforementioned complexity classes with special underlying rings and give a conjecture about which inclusions of classes could be strict.