Research Overview

Boolean Satisfiability

My research for my Master's thesis resulted in a new algorithm for determining whether a general boolean expression (not necessarily in CNF or DNF) is satisfiable. The algorithm assumes that an expression evaluates to true, reverse propagates that constraint, constructs a constraint tree, and from that constructs a directed acyclic graph of constraints having a single source and sink. The expression is satisfiable iff there exists a consistent set of constraints along a path from the source to the sink. Assuming that the expression evaluates to false can be used for falsifiability testing. The constraint calculus that I defined was proven to be both sound and complete. The algorithm has some ordering parameters and I did some preliminary studies of the effects of settings for these parameters on algorithm efficiency. I also sought and found some metrics that were predictive of satisfiability, falsifiability, and the amount of work the algorithm would need to determine the logical class of an expression.

Status: In the past year, I've written several posts on this for my blog. I'd really enjoy spending more time on this problem, but it will be dormant for a while.

Boolean Simplification

My research for my doctoral dissertation resulted in a new algorithm for simplifying a general boolean expression to a canonical logically equivalent expression. The reduction process operates upon a constraint tree. I found a set of eight reductive graph transformations that form a complete set of reductions, meaning that if the eight reductions are applied in any order to any application sites in the tree until no further application is possible, the same canonical constraint tree will result. This property allowed me to concerned with efficiency rather than minimality. Proving that this set of reductions was complete and providing an algorithm for the reduction process were the central results of my dissertation. This algorithm has ordering parameters that were not explored at that time. I sought and found some metrics that were predictive of the amount of work required for reduction and the size of the resulting reduced expressions. It was during this research that I first considered the problem of how to choose the best tools for a task (see Adaptive Market Pattern).

Status: I have only revisited this problem occasionally over the past several years. I have thought of some additional reductions and would like to explore some new ideas. Much more should be done, and I'd like to work on it again. In the past year, I've written several posts on this for my blog and brought my code for reduction to elegance up to date. I'd really enjoy spending more time on this, but it will be dormant for a while.

k-Clique Exists

Determining whether a graph contains a clique of size k remains my favorite problem - it has fascinated me for the past eighteen years. I have worked on six new algorithms for its solution. A clique is a complete subgraph of a graph - there is an edge between every pair of nodes in a clique. The approach that I've been focusing on for the past several years began as an investigation of a classic searching technique. It changed into a studies on the reduction of the search space and has become an exercise in squeezing blood from a stone. The reduction of the search space now often solves the problem and actually performing a search is most often not necessary.

Status: Each of the six algorithms needs more work, but I am focusing on the search approach as the most promising. I plan to spend much of my spare time on this algorithm framework over the next several years. Writing up this work will take a lot of time and remains a priority.

Maximum Cliques and Maximum Clique Size

These are the problems of finding the maximum cliques of a graph - the cliques having the largest size and the size of these largest cliques. The approach that I've favored is an adaptation of my splitting algorithm for finding the maximal cliques of a graph.

Status: I think I can do much better and hope to spend more time on this problem. This is in my current working set.

Maximal Cliques

A maximal clique is a clique that is not a proper subgraph of any other clique of the graph. The Maximal Cliques problem is the construction of the set of the maximal cliques of a graph. I found a way to use a splitting technique to build up the set of maximal cliques. A few years ago, when a European telecommunications company (Vodafone) was looking for a better maximal cliques problem, I ran two of their sample graphs through my algorithm. It was able to construct complete sets of maximal cliques for the graphs in minutes, while their algorithm was having trouble producing incomplete sets over the course of a weekend. They confirmed the correctness of my solutions down to the threshold that their algorithm had been permitted to use. I believe that they were doing this weekly processing to verify cell coverage in a cellular network.

Status: The algorithm has ordering and size parameters that need to be explored. The basic theory and algorithm are straightforward and have been written up in my blog. Many enhancements are possible.

Graph Isomorphism

Several years ago, a friend and colleague noticed my obsession with the k-Clique Exists problem and told me a cautionary tale of his many-year obsession with the Graph Isomorphism problem. His tale did not have the desired effect - I fell in love with the Graph Isomorphism problem as well. The Graph Isomorphism problem is determining whether two labeled, undirected, and unweighted graphs are identical except for their labeling. I wandered down several paths, most of them well-worn, for a few years. I thought of a new approach for constructing the canonical representation for a graph and have worked on the theory and implementation for much of the past few years.

Status: The basic algorithm is beautiful and works efficiently, but I found that, for some graphs, a supplement to the basic algorithm is needed. Most of my time has been spent on this supplement. I think I've nearly got it pinned down - I'm almost done with the proofs and have to rework the implementation of the supplement. I really need to finish this work as soon as possible.

Subgraph Isomorphism

This is the problem of determining whether a proper induced subgraph of one graph is isomorphic to a second graph. The approach that I've taken for solving Graph Isomorphism shows promise as the seed of an approach for solving this problem.

Status: I've been jotting down ideas, but need to finish my work on Graph Ismorphism before I can use it as the starting point for work on Subgraph Isomorphism.

