= Andre Nies' home page

Andre Nies: talks

Talks I have given at conferences, workshops, and in some cases seminars.

2024

Two “almost sure” theorems under the lens of algorithmic randomness. Randomness, information and complexity, CIRM, Luminy.

2023

The Borel complexity of the bi-interpretability relation between omega-categorical structures. Generic structures, Banach Centre, Bedlewo.

Representing totally disconnected, locally compact groups by countable structures. Totally disconnected locally compact groups: local to global, Uni Muenster.

Prime numbers, factorization, and algorithms. ISA- Institute of Advanced Studies, Bologna.

Computably totally disconnected, locally compact groups. Cross-Alps Logic Seminar, online.

Undecidability and quantum information theory. Center for Quantum Technologies, NU Singapore.

Martin-Loef randomness, 2-randomness, and reverse mathematics. From omega to Omega, Inst. Mathematical Sciences, Singapore.

2022

Computably totally disconnected locally compact groups. Computational Aspects of Totally Disconnected Locally Compact Groups, University of Newcastle, Australia.

Computability theory and quantum information theory. QuSoft, CWI, Amsterdam.

20 years of K-triviality. International conference on computability, complexity and randomness, Isaac Newton Institute, Cambridge, UK.

Randomness for infinite sequences of quantum bits. New Directions in Computability Theory, CIRM, Marseille. Video.

2021

The search for FA presentable groups. Automata Theory and Applications: Games, Learning and Structures, IMS, Singapore.

When can a totally disconnected locally compact group be called computable?. Workshop Totally Disconnected Locally Compact Groups via Group Actions (21w5151), Banff. Video.
Later version: Computability for totally disconnected locally compact groups. Workshop Algorithmic Presentations in Mathematicss (APM-2021), Sochi, Russia.

Undecidability and algorithmic randomness for spin chains. Workshop on Logic, Quantum Computing, and Artificial Intelligence, Arak University, Iran, July (online).

Duality between topological groups and approximation groupoids. Third Workshop on Digitalization and Computable Models (WDCM 2021), Sobolev Institute and Kazan Federal University, July (online). Joint work with Melnikov, and also Tent and Schlicht.

Calibrating word problems of groups via the complexity of equivalence relations. Joint work with Sorbi. Workshop on Equivalences, Numberings, Reducibilities, Udine, June (online).

Maximal towers and ultrafilter bases in computability theorys (video). Midwest Computability together with Computability theory and applications online seminars, May. Slides.

2020

Groups and first-order logic. International Congress on Mathematics and Applications (ICMA 2020), Mahidol University, Bangkok, Dec.

Metric spaces and computability theory. Mal'cev meeting, Novoskibirsk, Nov (online).

Discovering structure within the class of K-trivial sets (video). CTA online seminar, August. Slides.

Randomness and initial segment complexity for probability measures. With Frank Stephan. STACS 2020, Montpellier. Extended version at minisymposium on randomness, DMV meeting, Chemnitz, Sept. Journal paper.

Expressivity of first-order logic for profinite groups. Covers research with Segal and Tent. CARMA seminar, University of Newcastle, Feb.

2019

Muchnik degrees and cardinal characteristics. With B. Monin. Set theory of the reals, Casa Matemática Oaxaca, August.

The complexity of the isomorphism relation between oligomorphic groups. Joint work with Philipp Schlicht and Katrin Tent. Set theory of the reals, Casa Matemática Oaxaca.

The remarkable expressivity of first-order logic for profinite groups. Joint work with Dan Segal and Katrin Tent. Conference on algebra and Mathematical Logic, Kazan, June.

Effective metric Scott analysis. Institute of Mathematical Sciences, National University of Singapore, June.

Quantum information science. Mathematical background. School of Computer Science, Auckland University, May.

2018

Topological isomorphism for classes of closed subgroups of Sym(N). Descriptive set theory conference, Bernoulli Center, June. Seminar Talk Uni Bonn October about the same topic.

