Conference on

Logic, Computability and Randomness 2004

Córdoba, Argentina

September 20th to 24th

 >> General Information >> Program Committee >> Plenary Speakers >> Abstracts and slides        of Plenary Speakers >> Conference Address >> Local Organization >> Registration >> Accomodation and         Practical Information >> Travel grants >> About Córdoba >> Abstracts of invited         and contributed talks >> Conference Photos >> Turism photo gallery
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 <<
 Rod Downey Victoria University Wellington  New Zealand Denis Hirschfeldt University of Chicago  USA Verónica Becher University of Buenos Aires Argentina

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 <<
 Facultad de Matemática, Astronomía y Física Universidad Nacional de Córdoba Av. Haya de la Torre s/n Ciudad Universitaria Córdoba, Argentina

Local Organization <<
 Santiago Figueira Silvana Picchi
 Tel: +54 (11) 4576 3390 int. 718 Fax: +54 (11) 4576 3359

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.
In the text include:

Name, Country and University or Institute.

Please also indicate whether you need a letter of invitation.
You will receive an email as confirmation for your participation in the event.

Accomodation and practical information <<

Argentinean money
The exchange rate is 1US$= 3$ Argentinean. Links to Currency converters http://money.cnn.com/markets/currencies/.

Hotels
Most of the participants will stay at

NH Urbano Express Hotel ****,
Marcelo T. de Alvear 363, Cordoba, Argentina
Tel. 54-351-410-3960
Fax 54-351-410-3990
ma.mauro@nh-hotels.com
www.nh-hotels.com

The special Conference price is US$25 per day (tax included) with breakfast. If you want to stay at this hotel, send an email to logic2004@dc.uba.ar including your arrival and departure date, and we will make a reservation at your name. Any hotel in downtown Cordoba is close enough to the Conference site, which is at the campus of the National University of Córdoba. This is an exhaustive list of hotels in Cordoba. Getting there The best way to get to Cordoba is first to fly to Buenos Aires (Ezeiza Airport) and, from this airport, connect with a domestic flight to Cordoba (Pajas Blancas Airport). Beware that Buenos Aires has another airport, Aeroparque Jorge Newbery, related to most domestic flights (it is one hour drive from Ezeiza). Useful link: http://www.amadeus.net/ Information on how to go from Pajas Blancas airport to the city will be provided here. Climate At the time of the conference it will be spring. Do not expect rain. Useful links: http://weather.cnn.com/weather/forecast.jsp?locCode=SACO. http://www.infoclima.com.ar/. Local Time and dialing codes Useful link: http://www.timeanddate.com/worldclock/city.html?n=485. Meals You can eat at the University campus for$5. Outside University meals cost between $10-$25 (all Argentinean \$).

Additional information
This page will be updated regularly. To obtain further information, email Veronica or Santiago.

Travel grants <<

Students members of the ASL can apply for travel grants
(see http://www.aslonline.org/studenttravelawards.html).

The approval process takes a few weeks.

About Córdoba <<
 It is a colonial city of Argentina on the edge of the Sierra Chica mountain. It has the oldest and one of the most prestigious universities of the country, founded by the Jesuits in 1622, and the center of the city is rich in Spanish colonial architecture from the 16th century. Its name comes from the surrounding province, which embraces an unusually scenic section of the Andes, the Sierras de Cordoba. Located in the geographical centre of Argentina, it offers opportunities for traditional and adventure tourism as the hills and valleys are filled with springs, crystal clear rivers, artificial lakes, the huge salted lake of Mar Chiquita (heaven of ornithologists), and rupestrian (cave) paintings in Cerro Colorado. The Punilla Valley and Cuchi Corral have exceptional natural atmosphere for aerial activities, such as parachuting and ballooning, and on San Roque Lake windsurfing, yachting and nautical sports. The Calamuchita Valley has lakes and clear rivers surrounded by mountains, an ideal area for swimming, mountain climbing and trekking, cycling, horse riding and  fishing. In Traslasierra Valley, across the Sierras Grandes, there is Pampa de Achala. On the peak resides the Quebrada de los Condoritos National Park, one of the only places in the world where you may see the highly endangered condor, largest bird on earth, in their natural habitat.

Córdoba photo gallery <<

Last update: Oct 4, 2004