Lattice Theory with Applications

One of the themes of my research has been to explore computational aspects of lattice theory with applications to distributed computing and combinatorics. I gave an invited lecture in the national meeting of American Monthly Society on the topic in 2006. Some specific contributions include:

• Incremental Optimal Chain Partition: We give an incremental algorithm to maintain optimal chain partition of posets, (ICDCS'06)
• Algorithmic Combinatorics: A combinatorial problem usually requires enumerating, counting or ascertaining existence of structures that satisfy a given property B in a set of structures L. This paper describes a technique based on a generalization of Birkhoff's Theorem of representation of finite distributive lattices that can be used for solving such problems mechanically and efficiently. Specifically, we give an efficient (polynomial time) algorithm to enumerate, count or detect structures that satisfy B when the total set of structures is large but the set of structures satisfying B is small. We illustrate our techniques by analyzing problems in integer partitions, set families, and set of permutations. (FSTTCS'02, Theoretical Computer Science'06)
• Enumerating Global States of a Distributed Computation: We give an efficient algorithm that perform the lex traversal of the lattice. We also give a space efficient algorithm for the breadth-first-search (BFS) traversal. (PDCS'03)