HYDERABAD EECS THEORY SEMINARS (HyTS)

• Venue: Saranga Hall, Nilgiris Building, 119, IIIT Hyderabad (Directions: After you enter the campus take a right immediately at the main circle. Nilgiris is the last main building at the end of the road)
  

• Time: 9.30am-4.30pm

Gowtham Raghunath Kurri: Fractional Subadditivity of Submodular Functions: Equality Conditions and Their Applications

Abstract: Submodular functions are known to satisfy various forms of fractional subadditivity. In this work, we investigate the conditions for equality to hold exactly or approximately in fractional subadditivity. We establish that a small inequality gap implies that the function is close to being modular, and that the gap is zero if and only if the function is modular. We also present the natural implications of these results for special cases of submodular functions, such as entropy, relative entropy, and matroid rank. As a consequence, we characterize the necessary and sufficient conditions for equality in Shearer's lemma, recovering a result of Ellis et al. (2016) as a special case. We leverage our results to propose a new multivariate mutual information, which generalizes Watanabe's total correlation (1960) and Han's dual total correlation (1975), and analyze its properties. Among these properties, we extend Watanabe's characterization of total correlation as the maximum correlation over partitions to fractional partitions. When applied to matrix determinantal inequalities for positive definite matrices, our results recover the equality conditions of the classical determinantal inequalities of Hadamard, Szasz, and Fischer as special cases. This is a joint work with Gunank Jakhar, Suryajith Chillara, and Vinod Prabhakaran.

Bio: Gowtham R. Kurri received the B.Tech. degree in electronics and communication engineering from the International Institute of Information Technology (IIIT), Hyderabad, India, in 2011, and the M.Sc. and Ph.D. Degrees in computer science from the Tata Institute of Fundamental Research, Mumbai, India, in 2020. From 2011 to 2012, he was an Associate Engineer with Qualcomm India Pvt. Ltd., Hyderabad, India. From July 2019 to October 2019, he was a Research Intern with the Blockchain Technology Group, IBM Research, Bengaluru, India. From 2020 to 2023, he was a Post-Doctoral Researcher with the School of Electrical, Computer and Energy Engineering, Arizona State University. Since February 2023, he has been an Assistant Professor with IIIT Hyderabad, where he is affiliated with the Signal Processing and Communications Research Centre. His research interests include information theory and statistical machine learning. He received the ANRF Prime Minister's Early Career Research Grant in 2025.

Rogers Mathew: Bisection-closed families of set systems

Abstract: A set X bisects a set Y if the cardinality of their intersection is exactly |Y|/2. A family F of subsets of {1,2, … , n} is bisection-closed if for every two distinct sets X, Y in F either X bisects Y or Y bisects X (or both). How large can such a family F be (in terms of n)? We believe that |F| = O(n). In this talk, we present various results towards answering this simple combinatorial question. This talk is based on joint works with Niranjan Balachandran, Srimanta Bhattacharya, Krishn Vishwas Kher, Tapas Kumar Mishra, and Brahadeesh Sankarnarayanan.

Bio: Rogers Mathew is an associate professor in the Department of Computer Science and Engineering, IIT Hyderabad. He works in graphs theory, combinatorics, and graph algorithms.

Lalitha Vadlamani: An Analysis of RPA Decoding of Reed-Muller Codes Over the BSC

Abstract: In this talk, we consider the Recursive Projection-Aggregation (RPA) decoder, of Ye and Abbe (2020), for Reed-Muller (RM) codes. Our main contribution is an explicit upper bound on the probability of incorrect decoding, using the RPA decoder, over a binary symmetric channel (BSC). Importantly, we focus on the events where a single iteration of the RPA decoder, in each recursive call, is sufficient for convergence. Key components of our analysis are explicit estimates of the probability of incorrect decoding of first-order RM codes using a maximum likelihood (ML) decoder, and estimates of the error probabilities during the aggregation phase of the RPA decoder. Our results allow us to show that for RM codes with block length 2^m, the RPA decoder can achieve vanishing error probabilities, in the large block length limit, for RM orders that grow roughly logarithmically in m. This is joint work with V. Arvind Rameshwar.

Bio: V. Lalitha received her B.E. degree in Electronics and Communication Engineering from the Osmania University, Hyderabad, in 2003 and her M.E.and Ph.D. degrees from the Indian Institute of Science (IISc), Bangalore,in 2005 and 2015 respectively. From May 2015, she has been at IIIT Hyderabad, where she is affiliated to Signal Processing and Communications Research Center and she is currently an Associate Professor. Her research interests include coding for distributed storage and computing, quantum error correcting codes, index coding, Reed-Muller codes and polar codes. She is a recipient of Prof. I.S.N. Murthy medal from IISc, 2005 and the TCS Research Scholarship for the year 2011. She (along with her students) is a recipient of Qualcomm Innovation Fellowship for the years 2019 and 2022. She received the runner-up best paper award in National Conference on Communications (NCC) 2019. She is currently serving as the Newsletter Editor of the IEEE Information Theory Society.