Events at Towson University

Sabbatical Talk: Dr. Marius Zimand

Sabbatical Talk: Dr. Marius Zimand

During my sabbatical leave (Spring 2021), I have studied several questions on channel coding, the design of non-blocking networks, dynamic matching in bipartite graphs, and one-probe storage schemes.  I will present some results from the last two items in the list.

Dynamic matching: A bipartite graph has matching up to K elements if for every set S of K left nodes, we can assign to each element in S one of its neighbors so that the assigned neighbors are pairwise different. The classical Hall Marriage Theorem characterizes graphs that have bipartite graphs.  I will present results for the case of online matching in which the elements of S arrive one at a time and the matching has to be done on the fly, and for the case of dynamic matching in which the elements of S not only arrive but can also depart releasing their matches.

 

One-probe storage schemes: The goal is to store a subset S of a large set U (the ``universe"). Let N denote the size of U, and K denote the size of S. A simple storage scheme is to keep in a table a sorted listof the K elements of S. The table is stored on K log N bits, and, for x in U, one can determine if x is in S or not, by reading log K · log N bits from the table. An alternative is to have a table of N bits indexed by the elements in U and to set a bit to 1 if and only if its index is in S. Now the query ``Is x in S?" can be answered by reading a single bit. The cost is that the table is long (taking into account that typically N >> K). I will present a solution which is the ``best of both worlds: " only 1 bit of the data structure is probed, and the table is short, namely has size K exp ( (\log \log N)^2)

Friday, April 1, 2022 at 10:30am to 11:00am

7800 York Road, YR 459
7800 York Rd, Towson University, Towson, MD 21204, USA

Departments

Academic Affairs, Computer & Information Sciences (Department of)

Subscribe
Google Calendar iCal Outlook

Recent Activity