Conference on
 |
||||||||||||||||||||||||
|
General Information
<<
|
||||||||||||||||||||||||
|
The conference will be held at
Facultad de Matemática, Astronomía y Física,
Universidad Nacional de Córdoba, Argentina.
The registration is on Monday 20th form 9:00 to 10:00. We meet at Facultad de Matemática, Astronomía y Física -FAMAF- (Av. Haya de la Torre s/n Ciudad Universitaria). Program and abstracts of invited and contributed talks are now available. The program will consist of invited talks, contributed talks and discussions. The conference will include topics in mathematical logic, computability, effective randomness, Kolmogorov complexity and related subjects. The conference is sponsored by the Association for Symbolic Logic. It will be run in parallel to the 33 Argentinean Conference on Computer Science and Operational Research (33 JAIIO), organized by Sociedad Argentina de Informática e Investigación Operativa (SADIO). |
||||||||||||||||||||||||
|
Program Committee <<
|
||||||||||||||||||||||||
|
|
||||||||||||||||||||||||
|
Plenary Speakers
<<
|
||||||||||||||||||||||||
|
Joos Heintz (University of Buenos Aires/ University of Cantabria) Antonin Kucera (Charles University, Prague) Joseph S. Miller (University of Victoria /Indiana) André Nies (University of Auckland) Jan Reimann (University of Heidelberg) Theodore Slaman (University of California, Berkeley) Paul Vitanyi (CWI, Amsterdam) Diego Vaggione (University of Córdoba) |
||||||||||||||||||||||||
|
Abstracts and slides of Plenary Speakers
<<
|
||||||||||||||||||||||||
|
Complete list of abstracts of invited and contributed talks is now available. The queries of algebraic geometry Joos Heintz (University of Buenos Aires/ University of Cantabria) Application of scientific knowledge leads often to questions, which, after a suitable process of modelling and simplification, can be reformulated as polynomial (or algebro-differential) equation systems whose solutions represent the answers to these questions. Remarks on randomness and PA sets Antonin Kucera (Charles University, Prague) The first part will be devoted to remarks on Demuth's work which relates to randomness. Demuth was motivated by the study of computable aspects of concepts from (constructive) mathematical analysis. The second part will be devoted to DNR functions, PA sets and randomness. See slides Omega Operators Joseph S. Miller (University of Victoria /Indiana) As a natural example of a 1-random real, Chaitin proposed the halting probability $\Omega$ of a universal partial computable prefix-free machine. We can relativize this example by considering a universal prefix-free oracle machine $U$. Let $\Omega^A_U$ be the halting probability of $U^A$; this gives a natural uniform way of producing an $A$-random real for every $A\in 2^\omega$. We can draw an analogy between the jump operator from computability theory and this $\Omega$-operator. But unlike the jump, which is invariant (up to computable permutation) under the choice of an effective enumeration of the partial computable functions, $\Omega^A_U$ can be vastly different for different choices of $U$. Even for a fixed $U$, there are oracles $A=^*B$ such that $\Omega^A_U$ and $\Omega^B_U$ are 1-random relative to each other. We discuss this and many other interesting properties of $\Omega$-operators. We investigate these operators from the perspective of analysis, computability theory, and of course, algorithmic randomness. This talk describes joint work with Rod Downey, Denis Hirschfeldt and Andre Nies. See slides Randomness and descriptive set theory André Nies (University of Auckland) The set $A$ is a basis for Martin-Lof random if $A$ is Turing below some $Z$ which is ML-random in $A$. This notion was introduced by Kucera in a 1993 paper (called basis for 1-rra there). Denis Hirschfeldt and myself, working in Rio in (our) summer 2003, proved that each basis for ML-random is $K$-trivial. By the Kucera-Gacs Theorem (each set is Turing below a ML-random), this gives a new proof that each low for ML-random set is $K$-trivial (originally proved by different means, Nies 2002). In the first half of the talk I will discuss this result and interesting related results due to Stephan. In April 2004, G. Hjorth and myself looked at an analog of ML-randomness defined in terms of $\Pi^1_1$ sets of numbers. (T. Slaman had suggested to look at randomness notions higher up.) Such $\Pi^1_1$ sets can be thought of as being enumerated in a construction at stages that are recursive ordinals. One may, in a straightforward way, define analogs of ML-randomness and prefix free complexity K. The basics of the theory go through, like the Kraft- Chaitin Theorem, Schnorr's Theorem and Kucera-Gacs. Moreover, there is a $K$- trivial which is not hyperarithmetical. However, the analog of the argument used for the Hirschfeldt-Nies Theorem proves a stronger fact here: each basis $A$ for ML-random is already $K$-trivial at some recursive ordinal stage. This implies that $A$ is hyperarithmetical. Thus there are no low for ML-random sets in this setting beyond the hyperarithmetical ones. Random functions Jan Reimann (University of Heidelberg) When we speak of random sequences, it is usually implied to refer to binary sequences (or sequences over a finite alphabet). Is there an adequate notion of randomness for sequences of natural numbers? We investigate to what extent the two major approaches to randomness (measure theoretic and via descriptive complexity) yield a robust notion of randomness for functions. Besides, we use the correspondence between sequences of natural numbers and continued fractions to study random reals and some connections to diophantine approximation. See slides Measures and Their Random Reals Theodore Slaman (University of California, Berkeley) I will discuss joint work with Jan Reimann, University of Heidelberg, in which we examine reals which are random for measures other than the standard Lebesgue measure. See slides Extracting Meaning: Positive Randomness and Negative Randomness Paul Vitanyi (CWI, Amsterdam) In classical probabilistic statistics model selection the problem arises that for individual data the selection of the model may be bad although the selection performance is good on average, or vice versa. There is also the problem of what probability means, whether it is subjective, objective, or exists at all. As perhaps the last mathematical innovation of an extraordinary scientific career, Kolmogorov in 1974 proposed to found statistical theory on finite combinatorial and computability principles independent of probabilistic assumptions, as the relation between the individual data and its explanation (model), expressed by Kolmogorov's structure function. It turns out that this proposal is formally a Shannon's rate distortion function for individual data and related to lossy compression. The information contained in an individual finite object (like a finite binary string) is measured by its Kolmogorov complexity---the length of the shortest binary program that computes the object. Such a shortest program contains no redundancy: every bit is information; but is it meaningful information? If we flip a fair coin to obtain a finite binary string, then with overwhelming probability that string constitutes its own shortest program. However, also with overwhelming probability all the bits in the string are meaningless information, random noise. On the other hand, let an object $x$ be a sequence of observations of heavenly bodies. Then $x$ can be described by the binary string $pd$, where $p$ is the description of the laws of gravity, and $d$ the observational parameter setting: we can divide the information in $x$ into meaningful information $p$ and accidental information $d$. The main task for statistical inference and learning theory is to distil the meaningful information present in the data. The question arises whether it is possible to separate meaningful information from accidental information, and if so, how. The basic approach as formulated by Kolmogorov is as follows: ``To each constructive object corresponds a function $\Phi_x(k)$ of a natural number $k$---the log of minimal cardinality of $x$-containing sets that allow definitions of complexity at most $k$. If the element $x$ itself allows a simple definition, then the function $\Phi$ drops to $1$ even for small $k$. Lacking such definition, the element is ``random'' in a negative sense. But it is positively ``probabilistically random'' only when function $\Phi$ having taken the value $\Phi_0$ at a relatively small $k=k_0$, then changes approximately as $\Phi(k)=\Phi_0-(k-k_0)$.'' The talk will explain the basic setting of 1974, modest progress up to 2002, and the recent breakthroughs. Based on joint work with Nikolai Vereshchagin presented partially at the 47th IEEE Symp on Foundat. Comput. Sci., 2002, Vancouver, Canada; paper at http://www.cwi.nl/~paulv/kolmcompl.html or http://arXiv.org/abs/cs.CC/0204037 to appear in IEEE Trans. Inform. Th.; and recent unpublished work with Peter Grunwald and Nikolai Vereshchagin. Axiomatizability by sentences of the form (All)(Exist)! &p=q Diego Vaggione (University of Córdoba) Give an equational class V, several important subclasses of V can be defined by sentences of the form (All)(Exist)! &p=q. For example, if V is the class of all semigroups con unit, then the subclass of all groups can be defined in this manner and if V is the class of all bounded distributive lattices, then the subclass of all Boolean lattices is axiomatizable in this manner. We will present a solution to the problem. Characterize the subclasses of V which can be axiomatized by sentences of the form (All)(Exist)! &p=q for some equational classes V. |
||||||||||||||||||||||||
|
Conference Address <<
|
||||||||||||||||||||||||
|
||||||||||||||||||||||||
|
Local Organization <<
|
||||||||||||||||||||||||
|
||||||||||||||||||||||||
|
Registration <<
|
||||||||||||||||||||||||
|
The registration fee is U$S 80. Registration for students is U$S 40.
To register send an email to logic2004@dc.uba.ar
with subject REGISTRATION.
Name, Country and University or Institute. |
||||||||||||||||||||||||
|
Accomodation and practical information <<
|
||||||||||||||||||||||||
|
Argentinean money Hotels Getting there Climate Local Time and dialing codes Meals Additional information |
||||||||||||||||||||||||
|
Travel grants <<
|
||||||||||||||||||||||||
|
Students members of the ASL can apply for travel grants The approval process takes a few weeks. |
||||||||||||||||||||||||
|
About Córdoba <<
|
||||||||||||||||||||||||
|
||||||||||||||||||||||||
|
Córdoba photo gallery <<
|
||||||||||||||||||||||||
|
||||||||||||||||||||||||
|
||||||||||||||||||||||||
