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.
[2025] E. Fischer, Pixelating relations and functions without adding substructures, Model Theory, Computer Science, and Graph Polynomials: Festschrift in Honor of Johann A. Makowsky (K. Meer, A. Rabinovich, E. Ravve and A. Villaveces eds.), Trends in Mathematics, Birkhäuser (2025).
The analysis in [ITCS21] depends on a lemma that allows moving from the specific limit objects (called there “orderons”) to ones whose whose values follow depend only on the partition of the domain into finitely many subcubes (thus making them “pixelated”). Here this lemma is extended to more general functions over cubes of arbitrary dimensions and without symmetry constraints. Such functions can be thought of as relations over the interval [0,1), where the natural order of this interval is “hard-coded”.
The proof uses a version of Ramsey’s theorem (also proved there) that allows the vertices to belong to a fixed number of “types”, where a minimum number of vertices from every type needs to be picked.