Steve Gismondi

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. 

My own research interests are interdisciplinary and involve the study of these problems and their solutions. This is the field of classical and quantum complexity theory. In particular, my interests are focused upon 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?”. I study 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. I have recently begun to apply these techniques to the Graph Isomorphism decision problem. 

Prospective graduate students should have an excellent background in computational sciences and computing skills or willingness to improve them (i.e. ability to design, code, and test scientific applications in FORTRAN or C++).