Others

This lists book chapters and other publications not in the above categories.


[2001] E. Fischer, The art of uninformed decisions: A primer to property testing, The Computational Complexity Column of The Bulletin of the European Association for Theoretical Computer Science 75 (2001), 97–126. Also in: Current Trends in Theoretical Computer Science: The Challenge of the New Century (G. Paun, G. Rozenberg and A. Salomaa eds.), World Scientific Publishing (2004), Vol. I 229–264.

Despite its relatively young age, property testing has progressed enough to merit several surveys by the time of this publication. This one gives an introduction to the field, and presents several of its methods with examples.

The version appearing here is the updated one, which appears in the “Current Trends in Theoretical Computer Science” volume that is based on the BEATCS.


[2008] E. Fischer and J. A. Makowsky, Linear recurrence relations for graph polynomials, Pillars of Computer Science: Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occasion of His 85th Birthday (A. Avron, N. Dershowitz and A. Rabinovich eds.), LNCS no. 4800 (2008), 266–279.

Suppose that you build a sequence of graphs G1, G2, G3… by applying the same elementary operations over and over again. What would this mean for the invariants of the graphs? Here it is shown that for a wide class of graph polynomials, a linear recurrence relation for calculating them will exist.


[2012] E. Fischer, T. Kotek and J. A. Makowsky, Application of logic to combinatorial sequences and their recurrence relations, Model Theoretic Methods in Finite Combinatorics, volume 558 of Contemporary Mathematics, American Mathematical Society (2012).

This paper deals with integer sequences occurring from counting the number of models satisfying a given logical sentence, centering mainly on positive recurrence results.