Closure of resource bounded randomness notions under polynomial time permutations. STACS 2018, Caen, France, February.

Quantum Martin-Loef randomness and the Shannon-McMillan-Breiman Theorem. Algorithmic questions in dynamical systems, Toulouse, March.

2017

Randomness for infinite sequences of quantum bits. CCR 2017, Mysore, India, July 5.

Sets that coincide with 1/2 − ε of each computable set. Leibniz Zentrum, Dagstuhl, Feb. 17.

Structure within the class of K-trivial sets. NTU seminar, Feb. 6.

My work with Rod 1995-2001. Rodfest, Traumati Beach, January 5-8.

2016

Describing finite groups by first-order sentences of polylogarithmic length.
With Katrin Tent. LC 2016, Computability special session, University of Leeds, August 5.

Randomness and quantum computation.
Computability and the BSS model, Hiddensee, August 8-12.

Lowness, Randomness, and Computable Analysis.
Computability in Europe 2016 plenary talk, Paris, June 27-July 1.

Lightface Pi03-completeness of density sets under effective Wadge reducibility. With Gemma Carotenuto.
CiE 2016 contributed paper, Paris, June.

Randomness connecting to set theory and to reverse mathematics.
Computability, randomness and applications, CIRM Luminy, June.

The complexity of isomorphism between profinite groups.
Cabal seminar, UCLA, March 9.

2015

Randomness and Analysis: a tutorial.
Continuity, Computability, Constructivity (CCC), Sept 2015, Kochel near Munich.

Part 1: Randomness notions and almost everywhere theorems
Part 2: Lebesgue density and its applications to anti-randomness

A unifying approach to the Gamma question.
With B. Monin. Logic in Computer Science (LICS), July, Kyoto.

Local compactness for computable Polish metric spaces is Pi-1-1 complete.
With S. Solecki. Contributed to Computability in Europe (CiE), July, Bucharest.

Objects of greatest complexity in their class.
Workshop on Computability Theory (WCT), July, Bucharest.

Multiple recurrence and algorithmic randomness.
Computability, complexity and randomness (CCR), June, Heidelberg.

Interactions of computability and randomness.
London School of Ecomonics, Dept. of Mathematics Seminar talk, May.

The Gamma question and cardinal characteristics.
Sets and Computations, March/April, Inst. Math. Sciences, Singapore.

2014

Compression and Randomness.
Inaugural Lecture, University of Auckland, Oct. Poster. Slides.

An analogy between cardinal characteristics and highness properties of oracles.
Computability, Complexity, and Randomness, May, Inst. Math. Sciences, Singapore.

Differentiability of polynomial time computable functions.
Symposium on Theoretical Aspects of Computer Science (STACS), March, at ENS Lyon.

Groups and first-order logic.
Department of Mathematics, Feb, University of Western Australia (Perth).

2013

The complexity of similarity relations for Polish metric spaces.
Universality and Homogeneity Trimester, Hausdorff Institute for Mathematics, Sept-Dec, Bonn.

How the Lebesgue density theorem resolved the covering problem.
Asian Logic Colloquium (ALC), Sept, Guangzhou.

Metric spaces and computability theory.
Sy Friedman's 60th Birthday Confernce, July, in Vienna.

Categoricity for compact computable metric spaces. With A. Melnikov.
Computability in Europe, Milano, July.

Differentiability and porosity
Buenos Aires Semester on computability, complexity, and randomness, Feb-June.

Complexity of isomorphism relations
Descriptive set theory and model theory (DSTMT), Indian Statistical Institute, Kolkata, Jan.

2012

Demuth randomness and its variants
CCR, Cambridge, UK, June.

"Almost everywhere'' theorems and algorithmic randomness
CCA, Cambridge, UK, June.

Ten years of triviality
The Incomputable, Chicheley Hall, June.

