Science of Information Seminar: P4-free Partition and Cover Numbers

Dr. Hemanta Maji, Assistant Professor of Computer Science, Purdue University will present an online seminar titled "P4-free Partition and Cover Numbers", as part of the Fall 2020 Science of Information Seminar Series.

Wednesday, November 18, 2 PM (EST)

Online Meeting Link: https://purdue-edu.zoom.us/j/96294915839

Title: P4-free Partition and Cover Numbers

Abstract: P4-free graphs -- also known as cographs, complement-reducible graphs, or hereditary Dacey graphs -- have been well studied in graph theory. This work introduces the graph properties of partitioning and covering a graph's edges with the minimum number of P4-free graphs, namely, the P4-free partition and cover numbers, respectively. We prove that computing these numbers for general graphs is NP-complete, even for bipartite graphs. We present bipartite graph constructions where these numbers are large. Finally, we upper bound these numbers for bipartite graphs encoding well-studied Boolean functions from circuit complexity, like set intersection and disjointness function, and the inequality function.

The talk shall elaborate on fundamental representative applications of P4-free partition and cover numbers in information theory, communication complexity, cryptography, and combinatorial optimization by encoding joint probability distributions and Boolean functions as bipartite graphs.

 

Bio: Hemanta Maji is an Assistant Professor of Computer Science at Purdue University. Dr. Maji received his doctorate in computer science from University of Illinois at Urbana-Champaign. He was a Computing Innovations Fellow from 2011-2013, and then joined the Center for Encrypted Functionalities at UCLA as a Research Fellow prior to joining the faculty at Purdue. Dr. Maji is interested in cryptography and algorithms; with special emphasis on secure computation and information-theoretic cryptography. Hemanta K. Maji's Faculty Page