Information Theoretic Duets: The IEEE ISIT 2022 Student Competition

The IEEE IT Society Student and Outreach Subcommittee is proud to present the “Information Theoretic Duets Competition”, an online challenge to give students the opportunity to work with a mentor and a teammate, create a five-minute video, win prizes, and gain recognition for their work! Team up for competition, collaborate for life!

Winners

1st Place: Private Set Intersection (Video)

 

2nd Place: On Weight Distribution of Polar Codes (Video)

In private set intersection (PSI), there are two entities, each with a specific set, with the goal of finding the intersection of the two sets without revealing any information beyond the intersection itself. As a practical scenario for the PSI problem, we consider two private sets, the ISIT 2022 participants and the list of people with positive covid tests. In this scenario, the goal is to find the intersection of the two sets privately, which can be used to prevent any possible covid outbreaks at ISIT 2022. In this video, we start with the problem of PSI and its existing solutions that deal with hash functions and homomorphic encryption. Then we introduce the information-theoretic model of the PSI problem along with its connection to multi-message symmetric private information retrieval (MM-SPIR) and describe its capacity-achieving scheme. We provide a detailed explanation on how the capacity-achieving PSI scheme is applied to the practical scenario mentioned above to find the intersection of the two sets privately.

Since its introduction in 2008, polar codes are drawing a lot of research attention from both academic and industry leading to their adoption in 5G-NR. Research towards the weight distribution only led to a fraction of the whole weight distribution. In the paper A Deterministic Algorithm for Computing the Weight Distribution of Polar Codes, authors present a deterministic algorithm for computing the entire weight distribution. The algorithm is based on the representation of any polar code as a disjoint union of polar cosets. The complexity of this algorithm is reduced by proving that a subgroup of the automorphism group of polar codes acts transitively on certain subsets of the codes. This permits to reduce the number of polar cosets to evaluate.

Presenters

Presenters

Sajani Pallegoda Vithana received her B.Sc. degree in electrical and electronic engineering from the University of Peradeniya, Sri Lanka, in 2017. She is currently pursuing the Ph.D. degree with the Department of Electrical and Computer Engineering, University of Maryland, College Park, MD, USA. Her research interests include information theory, privacy, and machine learning.

Amir Masoud Jafarpisheh received the BSc degree in Electrical Engineering from Isfahan University of Technology, Iran, with the first rank in the Electrical and Computer Engineering department in 2019. He got a master of science admission as an exceptional talent from the Sharif University of Technology in 2019. He received his MSc degree with the second rank among students in the Secure Communication and Cryptography specialization in 2021 from the Electrical Engineering department, Sharif University of Technology, Iran. His research interests include information theory, coding for distributed systems, and learning theory.

Malek Ellouze obtained the M.Sc. degree in telecommunications from the engineering school ENSEIRB-MATMECA – Bordeaux INP in 2020. She is currently on her second year of PhD degree with the IMS laboratory and university of Bordeaux, France. Her research mainly revolves around the analysis and optimization of the polar codes decoders.

Charles Pillet received the M.Sc. degree in telecommunications engineering from Enseirb-MATMECA – Bordeaux INP in 2018 and the PhD degree in telecommunications with Huawei Paris research center and the Lab-STICC affiliated with IMT Atlantique (Brest, Brittany) in June 2022. He is currently doing his postdoctoral research in Lacime, ÉTS Montréal under the supervision of Prof. Pascal Giard. His research includes polar coding, low-latency applications and soft decoding algorithms.

3rd Place: Binary Hypothesis Testing with Deterministic Machine (Video)

 

4th Place: Active Learning for Classification with Abstention (Video)

 

In this video, we explain the key result and insight from “Binary Hypothesis Testing with Deterministic Finite-Memory Decision Rules” by Tomer Berg, Or Ordentlich, and Ofer Shayevitz. Given a sequence of independent and identically distributed random variables that may come from Bern(p) or Bern(q), we perform hypothesis testing using a deterministic finite-memory machine. The key result is a converse bound on the error exponent, as a function of the size of the memory, of any deterministic machine. The converse bound demonstrates that the gap between deterministic machine error exponent (derived in this paper) and randomized machine error exponent (derived by Hellman and Cover) can be unbounded. The pivotal insight that leads to this result is since the machine is deterministic, the memory updating rule is only a function of p or q, whereas the memory updating rule for a randomized machine can be made as small or as large as desired.

