International Conference on
Computability and Complexity in Analysis

August 28-30, 2003, Cincinnati, USA


The conference is concerned with the theory of computability and complexity over real-valued data.

Computability theory and complexity theory are two central areas of research in mathematical logic and theoretical computer science. Computability theory is the study of the limitations and abilities of computers in principle. Computational complexity theory provides a framework for understanding the cost of solving computational problems, as measured by the requirement for resources such as time and space. The classical approach in these areas is to consider algorithms as operating on finite strings of symbols from a finite alphabet. Such strings may represent various discrete objects such as integers or algebraic expressions, but cannot represent a general real or complex number, unless it is rounded.

The classical theory of computation does not deal adequately with computations that operate on real-valued data. Most computational problems in the physical sciences and engineering are of this type, such as the complexity of network flow problems and of dynamical and hybrid systems. To study these types of problem, alternative models over real-valued data and other continuous structures have been developed in recent years. Unlike the well established classical theory of computation over discrete structures, the theory of computation over continuous data is still in its infancy.

Scientists working in the area of computation on real-valued data come from different fields, such as theoretical computer science, domain theory, logic, constructive mathematics, computer arithmetic, numerical mathematics, analysis, etc. The conference provides a unique opportunity for people from such diverse areas to meet and exchange ideas and knowledge.

The topics of interest include foundational work on various models and approaches for describing computability and complexity over the real numbers; complexity-theoretic investigations, both foundational and with respect to concrete problems; and new implementations of exact real arithmetic, as well as further developments of already existing software packages. We hope to gain new insights into computability-theoretic aspects of various computational questions from physics and from other fields involving computations over the real numbers. This will require the extension of existing computability notions to more general classes of objects.

Scientific Program Committee

Vasco Brattka (Hagen, Germany)
Douglas Cenzer (Gainesville, USA)
Rod Downey (Wellington, New Zealand)
Martín Escardó (Birmingham, UK)
Ker-I Ko (Stony Brook, USA)
Norbert Müller (Trier, Germany)
Marian Pour-El (Minneapolis, USA)
Dieter Schmidt (Cincinnati, USA)
Matthias Schröder (Hagen, Germany)
Viggo Stoltenberg-Hansen (Uppsala, Sweden)
Klaus Weihrauch, chair (Hagen, Germany)
Mariko Yasugi (Kyoto Sangyo, Japan)
Jeffery Zucker (Hamilton, Canada)

Local Organizing Committee

Kenneth Meyer (Cincinnati, USA)
Dieter Schmidt (Cincinnati, USA)
Bingyu Zhang (Cincinnati, USA)
Ning Zhong, chair (Cincinnati, USA)

Invited Talks

  1. Douglas S. Bridges (Christchurch, New Zealand)
    First steps in constructive game theory
  2. Rod Downey (Wellington, New Zealand)
    Presenting reals
  3. Peter Hertling (Duisburg-Essen, Germany)
    Topological complexity of zero finding for continuous functions
  4. Iraj Kalantari (Illinois, USA)
    Density and Baire category in recursive topology
  5. Vladik Kreinovich (Texas, USA)
    Computational complexity and feasibility of data processing and interval computations, with extension to cases when we have partial information about probabilities
  6. Boris A. Kushner (Pittsburgh, USA)
    The centenary of A.A. Markov, Jr.; His personality, his constructive mathematics
  7. Jack Lutz (Ames, USA)
    Effective fractal dimensions
  8. Klaus Weihrauch (Hagen, Germany)
    Continuity in Computable Analysis

Contributed Talks

  1. Andrej Bauer and Alex Simpson
    Locally non-compact spaces and continuity principles
  2. Vasco Brattka
    Effective Borel measurability and reducibility of functions
  3. Cristian S. Calude and Ludwig Staiger
    Generalisations of disjunctive sequences
  4. Douglas Cenzer and Jeffrey B. Remmel
    Index sets for computable real functions
  5. Arthur W. Chou and Ker-I Ko
    On the complexity of finding shortest paths in a two-dimensional domain
  6. Abbas Edalat and Dirk Pattinson
    Initial value problems in domain theory
  7. Daniel Silva Graça
    Computability via analog circuits
  8. Armin Hemmerling
    Characterizations of the class Delta_2^{ta} over Euclidean spaces
  9. Elham Kashefi
    Quantum domain theory - definitions and applications
  10. Bjørn Kjos-Hanssen, André Nies and Frank Stephan
    On a question of Ambos-Spies and Kucera
  11. Daren Kunkle
    Computability on spaces of integrable functions
  12. Branimir Lambov
    A two-layer approach to the computability and complexity of real functions
  13. Marian B. Pour-El and Ning Zhong
    Boundary regularity and computability
  14. Matthias Schröder
    Spaces allowing type-2 complexity theory revisited
  15. Guohua Wu
    Regular reals
  16. Xizhong Zheng and Robert Rettinger
    h-Monotonically computable real numbers
  17. Martin Ziegler
    Computable operators on regular sets

