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.

Venue: EE-004 (Ground floor, EECS building), IITH
Time: 3.30-4.30pm (tentative) on 19th February, 2025

Title: On how to try to beat the Gilbert-Varshamov bound

Abstract: The classic Gilbert-Varshamov (GV) bound from the 1950's gives us packings of q-ary Hamming balls in \(q\)-ary Hamming space, with a rate of \(1-H_q(\delta)\) for all \(q < 49\) this is essentially the densest known. In this informal blackboard talk I'll outline a deep rabbit-hole I've gone down the last few months, trying to beat this bound. I'll show a (to my knowledge) heretofore unanalysed class of random codes that achieve the GV bound for a wide range of parameters, and then show that if even one of a certain class of information inequalities holds then these codes can be refined to beat the GV bound. This is work in progress, and is an invitation for folks to come with me further down the rabbit-hole.


Bio: Sidharth (Sid) Jaggi (B.Tech. IIT Bombay 2000, M.S./Ph.D. CalTech 2006, all in electrical engineering, post-doctoral associate MIT 2006): He joined The Chinese University of Hong Kong in 2007, and the School of Mathematics at the University of Bristol in 2020, where he is currently a Professor of Information and Coding Theory. His research group (somewhat unwillingly) calls itself the CAN-DO-IT Team (Codes, Algorithms, Networks: Design and Optimization for Information Theory). Topics he has worked in include sparse recovery/group-testing, covert communication, network coding, and adversarial channels.

Venue: A-112, IITH
Time: 12-1pm on 25th November, 2024

Title: On some recent results for signal reconstruction from “non-uniformly encoded” sampling

Abstract: The classic problem of non-uniform sampling of data has a rich history, yet continues to be of interest to many given its application in devising efficient event-triggered mechanisms for asynchronous or distributed communication/control, and low-power analog-to-digital (ADC) converters. In this talk, I will first focus on “time-encoded sampling,” which represents an interesting paradigm for temporal discretization and has garnered recent interest. Using the theory of irregular sampling over general function spaces, I will first present a sufficient condition for achieving perfect recovery over generalized shift-invariant spaces (SISs), of which the bandpass (and bandlimited) signal space is a well known instance, as well as an appropriate (iterative) interpolation scheme. Our work builds upon and extends prior work, especially that of Gontier-Vetterli ’13 on such time-encoded machines (TEMs). We present illustrative results for some classical signal spaces highlighting both the value, as well as limitations of single-TEM-based time-encoding schemes. Using key ideas from this work, I will also seek to present some ongoing work and (possibly interesting) directions of related inquiry.
This is joint work with Roshaan Soundarapandian (formerly at IIT Kharagpur and now at Qualcomm Inc.), and Stefano Rini (NYCU Taiwan).

Bio: V. Amitalok J. Budkuley is an assistant professor in the Dept. of Electronics and Electrical Communication Engineering (E&ECE) at the Indian Institute of Technology Kharagpur. He received his B. Engg. degree in Electronics and Telecommunications Engineering from Goa University, in 2007, and his M. Tech. and Ph. D. degree in Electrical Engineering from the Indian Institute of Technology Bombay, Mumbai, India in 2009 and 2017 respectively. In between, he spent some time in industry working with Cisco Systems Inc.. From 2016 to 2019, he was at the Dept. of Information Engineering, The Chinese University of Hong Kong (CUHK) as a research assistant and then as a post-doctoral fellow.
His research interests include signal processing for distributed communication and control, communication theory, cryptography and security.

Venue: A-LH1, IITH
Time: 12-1pm on 13th November, 2024

Title: Joint Estimation of Frequency and Phasor of Three-Phase Signals

Abstract: Accurate estimation of frequency and phasor of voltage and current signals is essential for effective monitoring of modern power grids. This talk explores the challenges involved in estimating the frequency and phasor of typical signals and discusses the key performance and estimation requirements. Subsequently, this talk will outline some of the philosophies adopted in the literature for phasor and frequency estimation and highlight their respective challenges/shortcomings. Finally, this talk will introduce a simple and computationally efficient algorithm for joint estimation of frequency and phasor of three-phase signals.

