RCA'07 is the third 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'07 between March 11 and 15, in Seoul (South Korea).

SAC'2007

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 2007 is sponsored by the ACM Special Interest Group on Applied Computing and hosted by Seoul National University in Seoul and Suwon University in Gyeonggi-do.

Overview of RCA'07:

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'07:

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 2007 Website.

Submission:

The deadline for submission is September 8th, 2006.
Prospective authors should send their papers electronically to Martine Ceberio, with "[RCA'07] Submission" as the subject of the e-mail. In addition, the paper should be:

no more than 5 pages long;

submitted in postscript or pdf format;

without the authors' names;

formatted using the style of last year's conference (for information, you can find here, the zip files of the instruction to Authors of SAC'05; updated information will be posted here as soon as available).

IMPORTANT INFORMATION: Every author must ALSO register their paper(s) and submit the abstract(s) before the abstract submission deadline date (September 8, 2006). In order to register the paper, the author must submit the electronic form, available here.

Abstract Submission Guidelines: Authors must register their intent to submit a paper by submitting an electronic abstract (in text format) of a maximum length of 200 words by the due date prior to the actual submission and obtain a paper identification number. Prior to submitting the abstract, authors will be required to register as users on the system. Once an author has submitted an abstract, he/she will receive a confirmation email with instructions on submitting the paper. The format of the submitted paper must be PDF or Postscript.

Let us also recall the prospective authors that the acceptance rate at SAC is set to 33 to 36%. Therefore, we strongly encourage authors not to hesitate to submit several articles.

Important dates:

Paper Submission deadline	September, 8th
Notification of acceptance	October, 16th
Camera-ready version deadline	October, 30th

Conference venue:

Seoul is the biggest city of the Republic of Korea (South Korea), and its capital. Before 1945, it was the capital of all Korea. Since South Korea was started in 1948, it has been the capital, except for a short time during the Korean War. It has a population of 10,276,968, and is 610 km² wide.
Seoul is located in the middle of the Korean Peninsula, on the Han River near the sea. It is in the northern part of South Korea. It is not far from Korean Demilitarized Zone (DMZ), a buffer zone between North Korea and South Korea.
Seoul is the center of politics, economy, culture, transportation, and education for South Korea.

Seoul is one of oldest cities in Korea. Its history can be traced to the year 18 BC. The Goryeo Dynasty built a palace in Seoul, which was called "the Southern Capital". Later dynasties, including the Joseon Dynasty, also made Seoul their capital. It was still the capital during the colonisation by Japan from 1910 until 1945.
Seoul hosted the Olympic Games in the summer of 1988.

(Information taken from http://simple.wikipedia.org/wiki/Seoul)

Organizing committee:

Martine Ceberio (Primary contact)
University of Texas at El Paso - USA
e-mail: mceberio 'at' cs.utep.edu
website

Vladik Kreinovich
University of Texas at El Paso - USA
e-mail: vladik 'at' cs.utep.edu
website

Michel Rueher
University of Nice-Sophia Antipolis
e-mail: rueher 'at' essi.fr
website

Back to top of the page