Complexity of equivalence relations
Logic seminar, NUS, April; KGRC, May, University of Leicester, June (final version).

Randomness interacts with computable and polynomial time analysis
Computability Complexity and Randomness (CCR) at Schloss Dagstuhl, January.

Coding with first-order formulas
Talk at Universitaet Heidelberg on the occasion of Prof. Klaus Ambos Spies' 60th birthday.

2011

Introductory talk to the Conference Analysis and Randomness in Auckland 2011.

K-triviality in computable metric spaces
With A. Melnikov. ARA 2011, Auckland (former version CCA 2011)

Borel Structures and Borel theories
U Paris 7, 2011/KGRC Vienna 2012

Measuring the complexity of Delta-2 sets via their changes
Asian Logic Colloquium 2011, Victoria University, Wellington.

Randomness and computable analysis: results and open questions
CCR/A 2011, Cape Town

2010

Interactions of Computability and Randomness
International Congress of Mathematicians (ICM), Hyderabad, 2010

Borel Structures
ICM Satellite meeting, Chennai, 2010

Random objects, and objects of low complexity
Mathematics Department Colloquium, Auckland, 2010

Randomness and differentiability (with J. Miller and V. Brattka).
CCR, Notre Dame, May 2010.

2009

Three Lectures on applying randomness to computability. Assoc. Symb. Logic European Summer Meeting tutorial, Sofia. Slides or Paper version.

Superhighness and strong jump traceability.
ICALP, Rhodes, Greece, 2009

Future directions in Computability and Randomness.
CCR 2009, Marseille

Upper bounds for ideals in the Turing degrees.
With G. Barmpalias. Asian Logic Collquium, Singapore, 2009

Tutorial on cost functions.
FRG randomness workshop Madison, 2009

Tutorial on randomness via effective descriptive set theory.
FRG randomness workshop Madison, 2009

Cost functions and lowness properties.
Assoc. Symb. Logic. Annual meeting, 2009

2004-08

Weak reducibilities
CCR 08, Nanjing

Randomness, computability, effective descriptive set theory
TAMC 07, Shanghai

Lowness properties and Highness properties
American Inst. of Mathematics, Palo Alto, August 2006

Randomness via computability theory and effective descriptive set theory NUS Singapore, June 2006

Recent results relating computability and randomness SEALS, U of Florida, Mar 2006

Eliminating concepts: K-trivial equals low for K IMS workshop, Singapore, July 2005

Algebras with finite descriptions Assoc. Symb. Logic summer meeting, Athens, August 2005

Quasi-finitely axiomatizable groups Univ. of Auckland and Univ. Paris, Jan 2005

FA-presentable structures: richness and limitations WAssoc. Symb. Logic 2004, and Univ. Paris, Jan 2005

Randomness Notions and Lowness Properties VIC2004, Wellington, New Zealand, Feb 2004

Randomness, K-triviality and Omega UC Berkeley and UCLA, May 2004

1996-2003

Computable randomness and lowness. Kolmogorov complexity and its applications. Dagstuhl, Germany, May 2003

Lowness properties CL2002, Muenster, Germany

Model theoretic properties of structures from computability theory , Oberwolfach, Jan 2001

How expressive is the first--order language for groups? Math. Dept colloquium, U. of Chicago, 2001

Global properties of degree structures Boulder computability workshop (AMS), 1999

Model theory of degree structures, LMPS 99, Krakow, 1999

Definability and undecidability PUC-Rio, 1999

Approximations to bi-interpretability with N, XI. Latin American Logic Symposion, Merida, Venezuela, 1998

Homogeneity properties of free groups, Albany Group Theory Conference, 1997

Definability Lemmas Kazan recursion theory meeting (WORCT 97), 1997

Undecidability of the exponential time degrees and effective algebra Assoc. Symb. Logic meeting, 1997

(joint with Shore and Slaman) Coding and definability in the r.e degrees Oberwolfach, 1996

Validated xhtml logo