Factoring Composite Integers Into Two Factors

Inspired by the no-longer-active RSA Labs Factoring Challenge, I've worked on a new algorithm framework for factoring a composite integer into two factors. This is a beautiful problem and I wish I could devote large blocks of time to it, but it has lower priority for me given the time and attention needs of some other problems.

Status: Much more time needs to be spent both on the theory and implementation. I've only recently begun to write this up for my blog. Dormant for now.

The Adaptive Market Pattern

This is the pattern for a multi-level free-market framework for selecting and applying the best tools for tasks that learns from experience and incorporates the elements of prediction, estimation, bidding, reputation, and adaptation. I first became interested in this problem when thinking about how to choose the best tool (algorithm + parameters) for determining the satisfiability of general boolean expressions. I continued to encounter this problem and decided to generalize it into a pattern.

Status: I have been thinking about this pattern a great deal, especially in the context of problem-solving services. I have written some blog posts on the topic. It will be dormant for a while.

Problem-Solving Services

For several years, I've been interested in how a commercial problem-solving service could be organized. What I envision is software as a service, accessible through the internet, that would publish a catalog of problems it could solve (including many NP-complete and other challenging problems), accept instances of these problems to solve, and use the best algorithms and its experience with solving similar problems to attempt to solve these instances as efficiently as it can. This is an overview of this service.

Status: I've been doing a lot of thinking about this recently and have written up some blog entries on it. I am increasingly persuaded that it could be a viable business venture. It will be dormant for a while.

Active Blackboards

A blackboard is a software construct that can hold and serve objects of many varieties. At its simplest, it is a container of named objects. I'm interested in blackboards that can do far more. I've had fun thinking about templates for blackboards (e.g. crime investigation), blackboards that can perform reasoning, and blackboards that can perform tasks as appropriate. Blackboards should have the ability to source and history of all facts and deductions as well as a measure of confidence that can be justified. Blackboards should also be able to support What-If analysis. I could really use some of these enhanced blackboards for implementing some algorithms, the Adaptive Market pattern, and problem-solving systems.

Status: Still in the thinking stage. Definitely in my working set, as this is an enabling technology for some of my other work.

Netflix Prize Rating Prediction

A few years ago, Netflix posted a large database of customer ratings of movies and challenged people to improve on Netflix's own methods for predicting how customers will rate movies. Due to a death in my family, I stopped working on this problem at the end of December 2006 and have worked on it only itermittently since. I have an approach for developing the rating prediction system and algorithms for most of the pieces of the system. I've implemented some algorithms that perform cluster definition for corated movies by making use of my maximal cliques algorithm. Much more could be done on this problem, including working on the algorithms for determining the strength of a movie's membership in a cluster, the strength of a customer's cluster affinity, and the final rating prediction algorithm. I am hopeful that my approach will address and overcome many of the weakness that other approaches have been exhibiting.

Status: I haven't been working on this problem for some time - too many distractions, including Eternity II.

Eternity II

Several months ago, a good friend introduced me to the Eternity II puzzle, which is an evil masterpiece. Not only is the well-designed puzzle apparently immune to brute force attacks (it remained unsolved after a year and a half of serious attempts worldwide), but there is a signficant cash prize that will be awarded to the person submitting the first solution. Status: I have more ideas than time, and it has invaded my dreams.

Status: Much thinking, little programming as yet. In my working set and occasionaly rises to the top.

Emergent-Network Dataflow Processing

When I took my first course in computer architecture, my professor introduced the topic of dataflow processing by describing it as a pool of fundamental processing elements out of which could be woven as needed a network for solving a specific problem through which data could flow. I thought that was beautiful and was disappointed that the current implementations of dataflow processing were much more prosaic. I decided several years ago that the design and simulation of such an emergent-network dataflow processor would be great fun.

Status: I have made some progress on the architecture and design of such a processor but have spent little time on it over the last several years.

The Business Object Model and Rule Systems Methodology

My focus in graduate school was on automated theorem proving, automated reasoning, and deductive databases. I later spent three and a half years with Blue Cross Blue Shield of Minnesota as their rule systems architect, helping to spearhead an enterprise-wide rule systems initiative. My task was to find the best ways of incorporating rule-based reasoning and business rule engines into the data processing environment of a major insurance company.

I spent a lot of time thinking about the design of an engine-agnostic repository for business rules and, later, for an entire business object model. I also made some advances in adapting their methodology to the coexistence of traditional programming with a rule systems approach.

Status: I find the problems that I wrestled with exciting, but they have to take a back seat to the algorithm work that I'm doing now. Dormant for now.

The Riemann Hypothesis

I never expected to have more than an amateur's interest in this problem, but I made the mistake of playing with it and found an approach that is promising. My approach is based upon Denjoy's Probablistic Interpretation of the hypothesis. I'm persuaded that the hypothesis is true but only have the roughest outline of a proof and a few spaces in the proof filled in.

Status: All the makings of a life-long obsession. Great fun and high stakes.

Copyright and Legal Notices

All Rights Reserved.