Some participants of CCA 2003

Further pictures are provided by Andrej Bauer.


Here is a PDF version of the preliminary program.


Registration and application for financial support is no longer possible.

A registration fee of $50.00 will be collected at registration desk. ($20.00 for banquet for spouse.) The registration fee will be used to defray the cost for refreshements, three lunches, and the banquet.

A registration session will be held at the Vernon Manor Hotel, Wednesday, 4:00PM-7:00PM, August 27. Finger foods and drinks will be provided.

The travel support will be administrated in the form of reimbursement. Original receipts are needed for reimbursement. Usually it takes about one month to process paper works and sent out the reimbursement check after we receive your receipts.

Conference Site

The conference will be held at the west campus of the University of Cincinnati. The conference room is either 755 or 625, Baldwin Hall.

Refreshments and lunches will be provided in 736, Old Chemistry. Baldwin Hall and Old Chemistry are next to each other. If you need special dishes, please email your request to Ning Zhong ([Email removed])


Block of rooms have been reserved at the Vernon Manor Hotel, Cincinnati. Reservation will be accepted at the hotel until August 13, 2003. In order to receive a special rate for the CCA 2003 conference, reservation request (telephone or online) MUST identify your affiliation with International Conference. The rate per night, for either single or double beds, is $79.00 without breakfast or $85.95 with breakfast ($92.90 if two people share a double beds room), plus 16.5% taxes. If you would like to share a double beds room with another participant of the conference, please email your request to Ning Zhong ([Email removed]) for arrangement.


How to get to Vernon Manor Hotel from the Greater Cincinnati and Northern Kentucky International Airport? - At the airport baggage claim area, you can purchase shuttle or taxi ticket at the desk for Airport Executive Shuttle or at the desk for taxi. From airport to Vernon Manor Hotel, it costs $28.00 by taxi and $14.00 ($24.00 round trip) by shuttle bus.

How to get to the lecture room from Vernon Manor Hotel? - You can either take the hotel shuttle bus (shuttle time will be posted later) or walk to the conference site. The hotel is at the corner of Oak street and Burnet Ave. To walk to UC campus, turn north to Burnet Ave, then turn west to University Ave, which leads to UC west campus. (To get a map, log on and type in the address of the Vernon Manor Hotel - 400 Oak Street, Cincinnati, OH 45219.) At the UC entrance you will see a ship-shaped building (Engineering Research Center) straight ahead. Walking up an open staircase at the right of the ship building, you will find signs to Baldwin Hall and Old Chemistry. It takes about 15 minutes to walk to UC campus from the hotel.

Please visit for museums, performances, parks, and other entertainments in Cincinnnati.

Funding Opportunities

The conference is partially supported by the The National Science Foundation; Taft Memorial Foundation of the University of Cincinnati; the Institute for Mathematics and Applications (IMA); the Ohio Board of Regents; the Clermont College, the Department of Electrical and Computer Engineering and Computer Science, and the Department of Mathematical Sciences of the University of Cincinnati. Limited funds are available to conference participants - in particular, to young researchers and Ph.D. students, female mathematicians and female computer scientists, and members of underrepresented groups. The conference is also sponsored by the Association for Symbolic Logic (ASL). Financial support from ASL may be available for student members of ASL.


Here you can find information on the special issue of

Mathematical Logic Quarterly (MLQ),

following the conference and dedicated to Klaus Weihrauch's 60th birthday.


For further information, please contact Vasco Brattka ([Email removed]) or Ning Zhong ([Email removed])

Start |  Introduction |  Members |  Events |  Links
© 2002-2003 Vasco Brattka