Skip to content. Skip to navigation
CIM Menus

Informal Systems Seminar (ISS), Centre for Intelligent Machines (CIM) and Groupe d'Etudes et de Recherche en Analyse des Decisions (GERAD)

One-Shot Zero Error Network Problems (with and without Solutions)

Natasha Devroye
University of Illinois - Chicago

November 28, 2016 at  11:00 AM
McConnell Engineering Room 437


The zero-error capacity of a noisy communication link — modelled by a set conditional probability mass functions — between one transmitter and one receiver (or point-to-point channel) is the number of transmitter inputs per channel use that may be distinguished at the receiver with no error whatsoever. This is a more stringent condition than the more commonly studied small-error capacity, and results in a combinatorial problem rather than the more easily dealt with probabilistic one. In this talk we examine several zero-error networks (relay, multiple access, interference, broadcast) with more than one transmitter or receiver and present preliminary results on characterizing their zero-error capacity regions. We present more problems than solutions.


Natasha Devroye is an Associate Professor in the Department of Electrical and Computer Engineering at the University of Illinois at Chicago (UIC), which she joined in January 2009. From July 2007 until July 2008 she was a Lecturer at Harvard University. Dr. Devroye obtained her Ph.D in Engineering Sciences from the School of Engineering and Applied Sciences at Harvard University in 2007, and a Honors B. Eng in Electrical Engineering from McGill University in 2001. Dr. Devroye was a recipient of an NSF CAREER award in 2011 and was named UIC's Researcher of the Year in the "Rising Star" category in 2012. She has been an Associate Editor for IEEE Transactions on Wireless Communications, IEEE Journal of Selected Areas in Communications, and is currently an Associate Editor for the IEEE Transactions on Cognitive Communications and Networking. Her research focuses on multi-user information theory and applications to cognitive and software-defined radio, radar, relay, zero-error and two-way communication networks.