Efficient algorithms for dualisation problem for subclasses of Boolean functions

Murali EnduriSERB-DST projects aim to build up the best systems that would match the best global practices in the area of promotion and funding of basic research. Dr Murali Krishna Enduri, Assistant Professor, Department of Computer Science Engineering at SRM University-AP is yet another faculty member who has obtained a project with a total outlay of ₹18 lacs for a duration of three years. The project is sanctioned under the scheme of Teachers Associateship for Research Excellence (TARE) of SERB-DST, Government of India.

In the duality theory, the dual problem is the problem of checking the duality of a pair of monotone Boolean expressions in disjunctive normal form. Problem: DUAL Input: The complete DNF of two monotone Boolean functions, f and g. Output: If f is dual of g. Whether the problem DUAL admits a polynomial-time algorithm has been one of the challenging open problems in the field of Duality theory of Boolean function for the last 35 years. It is one of the few problems whose polynomial-time solvability is still unknown. So, this problem is important in complexity theory due to its unknown complexity status and it plays a central role in various applications arising in computational logic, data mining, reliability theory, artificial intelligence and game theory etc. The project goal is to solve the dual problem for an interesting class of Boolean functions. Improving the existing complexity results of the DUAL problem for a particular class of Boolean functions is a challenging task.

Few applications of the project are as follows:
Type error diagnosis: Type error diagnosis is the task of generating an explanation for some error. It requires finding all minimal unsatisfiable subsets of a given set of constraints (representing the error) which can be managed via solving the computational variant of Dual in its minimal transversal formulation.

Computational medicine: Optimal vaccination strategies are given a subset of initially infected individuals from a population of individuals and assumptions about disease transmission. The task of computing inclusion minimal vaccination strategies can be solved using the computational variant of Dual in its transversal hypergraph formulation.

The project will be carried out in collaboration with IIT Madras (Dr Jayalal Sarma, Associate Professor, Department of Computer Science & Engineering, Indian Institute of Technology Madras, Chennai, India.)

Leave a Reply

Your email address will not be published. Required fields are marked *