RCA'06 is the second edition of this technical track, on Reliable Computations and their Applications, with a particular emphasis on combining interval and constraint satisfaction techniques. It will be held at SAC'06 between April 23 and 27, in Dijon (France). NEWS! The list of accepted papers and poster is now available here

SAC'2006

For the past twenty years, the ACM Symposium on Applied Computing (SAC) has been a primary gathering forum for applied computer scientists, computer engineers, software engineers, and application developers from around the world. SAC 2006 is sponsored by the ACM Special Interest Group on Applied Computing, hosted by the University of Bourgogne, and held in Dijon, France.

Overview of RCA'06:

Many numerical computations, be they solutions to systems of differential equations or optimization problems coming from applied areas like protein folding, do not provide us with guaranteed computation results. In many situations, we have numerical solutions, we may even have a theorem guaranteeing that, eventually, this numerical solution tends to the actual precise one, but the algorithm itself does not provide us with guaranteed bounds on the difference between the numerical approximate solution and the desired actual one.

Therefore, in some practical situations, numerical solutions are much farther from the actual (unknown) precise solutions than the users assume. As a result, we often end up with inefficient local maxima for practical optimization problems like chemical engineering - or even with a mission failure if we are planning, e.g., a spaceship trajectory.
For some such algorithms, researchers have found such guaranteed bounds, but producing such a bound for each algorithm requires a lot of work.

It is therefore desirable to develop a methodology that would provide algorithms with automatic result verification, i.e., with automatically generated upper bound on the difference between the actual and the numerical solution. In other words, we need computation techniques that produce reliable (guaranteed) results.

This problem was recognized already in the 1950s.The corresponding techniques, largely developed by Ramon E. Moore, were later applied in guaranteeing trajectories of spaceflights and in other practical problems where deviations from the target are of critical importance. The main idea behind these techniques is that at any intermediate step of the computations, instead of the exact number, we keep an interval of possible values. For inputs (that usually come from measurements), we have an interval because measurements are never 100% accurate; if the manufacturer of the measuring instrument guarantees that the measurement error is D or smaller, then the measuring result X means that the actual value is in the interval [X-D,X+D]. At each elementary computational step, we apply interval arithmetic to the corresponding intervals and produce the interval for the result; e.g., [a,b]+[c,d] leads to [a+c,b+d]. Of course, this "straightforward interval computation", that does not take dependence between intermediate results into consideration, does not always lead to efficient estimates. However, in the last 40+ years, efficient interval computations methods have been developed based on this original idea. There are a lot of interesting applications of interval computations, there is a lot of potential, but there are still a lot of open problems, situations where new techniques are needed.
Of course, this "straightforward interval computation", that does not take dependence between intermediate results into consideration, does not always lead to efficient estimates. However, in the last 40+ years, efficient interval computations methods have been developed based on this original idea. There are a lot of interesting applications of interval computations, there is a lot of potential, but there are still a lot of open problems, situations where new techniques are needed.

Let us emphasize that, besides handling the uncertainty due to measurements, intervals also prove to be very convenient and useful when it comes to performing computations with inherent uncertainty. This is the case for instance when a quantity is not known precisely (e.g., the length of a mechanic component only known to lie between 12 and 13 cm). Intervals enable to take this kind of incomplete knowledge into account, which other approaches mainly fail to handle.

One such technique that has also been used to provide guaranteed bounds is the technique of constraint propagation. This technique originated in logical AI problems, and it has been lately successfully applied to numerical problems, often in conjunction with interval methods. For example, one of the latest textbooks on interval computations, by Jaulin et al., contains robot-related practical examples of combining these two techniques. This combination has started, it is the object of interest by many researchers, it has already led to interesting and efficient packages like Numerica, but there is still a lot of room for potential improvement.

Scope of RCA'06:

We hope that our track, with an emphasis on such a combination, will bring together not only algorithm developers but also practitioners whose practical needs will help guide researchers in the proper directions.
Authors are invited to submit original papers in all areas related to the track's topics. Possible submissions fall into the following categories:

Original and unpublished research work

Report of innovative computing applications in the arts, sciences, engineering, and business areas

Report of successful technology transfer to new problem domains

Report of industrial experience and demos of new innovative systems
We encourage in particular the submission of work in progress, of work on very specialized aspects of interval computations and/or interval constraint propagation, and of work emphasizing real applications of/need for reliable computations.

The authors should send their papers electronically to Martine Ceberio. Peer groups with expertise in the track focus area will blindly review submissions to that track. Therefore the authors should submit anonymous versions of their paper(s). Accepted papers will be published in the annual conference proceedings. Submission guidelines will be posted on SAC 2006 Website.

Program:

The program of the track session can be reached here.

Session:

The track will be held on April 25, from 4pm to 5:55pm.

Conference venue:

Dijon, former capital of the Dukes of Burgundy, is a town steeped in history, proud heir to a rich architectural legacy. Dijon is one of the first sectors safeguarded in France; Dijon accounts for 97 ha of nationally classed monuments very well preserved.
Lying at the gates of the famous vineyards of the Côte de Nuits, Dijon is also one of the glories of the French gastronomic tradition, known throughout the world for its mustard, blackcurrant liqueur, gingerbread, etc.
It is also a university town, a business and cultural centre boasting a wide and varied choice of hotels, an auditorium and extensive reception facilities capable of hosting all kinds of events.

For more information, please visit either of the following websites:

Office de tourisme: here

Dijon maps and visitor information: here

Sightseeing in Dijon: here

The best of Dijon: here

Organizing committee:

Martine Ceberio (Primary contact)
University of Texas at El Paso - USA
e-mail: mceberio@utep.edu
url: http://www.cs.utep.edu/mceberio

Vladik Kreinovich
University of Texas at El Paso - USA
e-mail: vladik@utep.edu
http://www.cs.utep.edu/vladik

Michel Rueher
e-mail: rueher@essi.fr
http://www.essi.fr/~rueher

Back to top of the page