Seminar - XWiki

= (% style="color:#000000" %)Logic Seminar(%%) =

(% style="color:#000000" %)The Logic seminar is held on Wednesdays, usually at 12-14. During the fall 2023 we will have both on-site and online talks, and we try to keep the page updated on when we have which kind.

7

8

9

(% style="color:#000000" %)The permanent Zoom room for the seminar is: (%%)[[https:~~/~~/helsinki.zoom.us/j/62891400777?pwd=UldCeThTaTJVQjUzUFo4S2ErcndNQT09>>url:https://helsinki.zoom.us/j/62891400777?pwd=UldCeThTaTJVQjUzUFo4S2ErcndNQT09||shape="rect" class="moz-txt-link-freetext"]] (Meeting ID: 628 9140 0777, Passcode: 164195)

10

11

(% style="color:#ff0000" %)**PLEASE NOTE**(% style="color:#000000" %)**: Due to the prevalence of zoom talks given by scholars based in various time zones, the times that the seminar meets will occasionally change from the usual 12-14 slot. **Also, if not separately specified, the talks always start at a quarter past.

12

13

14

(% style="color:#000000" %)The seminar is led by prof. Juha Kontinen and Ulla Karhumäki.

15

16

== Schedule of the spring term 2024 ==

(% class="p3" %)

**Wed 17.01.2024 12-14, C124**

21

22

(% class="p3" %)

23

**Miguel Moreno: **On the Borel reducibility Main Gap

24

25

One of the biggest motivations in Generalized Descriptive Set Theory has been the program of identifying counterparts of classification theory in the setting of Borel reducibility. The most important has been the division line classifiable vs non-classifiable, i.e. identify Shelah's Main Gap in the Borel reducibility hierarchy. This was studied by Friedman, Hyttinen and Weinstein (ne Kulikov) in their book "Generalized descriptive set theory and classification theory". Their work led them to conjecture the following:

26

27

If T is a classifiable theory and T' is a non-classifiable theory, then the isomorphism relation of T is Borel reducible to the isomorphism relation of T'.

28

29

In this talk we will prove this conjecture, discuss the objects introduced, and provide a detailed overview of the gaps between classifiable shallow theories, classifiable non-shallow theories, and non-classifiable theories. The main result that will be presented is the following:

30

31

Suppose \kappa=\lambda^+=2^\lambda, 2^c \leq \lambda = \lambda^{\omega_1} and T_1 and T_2 are countable complete first-order theories in a countable vocabulary.

32

33

If T_1 is a classifiable theory and T_2 is a non-classifiable theory, then the isomorphism relation of T_1 is continuously reducible to the isomorphism relation of T_2, and the isomorphism relation of T_2 is strictly above the isomorphism relation of T_1 in the Borel reducibility hierarchy.

34

35

This talk will be based on the article Shelah's Main Gap and the generalized Borel-reducibility ([[https:~~/~~/arxiv.org/abs/2308.07510>>url:https://arxiv.org/abs/2308.07510]]

(% class="p3" %)

**Wed 24.01.2024 12-14, C124**

40

41

(% class="p3" %)

42

**Miguel Moreno: **On the Borel reducibility Main Gap (continuation of last week)

43

44

One of the biggest motivations in Generalized Descriptive Set Theory has been the program of identifying counterparts of classification theory in the setting of Borel reducibility. The most important has been the division line classifiable vs non-classifiable, i.e. identify Shelah's Main Gap in the Borel reducibility hierarchy. This was studied by Friedman, Hyttinen and Weinstein (ne Kulikov) in their book "Generalized descriptive set theory and classification theory". Their work led them to conjecture the following:

45

46

If T is a classifiable theory and T' is a non-classifiable theory, then the isomorphism relation of T is Borel reducible to the isomorphism relation of T'.

47

48

In this talk we will prove this conjecture, discuss the objects introduced, and provide a detailed overview of the gaps between classifiable shallow theories, classifiable non-shallow theories, and non-classifiable theories. The main result that will be presented is the following:

49

50

Suppose \kappa=\lambda^+=2^\lambda, 2^c \leq \lambda = \lambda^{\omega_1} and T_1 and T_2 are countable complete first-order theories in a countable vocabulary.

51

52

If T_1 is a classifiable theory and T_2 is a non-classifiable theory, then the isomorphism relation of T_1 is continuously reducible to the isomorphism relation of T_2, and the isomorphism relation of T_2 is strictly above the isomorphism relation of T_1 in the Borel reducibility hierarchy.

53

54

This talk will be based on the article Shelah's Main Gap and the generalized Borel-reducibility ([[https:~~/~~/arxiv.org/abs/2308.07510>>url:https://arxiv.org/abs/2308.07510]]

(% class="p3" %)

**Wed 31.01.2024 12-14, C124**

59

60

(% class="p3" %)

61

**Teemu Hankala: **From Neural Network Training to Tarski's Exponential Function Problem

62

63

For simple network architectures, the weights and biases of a neural network can be trained to optimal values in polynomial time. However, in a general setting the decision variant of the training problem is known to be NP-hard, and gradient descent is often used in the training phase. In 2021 it was shown by Abrahamsen, Kleist and Miltzow that the training problem with piecewise algebraic activation functions is polynomial-time reducible to the satisfiability problem of the existential theory of the real numbers and, in addition, that it is polynomial-time bireducible to this satisfiability problem even if restricted to the identity activation function. In this talk, the connection between neural network training and real numbers is extended to arbitrary activation functions. In particular, the standard logistic function leads to a training problem that is polynomial-time equivalent to Tarski's exponential function problem, whereas neural activations using the sine function lead to undecidability.

64

65

This talk is based on joint work with Miika Hannula, Juha Kontinen and Jonni Virtema.

(% class="p3" %)

**Wed 07.02.2024 12-14, C124**

70

71

(% class="p3" %)

72

**Fausto Barbero: **Probabilistic counterfactuals in multiteam semantics

73

74

An appropriate generalization of multiteams can be used as semantics for probabilistic intrventionist counterfactuals, e.g. expressions of the form:

75

76

"If X were set to value x, then the probability of Y taking value y is e"

77

78

In joint works with G. Sandu and J. Virtema, we have studied the properties of languages of causal inference under this interpretation, and considered extensions with infinitary Boolean operators and with strict tensor.

79

80

On the model-theoretic side, we see that the infinitary language displays an interesting type of expressive completeness. Understanding the much less expressive finitary languages involves the identification of four classes of linear inequalities and an understanding of their geometry in simplexes. The characterization results can be sharpened into a strict hierarchy of expressivity (of the languages and, in parallel, of the classes of inequalities) and serve as a basis for undefinability results.

81

82

On the proof-theoretic side, we provide strongly complete, infinitary axiom systems for both the finitary and infinitary languages. The latter problem led us to the identification of sufficient criteria for the truth of Lindenbaum lemmas.

(% class="p3" %)

**Wed 14.02.2024 12-14, C124**

87

88

(% class="p3" %)

89

**Miika Hannula: **Query output size, entropic inequalities, and conditional independence

90

91

We consider the following problem: given an open formula over a relational vocabulary, and size bounds for relations, determine the least upper bound for the number variable assignments satisfying the formula. Even for simple logical formulae, such as conjunctive queries, this problem is non-trivial. The problem also occurs in practice, as estimating the output sizes of intermediate joins (i.e., conjunctive queries) is a critical component of the database query execution plan. Entropic inequalities, in turn, govern the laws of Shannon entropy, and in this talk we consider how these topics connect to one another.We also discuss how entropic inequalities relate to logical entailment through the notion of conditional independence, and, time permitting, explore howconditional independence generalizes in semiring semantics.

(% class="p3" %)

**Wed 21.02.2024 12-14, C124**

96

97

(% class="p3" %)

98

**Ulla Karhumäki: **Small supersimple pseudofinite groups

99

100

(% class="p3" %)

101

A simple group is pseudofinite if and only if it is isomorphic to a (twisted) Chevalley group over a pseudofinite field. This celebrated result mostly follows from the work of Wilson in 1995 and heavily relies on the classification of finite simple groups (CFSG). It easily follows that any simple pseudofinite group G has a supersimple theory and that the SU-rank of G is finite. In particular, if SU(G)=3 then G is isomorphic to PSL_2(F) for some pseudofinite field F. In this talk we discuss `small’ pseudofinite groups with supersimple theory. In particular, we will see that the classification G \cong PSL_2(F) above does not require CFSG. This is joint work with F. O. Wagner.

(% class="p3" %)

**Wed 28.02.2024, No seminar (most of the group not in Helsinki)**

(% class="p3" %)

**Wed 06.03.2024, Exam week (no seminar)**

(% class="p3" %)

**Wed 13.03.2024 12-14, No seminar (most of the group not in Helsinki)**

(% class="p3" %)

**Wed 20.03.2024 12-14, C124**

118

119

(% class="p3" %)

120

**Miguel Moreno: **On the Borel reducibility Main Gap (continuation of weeks 1-2)

121

122

One of the biggest motivations in Generalized Descriptive Set Theory has been the program of identifying counterparts of classification theory in the setting of Borel reducibility. The most important has been the division line classifiable vs non-classifiable, i.e. identify Shelah's Main Gap in the Borel reducibility hierarchy. This was studied by Friedman, Hyttinen and Weinstein (ne Kulikov) in their book "Generalized descriptive set theory and classification theory". Their work led them to conjecture the following:

123

124

If T is a classifiable theory and T' is a non-classifiable theory, then the isomorphism relation of T is Borel reducible to the isomorphism relation of T'.

125

126

In this talk we will prove this conjecture, discuss the objects introduced, and provide a detailed overview of the gaps between classifiable shallow theories, classifiable non-shallow theories, and non-classifiable theories. The main result that will be presented is the following:

127

128

Suppose \kappa=\lambda^+=2^\lambda, 2^c \leq \lambda = \lambda^{\omega_1} and T_1 and T_2 are countable complete first-order theories in a countable vocabulary.

129

130

If T_1 is a classifiable theory and T_2 is a non-classifiable theory, then the isomorphism relation of T_1 is continuously reducible to the isomorphism relation of T_2, and the isomorphism relation of T_2 is strictly above the isomorphism relation of T_1 in the Borel reducibility hierarchy.

131

132

This talk will be based on the article Shelah's Main Gap and the generalized Borel-reducibility ([[https:~~/~~/arxiv.org/abs/2308.07510>>url:https://arxiv.org/abs/2308.07510]]

(% class="p3" %)

**Wed 27.03.2024 12-14, C124**

137

138

(% class="p3" %)

139

**Minna Hirvonen**: Axiomatization of implication for probabilistic independence and unary variants of marginal identity and marginal distribution equivalence

140

141

A set of atoms S is said to logically imply another atom s if every suitable object (e.g. a database or a distribution) that satisfies all of the atoms in S also satisfies the atom s. An implication problem is the task of deciding whether a given set of atoms S logically implies another given atom s.

142

143

In this talk, we consider the implication problem for probabilistic independence and unary variants of marginal identity and marginal distribution equivalence over finite probability distributions. Two variables x and y satisfy a unary marginal identity when they are identically distributed. If the multisets of the marginal probabilities of all possible values for variables x and y are equal, the variables satisfy a unary marginal distribution equivalence. I will present a sound and complete finite axiomatization and a polynomial-time algorithm for the implication problem for probabilistic independence, unary marginal identity, and unary marginal distribution equivalence.

144

145

Slides of the talk are[[ here>>attach:Presentation.pdf]].

(% class="p3" %)

**Wed 03.04.2024, 12-14, C124**

151

152

(% class="p3" %)

153

**Kai Sauerwald: **A Semantic Perspective of AGM Belief Revision in Tarskian Logics

154

155

(% class="p3" %)

156

Changing theories according to new information minimally is axiomatically captured by the famous approach to revision from Alchourrón, Gärdenfors, and Makinson (AGM). We studied and characterized this notion of change in a very general framework on the ground of Tarskian logics semantically. Our starting point is the approach by Katsuno and Mendelzon (K&M), who provided such a characterization for propositional logic over finite signatures. We generalize K&M's approach to the setting of AGM-style revision over bases in arbitrary Tarskian logics, where base may refer to one of the various ways of representing an agent's beliefs (such as belief sets, arbitrary or finite sets of

157

sentences, or single sentences). The first result is a representation theorem providing a two-way correspondence between AGM-style revision operators and specific

158

assignments: functions associating every base to a "preference" relation over interpretations, which must be total but is - in contrast to prior approaches - not always transitive. The second contribution presented is a characterization of all Tarskian logics for which our result can be strengthened to assignments that produce transitive preference relations

159

(as in K&M's original work).

(% class="p3" %)

**Wed 10.04.2024, 12-14, C124**

164

165

(% class="p3" %)

166

**Ville Salo: **Automatic structures and some applications

167

168

We define automatic structures and discuss some of their applications in logic (Presburger arithmetic), group theory (Cayley graph (bi-)automatic groups), combinatorics on words (Thue-Morse word and the Fibonacci word) and symbolic dynamics (the domino problem and dynamics of cellular automata).

(% class="p3" %)

**Wed 17.04.2024, 12-14, C124**

173

174

(% class="p3" %)

175

**Werner Mérian: **Logical characterization of complexity classes for enumeration problems

176

\\The problems related to complexity theory most commonly studied are the so-called decision problems. They consist in deciding whether, given an input instance, a certain condition is verified or not. Most often, these problems raise the question of whether there exists a solution or not. For their part, enumeration problems are interested in enumerating all solutions. Enumeration problems have been studied in the context of computational complexity theory, and several complexity classes have been introduced for these problems (for tractable ones, we can cite EnumP, TotalP, IncP, DelayP). Our work aims to bring the mission of descriptive complexity to the world of enumeration. The ultimate goal is to successfully capture a tractable enumeration complexity class (namely IncP) with a certain logic. We will then be able to say that an enumeration problem is in this complexity class if and only if there is a formula from the logic associated to this complexity class which characterizes this problem. Our trip will lead us to study fragments of third-order logic and to capture natural enumeration problems.

(% class="p3" %)

**Wed 24.04.2024, 12-14, C124**

181

182

**Sándor Kisfaludi-Bak**: ER-completeness in geometric algorithms

183

184

Geometric algorithms often run into precision difficulties: for example, computing the total length of n segments (even when the segments have integer-coordinate endpoints) is of unknown complexity. We have discovered that several problem flavors, such as incidence, packing, visibility where the optimum output "requires" exponential precision numbers in some manner, which intuitively places them outside NP. Recently the class ER or (ETR), the existential theory of the reals arose as the natural complexity class for such continuous geometric problems. ER consists of those problems that can in polynomial time be reduced to checking if a semi-algebraic set is empty, or equivalently, to an existentially quantified Boolean formula of polynomial inequalities over the reals with integer coefficients. Today we have a wealth of problems that are ER-complete, including prominent problems such as art gallery, low-rank matrix completion, or training neural networks. During the talk I will introduce the complexity class and we will get an intuition about some of its complete problems. We will learn about how one can know (and attempt to prove) that a problem belongs there, as well as the state of the art for solving such problems.

(% class="p3" %)

**Tue 30.04.2024, 12-14, D123 (note unusual time and place)**

189

190

(% class="p3" %)

191

**Tuomas Hakoniem**i: Picking mushrooms

192

193

(% class="p3" %)

194

Proving superpolynomial lower bounds for constant depth refutations with modular counting connectives is a major open question in propositional proof complexity. In this talk we present the problem, map out a possible path towards its resolution and discuss some recent off-path discoveries along the way. This talk is based on joint works with Nashlen Govindasamy, Nutan Limaye and Iddo Tzameret.

(% class="p3" %)

**Wed 08.05.2024, Exam week (no seminar)**

**[[doc:Logic.Home.Seminar.Talks of the fall term 2023.WebHome]]**

203

204

==== [[doc:Logic.Home.Seminar.Talks of the spring term 2023.WebHome]] ====

205

206

==== [[Talks of the fall term 2022>>doc:Logic.Home.Seminar.Seminar talks fall 2022.WebHome]] ====

207

208

==== (% style="color:#000000" %)[[Talks of the spring term 2022>>doc:Logic.Home.Seminar.Seminar talks spring 2022.WebHome]](%%) ====

209

210

==== (% style="color:#000000" %)[[Talks of the fall term 2021>>doc:Logic.Home.Seminar.Seminar talks fall 2021.WebHome]](%%) ====

211

212

==== (% style="color:#000000" %)[[Talks of the spring term 2021>>doc:Logic.Home.Seminar.Seminar talks spring 2021.WebHome]](%%) ====

213

214

==== (% style="color:#000000" %)[[Talks of the fall term 2020>>url:https://wiki.helsinki.fi/display/Logic/Seminar+talks+fall+2020||shape="rect"]](%%) ====

215

216

==== (% style="color:#000000" %)[[Talks of the spring term 2020>>doc:Logic.Home.Seminar.Seminar talks spring 2020.WebHome]](%%) ====

217

218

==== (% style="color:#000000" %)[[Talks of the fall term 2019>>doc:Logic.Home.Seminar.Seminar talks fall 2019.WebHome]](%%) ====

219

220

==== (% style="color:#000000" %)[[Talks of the spring term 2019>>doc:Logic.Home.Seminar.Seminar talks spring 2019.WebHome]](%%) ====

221

222

==== (% style="color:#000000" %)Talks of the fall term 2018[[doc:Logic.Home.Seminar.Seminar talks fall 2018.WebHome]](%%) ====

223

224

==== (% style="color:#000000" %)Talks of the spring term 2018[[doc:Logic.Home.Seminar.Seminar talks spring 2018.WebHome]](%%) ====

225

226

==== (% style="color:#000000" %)Talks of the fall term 2017[[doc:Logic.Home.Seminar.Seminar talks fall 2017.WebHome]](%%) ====

227

228

==== (% style="color:#000000" %)Talks of the spring term 2017[[doc:Logic.Home.Seminar.Seminar talks spring 2017.WebHome]](%%) ====

229

230

==== (% style="color:#000000" %)Talks of the fall term 2016[[doc:Logic.Home.Seminar.Seminar talks fall 2016.WebHome]](%%) ====

231

232

==== (% style="color:#000000" %)Talks of the spring term 2016[[doc:Logic.Home.Seminar.Seminar talks spring 2016.WebHome]](%%) ====

233

234

==== (% style="color:#000000" %)Talks of the fall term 2015[[doc:Logic.Home.Seminar.Seminar talks fall 2015.WebHome]](%%) ====

235

236

==== (% style="color:#000000" %)Talks of the spring term 2015[[doc:Logic.Home.Seminar.Seminar talks spring 2015.WebHome]](%%) ====

237

238

==== (% style="color:#000000" %)Talks of the fall term 2014[[doc:Logic.Home.Seminar.Seminar talks fall 2014.WebHome]](%%) ====

239

240

==== (% style="color:#000000" %)Talks of the spring term 2014[[doc:Logic.Home.Seminar.Seminar talks spring 2014.WebHome]](%%) ====

241

242

==== (% style="color:#000000" %)Talks of the fall term 2013[[doc:Logic.Home.Seminar.Seminar talks fall 2013.WebHome]](%%) ====

243

244

==== (% class="confluence-link" style="color:#000000" %)Talks of the spring term 2013(% style="color:#000000" %)[[doc:Logic.Home.Seminar.Seminar talks spring 2013.WebHome]](%%) ====

245

246

==== (% style="color:#000000" %)Talks of the fall term 2012[[doc:Logic.Home.Seminar.Seminar talks fall 2012.WebHome]](%%) ====

247

248

==== (% style="color:#000000" %)[[(% style="color: rgb(0, 0, 0); color: rgb(0, 0, 0)" %)Older talks (2011-2012)>>url:http://www.helsinki.fi/~~kluosto/mat.log.sem/talks.txt||shape="rect"]](%%) ====

249

250

(% style="color:#000000" %)[[(% style="color: rgb(0, 0, 0); color: rgb(0, 0, 0)" %)Laboratory of dependence logic>>url:http://wiki.helsinki.fi/display/mathstatKurssit/Dependence+logic%2C+fall+2012||shape="rect"]]

Wiki source code of Seminar

Navigation