- 8/27/2019 4PM,
André Nies,
University of Auckland, New Zealand

Title: Random sequences of quantum bitsMartin-Löf (1966) formalised the intuitive notion of randomness for infinite sequences of bits via algorithmic tests. What if we replace classical bits by quantum bits?We first provide a framework to formalise infinite sequences of qubits as states of a suitable C

^{*}algebra. Thereafter we introduce an analog of Martin-Löf's notion. We show that for classical bit sequences the two notions coincide. We also discuss quantum Kolmogorov complexity for finite sequences of qubits and its relationship to quantum Martin-Löf randomness. Finally we consider an effective version of the Shannon-McMillan-Breiman theorem in the quantum setting.This is joint work with Volkher Scholz. Paper available at https://arxiv.org/abs/1709.08422.

Dinner: Vientiane Palace (151 W. Gorham St.) at 6PM at 6PM - 9/3/2019 4PM,
Luca San Mauro,
Vienna University of Technology, Austria

Title: The complexity of punctual equivalence relationsThe complexity of equivalence relations received much attention in the literature. In general, a reduction of an equivalence relation R on X to an equivalence relation S on Y is a function f: X\rightarrow Y that injectively maps R-classes to S-classes. In descriptive set theory, one assumes that X and Y are Polish spaces and f is Borel. In computability theory, one assumes that X=Y=ω and f is computable. To compare the complexity of equivalence relations which are computable, researchers also considered feasible variants of computable reducibility, such as the polynomial-time reducibility.In this work, we explore Peq, the degree structure generated by primitive recursive reducibility on punctual equivalence relations, i.e., primitive recursive equivalence relations with domain ω. We show that Peq has much structure, being a dense distributive lattice. This contrasts with all other known degree structures on equivalence relations. Finally, we use our analysis to investigate the online content of computably categorical equivalence structures and prove many elementary differences.

This is joint work with Nikolay Bazhenov, Keng Meng Ng, and Andrea Sorbi.

Dinner: Great Dane Pub (123 E. Doty St.) at 6PM - 9/10/2019 4PM,
Rod Downey,
Victoria University of Wellington, New Zealand

Title: TBATBA

Dinner: TBA at 6PM - 9/17/2019 4PM,
Iskander
Kalimullin, Kazan Federal University, Russia

Title: TBATBA

Dinner: TBA at 6PM - 9/24/2019 4PM,
Jun Le Goh,
UW

Title: TBATBA - 10/1/2019 4PM,
Dieter van Melkebeek,
UW computer science department

Title: Isomorphism problems and minimum circuit sizeTBA - 10/8/2019 4PM,
Manlio Valenti,
visiting UW from University of Udine, Italy

Title: TBATBA