=
Andre Nies' home page
Talks I have given at conferences, workshops, and in some cases seminars.
2024
Describing a group by a first-order sentence . New methods in group actions on manifolds, Korea Institute of Advanced Study .
Borel classes of closed subgroups of Sym(N) . Nankai Logic Colloquium, Nankai University .
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