Logic List Mailing Archive

New Horizons in Computing (Feb/Mar 2005, Kyoto)

Call for participation

               Workshop on Hew Horizons in Computing (NHC)
           -- Recent Trends in Theoretical Computer Science --

                    Feb 28 - Mar 3, 2005, Kyoto, Japan

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)

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)

Meeting Format
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.)  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).  A block of rooms are
being held at Kyoto Royal Hotel for 10,000 yen per night per person
including breakfast and tax.

For more details
Workshop: http://keisan-genkai.lab2.kuis.kyoto-u.ac.jp/nhc/
Project: http://keisan-genkai.lab2.kuis.kyoto-u.ac.jp/index.en.html
Contact: nhc@lab2.kuis.kyoto-u.ac.jp