Steve Gismondi

Education and Employment Background

Dr. Steve Gismondi received his PhD from the University of Guelph in 1996. Between 1992 to 2000, Gismondi held several teaching positions at the University of Guelph and Wilfrid Laurier University. He joined the University of Guelph permanently in 2000 where he is now an Associate Professor in the Department of Mathematics and Statistics. In 2012, Gismondi held a position as a Visiting Scientist at Memorial University.

---

Research Themes

As early as the late 1800’s, scientists in Russia wrote about classes of mathematics problems that appeared to require “Perebor” (brute-force search) techniques for their solution. Although we can often prove existence of a solution, we’re no closer to practically solving these kinds of problems today e.g. certain kinds of secret codes are known to be breakable no matter that it can take hundreds of thousands of years of compute power to find the key. These problems are especially well known. For example, the Clay Institute offers a $1,000,000 prize for anyone that can prove whether or not it’s possible for these problems to be solved efficiently. See http://www.claymath.org/millennium-problems/p-vs-np-problem. Of course, that’s just for fun. The security of world financial transactions, military based communications, a missile launch, your iPhone, and even your front door keyless combination lock depends upon these truths.

Gismondi’s research interests are interdisciplinary and involve the study of these problems and their solutions. This is the field of classical and quantum complexity theory. Specific areas of focus include:

1. Studying heuristic solution techniques applied to NP-complete and coNP-complete decision problems. A decision problem is classified as belonging to NP if a correctly guessed decision can be verified in polynomial time e.g. “Is graph G Hamiltonian?”. The complementary problem is classified as belonging to coNP e.g. “Is G non-Hamiltonian?”. Some decision problems belong to both NP and coNP, and a subset of these decision problems are in P i.e. solvable in polynomial time e.g. “Is a linear program feasible?”. Gismondi studies coNP by searching for subsets of instances of coNP-complete decision problems for which correctly guessed decisions can be verified in polynomial time. These techniques make use of 1) properties of the Birkhoff polytope, and, 2) algorithms that decide upon the existence of a perfect matching in a bipartite graph.
2. Graph Isomorphism decision problem. Recently, Gismondi has begun to apply the above techniques to the graph isomorphism decision problem.

Highlights

• Favourite Fall Professor, University of Guelph Student Residence, 2017, 2018
• 24th Ontario Combinatorics Workshop, Organizing Committee Member, 2016
• Special Merit Award, University of Guelph Faculty Association, 2010
• Associate Fellow of the Institute of Combinatorics and Applications, 2007-2018
• Numeracy Working Group Committee Member, 2009, 2010