The category of intractable (typically NP-hard) problems includes great many problems of fundamental and practical importance. When we encounter such a problem, we are forced to try to solve it in some way within a reasonable amount of time. This is generally bound to lead to a sacrifice on the optimality of the solution. In that case it is much preferable to be able to use an algorithm for which we know the maximum amount of this sacrifice mathematically or whose performance is rigorously guaranteed. In the past two decades, researchers have spent a lot of effort towards this goal, i.e., studying how to guarantee the performance of combinatorial optimization algorithms. Fortunately our level of knowledge on this topic has dramatically improved.
For example, we know that there is a sizable family, called PTAS, of problems for which we can design an arbitrarily good approximation algorithm running in polynomial time. Many online problems have competitive algorithms which can give us, without information of the future input, a solution whose cost is within only a constant factor away from the optimal offline solution which needs complete (future) information of the instance. For certain kinds of problems randomization works well, giving us a constant success probability (BPP). Its quantum counterpart (BQP) became a sensation after the discovery of the integer factoring algorithm. Also, several techniques were invented on the negative side, typically for proving lower bounds of approximation factors, many of which derived from the theory of Probabilistically Correct Proofs (PCP).
This line of research has recently been expanded into several interesting directions, providing new models for the design and analysis of contemporary algorithms, such as those for property testing, lattice problems, extraction, drawing, meta heuristics, truthful auction, web graphs, data mining, and many more. These new trends are still emerging and the situation is rapidly changing. To capture these many new exciting opportunities for our research community, a new theory project, "New Horizons in Computing" funded by the Ministry of Education in Japan for the next four years, has started in September 2004.
The NHC workshop is to kick off this project, consisting of some 20 invited talks by world-leading researchers. These will illustrate cutting-edge research, explore current trends, and glimpse future visions in theoretical computer science.