Bio: V. Seshadri Sravan Kumar is a faculty member in the Department of Electrical Engineering at IIT Hyderabad. His research interests lie in the areas of Power Systems and Applied Mathematics.

Venue: A-221, IITH
Time: 12-1pm on 18th October, 2024

Title: An Information-theoretic look at storing data on shotgun-sequenced DNA

Abstract: In shotgun sequencing, the input string (typically, a long DNA sequence composed of nucleotide bases) is sequenced as multiple overlapping fragments of much shorter lengths (called reads). Modelling the shotgun sequencing pipeline as a communication channel for DNA data storage, the capacity of this channel was identified in a recent work, assuming that the reads themselves are noiseless substrings of the original sequence. Modern shotgun sequencers however also output quality scores for each base read, indicating the confidence in its identification. Bases with low quality scores can be considered to be erased. Motivated by this, we consider the shotgun sequencing channel with erasures, where each symbol in any read can be independently erased with some probability. We identify achievable rates for this channel, using a random code construction and a decoder that is inspired by typicality arguments in information theory.

Bio: Prasad Krishnan received the B.E. degree from the College of Engineering at Guindy, Anna University, in 2007, and the Ph.D. degree from the Department of Electrical Communication Engineering, Indian Institute of Science, Bangalore, in 2014. Since 2014, he has been with the Signal Processing and Communications Research Centre, International Institute of Information Technology Hyderabad (IIIT Hyderabad) as a faculty member. His current research interests are in Algebraic Coding Theory, Private Information Retrieval, and Codes for DNA data storage.

Venue:

• 9.30am-12.45pm: C-LH6, IITH

• 1pm-5pm : LH12, Lecture Hall Complex, IITH

Shashank Vatedka: Sphere Packings and List Decoding in Euclidean Space

Abstract: What is the maximum number of non-overlapping \(n\)-dimensional spheres that you can pack in a given volume? This is the classical sphere-packing problem for which the solution is unknown except for some special cases. In this talk, I will discuss a generalization of this called the \(L\)-packing problem, wherein we allow at most \(L\) spheres to intersect. When \(L=1\), this reduces to the classical sphere packing problem. I will discuss connections to communications, coding theory, and some bounds on the maximum achievable rate, density of \(L\)-packings when \(n\) is large. Parts of this talk are based on joint work with Yihan Zhang (IST Austria).

Bio: Shashank Vatedka received his MSc (Engg) and PhD from the Indian Institute of Science Bengaluru. After postdoctoral stints at the Institute of Network Coding (The Chinese University of Hong Kong), and Telecom Paris, he joined the Indian Institute of Technology Hyderabad where he is currently an Assistant Professor. His research interests are Information Theory and Coding, with applications to Statistical Inference, Data Compression and Security.

Myna Vajha: Two way generalization of a burst erasure correcting code

Abstract: In this talk, we will present two generalizations of a binary code introduced by Hollmann and Tolhuizen (HT) that can correct any burst erasure including a wrap-around burst. The HT code is constructed by recursively concatenating identity matrices of appropriate sizes, either column-wise or row-wise, depending on the parameters. HT codes were initially introduced in the context of constructing streaming codes capable of recovering from a burst of size \(b\) within a delay constraint of \(\tau\). The first generalization of HT code allows us to construct a streaming code that can recover from either a random erasure of size \(a\) or a burst erasure of size \(b\) within a delay constraint of \(\tau\). The second generalization of the HT code is relevant in the context of a three-node relay setting, where both links experience at most one burst erasure of size \(b\). Burst erasure in the source-relay link can lead to message symbols being transmitted out of order at the relay. This is joint work with Vinayak Ramkumar, Nikhil Krishnan, P. Vijay Kumar.

