Marco Cesati's research page
In the design of sophisticated digital systems, elegance is not a dispensable
luxury but a matter of life and death, being a major factor that decides
between success and failure.
Edsger W. Dijkstra
I'm currently working in two different fields: Parameterized Computational Complexity and Operating Systems Research. I'm also interested in
Algorithms and Data Structures and in Computer
Networks.
Parameterized Complexity is a well-established field of
Computational Complexity. It was introduced by Mike Fellows and Rod
Downey in early 1990's. If you are interested, look at the Parameterized
Complexity home page, or directly at a list of
people working on it. (I have another non exhaustive list of people, which is largely overlapping
with the official one.)
The First Workshop on
Parameterized Complexity was held in Chennai, India,
December 7-9, 2000. You can look at some
pictures of the participants.
The Dagstuhl Seminar
on Parameterized Complexity was held in Dagstuhl, Germany,
July 29-August 3, 2001. (Unfortunately, I was
unable to attend.)
The Pre-Conference Workshop
on Complexity and Parameters: Logic and Structure will be held
on the two days prior to the FST-TCS conference at IIT, Kanpur, India.
I'm currently maintaining a unofficial Compendium of
Parameterized Problems,
Selected papers:
- M. Cesati, ``The Turing Way to Parameterized
Complexity'', Journal of Computer and System Sciences 67 (2003) 654-685
(Special Issue on Parameterized Computation
and Complexity, J. Chen and M. R. Fellows guest editors).
[Abstract]
- M. Cesati, ``Perfect Code is W[1]-complete'', Information
Processing Letters (81)3 163-168, 2002, Elsevier. A preliminary
version is available as
ECCC Report TR00-080, accepted on Sep 22, 2000. [Abstract]
- M. Cesati, M. Di Ianni, ``Parameterized Parallel Complexity'',
Proc. 4th International ACM/IFIP Euro-Par Conference on Parallel
Processing, Southampton, UK, September 1998. Lecture Notes in
Computer Science 1470, pp. 892-896. [Abstract] A preliminary version is available as
ECCC Report TR97-006
- M. Cesati, L. Trevisan, ``On the Efficiency of Polynomial Time
Approximation Schemes'', Information Processing Letters, 64(47)
165-171, 1997, Elsevier. [Abstract] [PostScript] [PDF] A
preliminary version is also available as
ECCC Report TR97-001
- M. Cesati, M. Di Ianni, ``Computational Model for Parameterized
Complexity'', Mathematical Logic Quarterly, 43 (1997), 179-202,
Johann Ambrosius Barth [Abstract]
- M. Cesati, M. Fellows, ``Sparse Parameterized Problems'',
Annals of Pure and Applied Logic 82 (1996) 1-15, Elsevier [Abstract]
- M. Cesati, H. T. Wareham, ``Parameterized Complexity Analysis
in Robot Motion Planning'', Proc. 25th IEEE Int. Conf. on Systems,
Man and Cybernetics, Vancouver, B.C., Canada, March 1995
[PostScript] [PDF]
Books:
- D. P. Bovet, M. Cesati, Understanding the
Linux Kernel, O'Reilly & Associates, Inc., 2000
(it covers the Linux kernel 2.2)
- D. P. Bovet, M. Cesati, Understanding the
Linux Kernel, 2nd edition, O'Reilly & Associates, Inc., 2002
(it covers the Linux kernel 2.4)
Articles:
- D. P. Bovet, M. Cesati, ``A Real Bottom-Up Operating System
Course'', Operating System Reviews 35(1), pp. 48-60, ACM Press,
January 2001. [PostScript] [PDF]