In this short video, we discuss active learning for binary classification with abstention. In this problem, the task of the learner is to design a binary classifier that has the additional option of abstaining from classifying in case it lacks sufficient confidence in its decision fidelity. Specifically, the setting of fixed abstention cost is considered, and the learner has a fixed budget on the number of queries, with the goal of minimizing the excess risk of the classifier. An upper-confidence-bound based algorithm is proposed for estimating the joint probability density of the input and the labels, which is then used for designing the active binary classifier. The excess error rate of this classifier matches the information-theoretic lower bound. This video is based on the work – “Shubhanshu Shekhar, Mohammad Ghavamzadeh, and Tara Javidi, Active Learning for Classification with Abstention.”

Presenters

Presenters

Yuxin Liu is currently a PhD candidate at the California Institute of Technology (Caltech) under the supervision of Prof. Michelle Effros. He received his B.E. degree from the Australian National University with first class honours in 2017 under the supervision of Prof. Parastoo Sadeghi and his M.S. in electrical engineering from Caltech in 2020. His research interests include information theory, channel coding, and their applications in real world.

Hari Krishnan P A is a second year PhD student at Tata Institute of Fundamental Research, Mumbai, advised by Prof. Vinod Prabhakaran. His research interests lie in information theoretic cryptography.

Rajarshi Saha is a third-year Ph.D. student in Electrical Engineering at Stanford University. He is co-advised by Mert Pilanci and Andrea Goldsmith. His research interests broadly lie in identifying and addressing problems related to distributed optimization over resource-constrained edge devices. He enjoys understanding problems in this domain from a theoretical perspective, investigating notions of optimality, and designing theoretically-backed practical algorithms.
Prior to joining Stanford, he completed his Bachelors’ and Masters’ from Indian Institute of Technology (IIT) Kharagpur, with a major in Electronics and Electrical Communications Engineering, a minor in Computer Science, and a micro-specialization in Embedded Wireless Systems. During his time there, he worked on topics of MIMO Radar Imaging which received the Best Undergraduate Thesis Award. He was also the recipient of the Prime Minister of India Gold Medal for being the class valedictorian.

Arpan Mukherjee is a third-year PhD student in the Department of Electrical, Computer and Systems Engineering at Rensselaer Polytechnic Institute (RPI). Arpan works with the Information Sciences Group, where I am fortunate to be supervised by Dr. Ali Tajer. His research lies in the domain of sequential design of experiments. Specifically, he investigates problems related to multi-armed bandits and controlled sensing. He is also interested in communication-efficient federated learning. At RPI, he was the recipient of the B. Jayant Baliga Fellowship in the year 2019. Prior to joining RPI, he obtained his M. Tech degree at the Indian Institute of Technology (IIT) Kharagpur, where he specialized in telecommunication systems. His research was focused on designing sparse adaptive filtering algorithms.

As a student participant in the competition, you will

  • Be a part of a team formed by two students, each from a different university. You are free to choose your teammate, or you can request the Student and Outreach Subcommittee to pair you up with another participant. You and your teammate will collaborate in preparing a five-minute video focusing on a research paper.
  • Interact with a mentor to prepare a video describing ideas in one of their research papers. You can choose your mentor from a list of volunteers who were finalists for past years’ Jack K. Wolf Best Paper awards (ISIT best student paper award), and create a video about their nominated paper or choose one of their papers and contact the mentor together with your teammate directly. Mentors have kindly agreed to be available for an online meeting with each team during the competition to provide advice to the participating students.
  • Collaborate on making and uploading a short video with your conversation explaining these ideas to the ISIT audience. The video should not be more than five minutes long. It should be uploaded to this link no later than Tuesday, June 21
  • Win prizes! Four videos will be selected by a jury composed of three members of the Student and Outreach Subcommittee. Each winning team will receive a $400 USD prize! The videos will be scored based on creativity, clarity, and evidence of collaboration.
  • Get visibility within the IT community. The four winning videos will be uploaded to the IEEE IT Society YouTube Channel and the winners will be recognized during ISIT 2022. Take a look at the three winning videos of the ISIT 2021 student online challenge (Video 1, Video 2, Video 3).

Participating students should be Student Members of IT Society at the time of registration, and should register no later than Saturday, May 28, by filling the form at this link. The teams will be announced by Tuesday, May 31.

Organized by the IEEE IT Society Student and Outreach Subcommittee (Farhad Shirani, Onur Günlü, Navid NaderiAlizadeh, Siyao Li, Neha Sangwan, I-Hsiang Wang)