Bio: Myna Vajha is an Assistant Professor at the EE department, IIT Hyderabad. She received BTech. (2011) and M.Tech. (2013) degrees from IIT Kharagpur and University of Southern California respectively, and the Ph.D. degree from IISc Bangalore in 2020. Post PhD, Myna worked on physical layer algorithms for WiFi at Qualcomm Wireless R&D, Bangalore. Her current research interests are in the areas of coding and information theory and systems design of communication systems.

Lakshmi Prasad Natarajan: Title: Recursive Subproduct Codes (and Berman Codes)

Abstract: We introduce a family of binary linear codes identified as subcodes of m-dimensional product codes which includes RM codes as a special case. This family also includes the dual of a class of codes introduced by Berman in 1967. Recursive subproduct codes provide a wider range of block lengths compared to RM codes while sharing several of its structural properties. The special case of dual Berman codes achieves the capacity of the binary erasure channel (in the sense of vanishing bit error rate).

Bio: Lakshmi Prasad Natarajan received the B.E. degree in electronics and communication from the College of Engineering, Guindy, in 2008, and the Ph.D. degree from the Indian Institute of Science, Bengaluru, in 2013. From 2014 to 2016, he held a post-doctoral position at the Department of Electrical and Computer Systems Engineering, Monash University, Australia. He is a Faculty Member with the Department of Electrical Engineering, Indian Institute of Technology Hyderabad. His primary research interests include coding techniques and information theory for communication systems.

Mrinmoy Datta:On the second and third weights of Projective Reed-Muller Codes

Abstract: It is well-known that the determination of Hamming weights of codewords belonging to the projective Reed-Muller codes PRM(d, m) are equivalent to the determination of the number of \(F_q\)-rational points on a given projective hypersurface of degree \(d\) and dimension \(m-1\). The highest number of such points on hypersurface, and consequently, the minimum weight of PRM (d, m) is known, thanks to Serre. In this talk, we will explore the question of determining the second and third minimum weights of the Projective Reed-Muller codes. We will revisit several results due to Sboui, Rodier, and Geil, among others, to this end. Finally, we will present some recent results concerning these problems.

Bio: Mrinmoy Datta is currently an Assistant Professor at the Department of Mathematics at IIT Hyderabad. He obtained his Masters degree from ISI Banglore and PhD from IIT Bombay. He held post-doctorial positions at Technical University of Denmark (DTU), and at UiT Norges Arktiske Universitet. He works in the area of Algebraic Geometry over Finite Fields with applications to Linear Error-Correcting Codes.

Alexander Barg: Smoothing of codes, uniform distributions, and applications

Abstract: The action of a noise operator on a binary code transforms it into a distribution on the Hamming space . We aim to characterize the cases when the output distribution is close to the uniform distribution on the space, as measured by Renyi divergence of order alpha>1. A version of this question is known as the channel resolvability problem in information theory, and it has implications for security guarantees in wiretap channels, error correction, discrepancy, and other problems. In the first part of the talk, we derive expressions for the minimum rate of codes required to attain asymptotically perfect smoothing and give achievability results for the rate of Reed-Muller codes used on the wiretap channel. In the second part we consider a related problem of linear hashing, proving estimates for the expected p-divergence from the uniform distribution over the ensemble of random linear codes. In the third part we prove some impossibility results for the worst-to-average case reduction in the problem of Learning Parity with Noise using code smoothing. The talk is based on joint works with Madhura Pathegama.

Bio: Alexander Barg (Fellow, IEEE) is currently a Professor with the Department of Electrical and Computer Engineering and the Institute for Systems Research (ISR), University of Maryland, College Park, MD, USA. His research interests include information and coding theory, applied probability, and algebraic combinatorics. He received the 2015 Information Theory Society Paper Award. He was a Plenary Speaker at the 2016 IEEE International Symposium on Information Theory, Barcelona, Spain. From 2018 to 2019, he served as the Editor-in-Chief for this IEEE Transactions. He is currently the Editor-in-Chief of Foundations and Trends in Communications and Information Theory. He is honoured with the 2024 IEEE Richard Hamming medal.