Winter 2021 Talks

Tuesday, November 16, 2021

Speaker: Oren Weimann (University of Haifa).

Title: On edit distance oracles and planar distance oracles

Read More

Abstract:

In this talk, I will discuss two highly related problems:

(1) Edit distance oracles: preprocess two strings S and T of total length n into a data structure that can quickly report the optimal edit distance between any substring of S and any substring of T. I will describe a data structure with query time Õ(1), and construction time and space n^(2+o(1)). This is optimal up to subpolynomial factors since computing just the edit distance between S and T requires quadratic time (assuming the strong exponential time hypothesis).

(2) Planar distance oracles: preprocess a directed weighted planar graph into a data structure that can quickly report the distance between any two vertices. Using the concept of Voronoi diagrams, dramatic progress has been made on planar distance oracles in the past few years. I will describe an oracle of almost linear n^{1+o(1)} size that answer queries in Õ(1) time. This is again optimal up to subpolynomial factors. However, the construction time is currently O(n^{1.5}), which is not known to be optimal.

I will describe how ideas developed for planar distance oracles propagate to edit distance oracles. The structure of the edit distance graph allows for a simpler presentation of some of the techniques involved, and is further exploited to obtain a faster construction time.

Based on joint works with Panos Charalampopoulos, Pawel Gawrychowski and Shay Mozes (STOC 2019, ICALP 2021)

Tuesday, November 23, 2021

Speaker: Or Meir (University of Haifa)

Title: Query-to-Communication Lifting Using Low-discrepancy Gadets

Read More

Abstract:

Lifting theorems are theorems that relate the query complexity of a function f:01^n01 to the communication complexity of the composed function fgn, for some “gadget” g:01^b01^b01 . Such theorems allow transferring lower bounds from query complexity to the communication complexity, and have seen numerous applications in the recent years. In addition, such theorems can be viewed as a strong generalization of a direct-sum theorem for the gadget g.

We prove a new lifting theorem that works for all gadgets g that have logarithmic length and exponentially-small discrepancy, for both deterministic and randomized communication complexity. Thus, we significantly increase the range of gadgets for which such lifting theorems hold.

Our result has two main motivations: First, allowing a larger variety of gadgets may support more applications. In particular, our work is the first to prove a randomized lifting theorem for logarithmic-size gadgets, thus improving some applications of the theorem. Second, our result can be seen as a strong generalization of a direct-sum theorem for functions with low discrepancy.

Joint work with Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, and Toniann Pitassi

Tuesday, November 30, 2021.

No seminar

Tuesday, , December 7, 2021.

No seminar

Tuesday, December 14, 2021

Speaker: Ilan Newman (University of Haifa)

Title: TBA

Read More

Absract: TBA

Tuesday, December 21, 2021

Speaker: Elie Abboud (University of Haifa)

Title: TBA

Read More

Absract: TBA

Tuesday, December 28, 2021

Speaker: Anamay Tengse (University of Haifa)

Title: TBA

Read More

Absract: TBA

Tuesday, January 4, 2021.

No seminar