Here's a random list of papers in Theoretical Computer Science
with cute titles.
Ah, la recherche! Du temps perdu.
- Scott is not Always Sober. By Peter
T. Johnstone, in Continuous lattices, Lecture Notes in
Mathematics, 871 (1981), pp. 282--283.
- Coin Flipping By Telephone, A Protocol for Solving
Impossible Problems. By Manuel Blum, in SIGACT News 15(1),
1983 , pp. 23-27.
- One, Two, Three ... Infinity. Lower Bounds for
Parallel Computation. By
Faith E. Fich, Friedhelm Meyer auf der Heide, Prabhakar Ragde and
Avi Wigderson, in Proceedings of the 17th ACM
Symposium on Theory of Computing (1985), pp. 48-58.
- How Hard is it to Marry at Random? (On the
Approximation of the Permanent). By Andrei Broder,
in Proceedings of the 18th ACM
Symposium on Theory of Computing (1986), pp. 50-58.
-
Theorems for free! By Philip Wadler, in
4th International Conference on Functional Programming and
Computer Architecture (1989), pp. 347-359.
- The Art of Pointless Thinking: a Student's Guide to the
Category of Locales. By Peter T. Johnstone, in Category
theory at work, Research and Exposition in Mathematics 18 (1991),
pp. 85-107.
- Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire. By Erik Meijer, Maarten Fokkinga and Ross
Paterson, in Proceedings of the 5th ACM Conference on Functional
Programming Languages and Computer Architecture (1991), pp. 125-144.
- Mick Gets Some (the Odds Are on His
Side). By Vasek Chvátal and Bruce Reed, in
Proceedings of the 33rd IEEE Symposium on Foundations
of Computer Science (1992), pp. 620-627.
- Lively Linear Lisp - 'Look Ma, No Garbage!'
By Henry G. Baker, in ACM SIGPLAN Notices
- Highway to the Danger Zone. By Marcus Kracht, in
Journal of Logic and Computation 5(1), 1995, pp. 93-109.
- Once and For All. By Orna
Kupferman and Amir Pnueli, in Proceedings of the 10th IEEE
Symposium on Logic in Computer Science (1995), pp. 25-35.
- Once upon a Type. By David N. Turner, Philip
Wadler and Christian Mossin, in ACM Conference on Functional
Programming Languages and Computer Architecture, 1995, pp. 1-11.
- The Satanic Notations: Counting Classes beyond #P and
Other Definitional Adventures. By Lane Hemaspaandra and
Heribert Vollmer, in SIGACT News 26(1), 1995, pp. 2-13.
- See More through Lenses than Bananas. By La
Monte H. Yarroll, in Theoretical Computer Science 169(1), 1996,
pp. 113-121.
- Buy One, Get One Free!!!. By Orna Kupferman and
Orna Grumberg, in Journal of Logic and Computation 6(4), 1996,
pp. 523-539.
- To Weight or not to Weight: Where is the
Question?. By Pierluigi Crescenzi, Riccardo Silvestri and
Luca Trevisan, in Proceedings of the 4th Israeli Symposium
on Theory of Computing and Systems, 1996, pp. 68-77.
- Six Hypotheses in Search of a Theorem. By Harry
Buhrman, Lance Fortnow and Leen Torenvliet, in Proceedings of the
12th IEEE Conference on Computational Complexity (1997),
pp. 2-12.
- When Scott is Weak on the Top. By Abbas Edalat,
in Mathematical Structures in Computer Science 7(1), 1997,
pp. 401-417.
- When Hamming Meets Euclid: the Approximability of
Geometric TSP and MST. By Luca Trevisan, in Proceedings of
the 29th ACM Symposium on Theory of Computing (1997),
pp. 21-29.
- Pipes, cigars, and kreplach: the union of Minkowski sums in three dimensions.
By Pankaj K. Agarwal and Micha Sharir, in Proceedings of the
15th Annual Symposium on Computational Geometry (1999),
pp. 143-153.
- Achilles and the Tortoise Climbing Up the Arithmetical
Hierarchy. By Eugene Asarin and Oded Maler, in Journal of
Computer and System Sciences 57(3), 1999, pp. 389-398.
- Repetitive Perhaps, but Certainly Not Boring. By
W.F. Smyth, in Theoretical Computer Science 249(2), 2000,
pp. 343-355.
- A Smaller Sleeping Bag for a Baby Snake. By
Johan Håstad, Svante Linusson and Johan Wästlund, in Discrete and
Computational Geometry 26, 2001, pp. 173-181.
- Random 3-SAT: The Plot Thickens.
By Cristian Coarfa, Demetrios D. Demopoulos,
Alfonso San Miguel Aguirre, Devika Subramanian and Moshe Y. Vardi,
in Principles and Practice of Constraint Programming - CP 2000,
6th International Conference, Proceedings. Springer LNCS 1894, pp.
143-159.
- Many Happy Returns. By Olivier Danvy, in Typed
Lambda Calculi and Applications 2001, 5th International Conference,
Proceedings, Springer LNCS 2044, p. 1.
- The Importance of Being Biased. By Irit Dinur
and Shmuel Safra, in Proceedings of
the 34th ACM Symposium on Theory of Computing (2002), pp. 33-42.
- A Bit of Abstinence (Provably) Promotes
Satisfaction. By Dimitris Achlioptas and Chris Moore, in the
5th International Symposium on the Theory and Applications
of Satisfiability Testing (SAT 2002).
- Vacuum Cleaning CTL Formulae. By Mitra
Purandare and Fabio Somenzi, in Computer Aided Verification, 14th
International Conference, CAV 2002, Proceedings, Springer LNCS 2404,
pp. 485-499.
- Do Not Read This. By Juan Bicarregui, in
FME 2002: Formal Methods - Getting IT Right, International
Symposium of Formal Methods Europe, 2002, Proceedings. Springer
LNCS 2391.
- No Coreset, No Cry. By Sariel Har-Peled, in
FSTTCS 2004: Foundations of Software Technology and Theoretical
Computer Science, 24th International Conference, Proceedings.
Springer LNCS 3328, pp. 324-335, 2004
- This Side Up!. By Leah Epstein and Rob van Stee,
in Persiano, G. and Solis-Oba, R. (Eds.), Approximation and
Online Algorithms: Second International Workshop, WAOA 2004,
Bergen, Norway, September 14-16, 2004, Revised Selected
Papers. Springer LNCS 3351, pp. 48-60, 2005.
Thanks to Andreas Abel, Klaus Aehlig, Hubie Chen, Chris Gray, David Molnar, Deepak
Ramachandran, Robert Reitmeier, Ulrich Schöpp, Alasdair Urquhart and Rolf Wanka for
contributions to this list.
The motto is from Quotients
homophone des groupes libres - Homophonic quotients of free
groups, by J.-F. Mestre, R. Schoof, L. Washington and
D. Zagier, in Experimental Mathematics 2 (1993) pp. 153-155.
It was pointed out by Gerit Sonntag.
Please send me any suggestions for inclusions by email.
Back to my home
page.