

General Information
<<




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 algebrodifferential) 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 1random real, Chaitin proposed the halting
probability $\Omega$ of a universal partial computable prefixfree
machine. We can relativize this example by considering a universal
prefixfree 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 1random 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 MartinLof random if $A$ is Turing below some
$Z$ which is MLrandom in $A$. This notion was introduced by Kucera in a
1993 paper (called basis for 1rra there). Denis Hirschfeldt and myself,
working in Rio in (our) summer 2003, proved that each basis for MLrandom
is $K$trivial. By the KuceraGacs Theorem (each set is Turing below a
MLrandom), this gives a new proof that each low for MLrandom 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 MLrandomness
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
MLrandomness and prefix free complexity K. The basics of the theory go
through, like the Kraft Chaitin Theorem, Schnorr's Theorem and
KuceraGacs. Moreover, there is a $K$ trivial which is not
hyperarithmetical. However, the analog of the argument used for the
HirschfeldtNies Theorem proves a stronger fact here: each basis $A$ for
MLrandom is already $K$trivial at some recursive ordinal stage. This
implies that $A$ is hyperarithmetical. Thus there are no low for
MLrandom 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 complexitythe 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(kk_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 <<



Av. Haya de la Torre s/n
Ciudad Universitaria

Córdoba, Argentina



Local Organization <<

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. 543514103960
Fax 543514103990
ma.mauro@nhhotels.com
www.nhhotels.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
