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 17^th 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 18^th ACM Symposium on Theory of Computing (1986), pp. 50-58.

• Theorems for free! By Philip Wadler, in 4^th 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 33^rd 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 10^th 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 4^th 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 12^th 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 29^th 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 15^th 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 34^th 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 5^th 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.

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.