last update: Feb. 23, 2005

Workshop on New Horizons in Computing (NHC)

-- Recent Trends in Theoretical Computer Science --

Feb. 28 - Mar. 3, 2005,
Kyoto Royal Hotel, Kyoto, Japan

Kinkaku-ji Temple Fushimi-Inari Shrine

 - Program
 - Registration
 - Site Map
 - Workshop Photos  [ new ! ]
Travel & Lodging
 - Accomodation
 - Location
 - Transportation


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.

List of Speakers

  • Susanne Albers (Freiburg)
  • Avrim Blum (CMU)
  • Timothy Chan (Waterloo)
  • Richard Cole (NYU)
  • Josep Diaz (UPC)
  • Herbert Edelsbrunner (Duke)
  • Martin Farach-Colton (Rutgers)
  • Uriel Feige (Weizmann)
  • Lisa Fleischer (IBM)
  • Lance Fortnow (Chicago)
  • Tao Jiang (UC Riverside)
  • Ming Li (Waterloo)
  • Kazuhisa Makino (Osaka)
  • Jiri Matousek (Charles)
  • S. Muthukrishnan (Rutgers)
  • Seffi Naor (Technion)
  • R. Ravi (CMU)
  • David Shmoys (Cornell)
  • Mikkel Thorup (AT&T)
  • Osamu Watanabe (Tokyo Inst. Tech.)
  • Uri Zwick (Tel-Aviv)


Each of the four days has three or four talks in the morning, lunch, and two talks in the late evening. We may arrange a session for short contributed talks (if you are interested, please let us know). There will be a reception and a dinner. (More events like a small excursion and discussion sessions will also be considered.)

  • Program

  • Registration

    Registration fee is 15,000 Japanese yen for regular registration (including all the events) and 5,000 yen for student registration (excluding reception and dinner). Payment will be received in cash (JPY) on-site.

    Online registration has been closed. (Due date: Feb. 15 17:00 JST)

  • Site Map

    Site Map (PDF)

Travel & Lodging

Organizing Committee

  • Magnus Halldorsson (Co-Chair, University of Iceland, Iceland)
  • Takeshi Tokuyama (Co-Chair, Tohoku University, Japan)
  • Kazuo Iwama (Kyoto University, Japan, Chair of the New Horizon Project)
  • Hiro Ito (Kyoto University, Japan)

Questions or Comments

Please send an e-mail to