Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Cameo of a Consummate Computabilist Read chapter Read first chapter

2017 | OriginalPaper | Chapter

Surfing with Rod

Author : Michael R. Fellows

Published in: Computability and Complexity

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

I wish Rod a happy birthday. Rod has offered a good historical account of our early days of collaboration in his paper, “The Birth and Early Days of Parameterized Complexity” [D12]. One of the themes of our life-long collaboration has been a shared passion for surfing, and many of our best ideas were hammered out on surf trips. This contribution is best viewed as a gloss on that earlier account by Rod, taking as an organizing skeleton, our various surf trips and what we were thinking about, with a particular emphasis on open problems and horizons that remain, and some reflections on the formation of our research community.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Cameo of a Consummate Computabilist
next chapter Prequel to the Cornell Computer Science Department
Footnotes
1
Most surfers do not surf alone, because it is a statistically proven fact that if you do not surf alone, your chances of being taken by a shark are improved by at least fifty percent.
 
2
Stand-up surfers look down on body-boarders, but they shouldn’t! Body-boarders can routinely catch waves that stand-up guys can’t, because bodyboarders have stronger sprinting ability, and the stability to handle a lip-launch as the wave breaks “late” (which involves flying through the air a bit). One could go on about this. There are lots of ways to have fun in the waves. When I first met Rod, he was a hand-gunner, which is a rare practice (except in Queensland) closely related to plain old body-surfing.
 
3
This is a mainstay of the community. There is a sort of informal award system for the best young researchers in the field, which is to receive a copy of what we call “Mr. Opinion” — this is the book: The New Guide to Modern World Literature by Martin Seymour-Smith.
 
4
This is not unheard-of in mathematics, that smaller “dimensions” require special approaches.
 
Literature
[AEFM89]
Abrahamson, K., Ellis, J., Fellows, M., Mata, M.: On the complexity of fixed-parameter problems. In: Proceedings of 13th FOCS, pp. 210–215 (1989)
[BDFH08]
Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels (extended abstract). In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5125, pp. 563–574. Springer, Heidelberg (2008). doi:10.​1007/​978-3-540-70575-8_​46 CrossRef
[BFH94]
Bodlaender, H., Fellows, M.R., Hallett, M.T.: Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy. In: Proceedings of ACM Symposium on Theory of Computing (STOC), pp. 449–458 (1994)
[CCDF97]
Cai, L., Chen, J., Downey, R., Fellows, M.: Advice classes of parameterized tractability. Ann. Pure Appl. Logic 84, 119–138 (1997)MathSciNetCrossRefMATH
[D97]
Dinneen, M.: Too many minor order obstructions (for parameterized lower ideals). J. Univers. Comput. Sci. 3, 1199–1206 (1997)MathSciNetMATH
[D12]
Downey, R.: The birth and early years of parameterized complexity. In: Bodlaender, H.L., Downey, R., Fomin, F.V., Marx, D. (eds.) The Multivariate Algorithmic Revolution and Beyond. LNCS, vol. 7370, pp. 17–38. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-30891-8_​2 CrossRef
[DFS98]
Downey, R., Fellows, M., Stege, U.: Parameterized complexity: a framework for systematically confronting computational intractability. In: Graham, R., Krachovil, J., Nesetril, J., Roberts, F. (eds.) Contemporary Trends in Discrete Mathematics, DIMACS, vol. 49, pp. 49–100. American Mathematical Society, Providence (1999)
[DFR98]
Downey, R.G., Fellows, M.R., Regan, K.W.: Parameterized circuit complexity and the W hierarchy. Theoret. Comput. Sci. A 191, 91–115 (1998)MathSciNetCrossRefMATH
[DFR98b]
Downey, R.G., Fellows, M., Regan, K.: Threshold dominating sets and an improved characterization of \(W\)[2]. Theoret. Comput. Sci. A 209, 123–140 (1998)MathSciNetCrossRefMATH
[DFT96]
Downey, R.G., Fellows, M., Taylor, U.: The parameterized complexity of relational database queries, an improved characterization of \(W\)[1]. In: Combinatorics, Complexity and Logic: Proceedings of DMTCS 1996, pp. 194–213. Springer, Heidelberg (1997)
[DFVW99]
Downey, R., Fellows, M., Vardy, A., Whittle, G.: The parameterized complexity of some fundamental problems in coding theory. SIAM J. Comput. 29, 545–570 (1999)MathSciNetCrossRefMATH
[FL87]
Fellows, M., Langston, M.: Nonconstructive proofs of polynomial-time complexity. Inf. Process. Lett. 26, 157–162 (1987/1988)
[FL88]
Fellows, M., Langston, M.: Nonconstructive tools for proving polynomial-time complexity. J. Assoc. Comput. Mach. 35, 727–739 (1988)MathSciNetCrossRefMATH
Metadata
Title
Surfing with Rod
Author
Michael R. Fellows
Copyright Year
2017
Book
Computability and Complexity

Print ISBN: 978-3-319-50061-4

Electronic ISBN: 978-3-319-50062-1

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-50062-1_2

Premium Partner

    Image Credits