Sheikh Azizul Hakim

Sheikh Azizul Hakim, Md. Shamsuzzoha Bayzid

Pairwise Compatibility Graphs (PCGs) form a tree-metric graph class that originated in phylogeny and has since attracted sustained interest in graph theory. Several natural generalizations have been proposed in order to overcome the expressive limitations of classical PCGs, including $k$-interval-PCGs, $k$-OR-PCGs, and $k$-AND-PCGs. In this paper, we introduce $(k,t)$-threshold-PCGs, a threshold-based framework that unifies these generalized notions: adjacency is determined by whether at least $t$ among $k$ underlying PCG predicates accept the vertex pair. We investigate the expressive power of this model from both constructive and asymptotic viewpoints. On the positive side, we show that every graph on $n$ vertices is a $(n,t)$-threshold-PCG for every $1 \le t \le n$. On the negative side, we prove that for every fixed pair $(k,t)$, the class of $(k,t)$-threshold-PCGs is asymptotically rare among all graphs. As a consequence, we obtain sharp separations from previously studied models, including a strict expressive gap relative to $k$-interval-PCGs. We also study explicit obstruction families through incidence graphs and derive additional structural consequences for the conjunction case, including the strictness of the $k$-AND-PCG hierarchy and the failure of closure under complement.

MD Sadik Hossain Shanto, Mahir Labib Dihan, Souvik Ghosh et al.

This report presents our approach for the IEEE SP Cup 2025: Deepfake Face Detection in the Wild (DFWild-Cup), focusing on detecting deepfakes across diverse datasets. Our methodology employs advanced backbone models, including MaxViT, CoAtNet, and EVA-02, fine-tuned using supervised contrastive loss to enhance feature separation. These models were specifically chosen for their complementary strengths. Integration of convolution layers and strided attention in MaxViT is well-suited for detecting local features. In contrast, hybrid use of convolution and attention mechanisms in CoAtNet effectively captures multi-scale features. Robust pretraining with masked image modeling of EVA-02 excels at capturing global features. After training, we freeze the parameters of these models and train the classification heads. Finally, a majority voting ensemble is employed to combine the predictions from these models, improving robustness and generalization to unseen scenarios. The proposed system addresses the challenges of detecting deepfakes in real-world conditions and achieves a commendable accuracy of 95.83% on the validation dataset.