Tennenbaum's theorem states that PA does not admit any nonstandard computable model. In 2022, Fedor Pakhomov proved that this theorem is fragile in regards to how PA is expressed, by constructing a theory that is definitionally equivalent to PA (roughly: “it’s PA but with a different choice of signature”) for which there is a computable nonstandard model. I will introduce the audience to this result and, time allowing, present the way in which we have been able to improve on Pakhomov's original construction and some remaining open questions.

An important aspect of socially interacting rational agents are the strategic abilities of individual agents and groups (coalitions) of agents to guarantee the achievement of their desired goals, while acting and interacting within an entire society of agents. Several logical systems have been proposed for formalising and capturing such reasoning were introduced in the early 2000s, starting with the Coalition Logic (CL), the Alternating Time Temporal Logic (ATL), and some extensions of these. Coalition Logic provides a natural, but rather restricted perspective: the agents in the proponent coalition are viewed as acting in full cooperation with each other but in complete opposition to all agents outside of the coalition, which are thus treated as adversaries. The Alternating Time Temporal Logic extends Coalition Logic with temporal operators allowing for expressing long-term temporised goals. The strategic interaction in real societies is much more complex, usually involving various patterns combining cooperation and competition. To capture these, more expressive and versatile logical frameworks are needed. In this talk I will give a brief overview of some of these, and will then focus on the Logic of Coalitional Goal Assignments (LCGA), capturing reasoning about strategic abilities of the entire society to cooperate in order to ensure achievement of the societal goals, while simultaneously protecting the abilities of individuals and groups within the society to achieve their individual and group goals.

Semantic tableaux for combined logical systems are usually constructed ad hoc and the problem of developing and applying more general methodologies for combining tableaux is yet to be systematically explored. In this talk I will address that problem and will outline some methodological approaches for combining tableaux for fibring, fusion, and products of logics. I will focus mainly on the case of fibring of tableaux and will discuss the questions of transfer of soundness, completeness, and termination from the components to the combined tableaux, both in general and in the context of some important special cases.

A classical result of Plotkin (IRE Transactions on Information Theory, 1960) establishes that over binary alphabets, positive rate codes cannot have minimum distance greater than $1/2$, and thus can uniquely correct at most a $1/4$ fraction of bit-flip errors. It is additionally known that if one insists on constructing a code correcting a $1/4+ε$ fraction of errors (for small $ε>0)$, then this code can have size at most $O(1/ε)$, and that this is tight.

If one moves to list-decoding binary codes with list-size $L$ — that is, the decoder may output up to $L$ guesses for the transmitted message, as long as one of the guesses is correct — Blinovsky (Problems of Information Transmission, 1986) computed a similar threshold $p_L$. Additionally, his argument establishes that any $(p_L+ε, L)$-list-decodable code must have size at most $O_{ε,L}(1)$ — a constant, but with a (massive) dependence on $ε$. Later, Alon, Bukh and Polyanskiy (IEEE Transactions on Information Theory, 2018) showed that for odd $L$, such codes have size $O_L(1/ε)$ (as with Plotkin’s bound), but already with $L=2$ such codes of size $O(1/ε^{3/2})$ exist.

In this talk, we will generalize all of these results to any (constant) alphabet size $q > 2$. A crucial tool in the proof is the concept of Schur convexity, which in certain cases allows one to show that the optimizing value for a function on a space of distributions is the uniform distribution.

The celebrated “hardness vs. randomness” paradigm lets us derandomize algorithms under the assumption that certain computational problems are hard to solve. Classical applications of this paradigm led to many exciting results in complexity theory, and in recent years we have been able to overcome several barriers of the original approach, using a host of new techniques.

In this talk I will survey a small selection of recent results in hardness vs. randomness. The common theme will be a close look at reconstructive pseudorandom generators, studying the complexity of reconstruction and the possibility of deterministic reconstructions.

The talk will be high-level and will aim to assume no prior knowledge.