Seminar

We typically have seminars on Wednesday at noon in Malone 228.  All seminar announcements will be sent to the theory mailing list.

Aug
23
Thu
[Theory Seminar] Akash Kumar @ Malone 338
Aug 23 @ 12:00 pm – 1:00 pm

Speaker: Akash Kumar
Affiliation: Purdue University
Location: Malone 338 (note change of location)

Title:
Finding Minors in Sublinear time in Bounded degree graphs with (almost) optimal one-sided query complexity.

Abstract:
Let G be an undirected, bounded degree graph with n vertices. Fix a finite graph H, and suppose one must remove \varepsilon n edges from G to make it H-minor free (for some small constant \varepsilon > 0). We give an n^{1/2+o(1)}-time randomized procedure that, with high probability, finds an H-minor in such a graph. For an example application, suppose one must remove \varepsilon n edges from a bounded degree graph G to make it planar. This result implies an algorithm, with the same running time, that produces a K_{3,3} or K_5 minor in G. No sublinear time bound was known for this problem, prior to this result.

By the graph minor theorem, we get an analogous result for any minor-closed property. Up to n^{o(1)} factors, this resolves a conjecture of Benjamini-Schramm-Shapira (STOC 2008) on the existence of one-sided property testers for minor-closed properties. Furthermore, our algorithm is nearly optimal, by an \Omega(\sqrt{n}) lower bound of Czumaj et al (RSA 2014).

Prior to this work, the only graphs H for which non-trivial property testers were known for H-minor freeness are the following: H being a forest or a cycle (Czumaj et al, RSA 2014), K_{2,k}, (k\times 2)-grid, and the k-circus (Fichtenberger et al, Arxiv 2017).

(Joint work with C. Seshadhri and Andrew Stolman).

Sep
5
Wed
[Theory Seminar] Welcome and Introductions
Sep 5 @ 12:00 pm – 1:00 pm

Welcome and Introductions

Sep
12
Wed
[Theory Seminar] Zhengzhong Jin
Sep 12 @ 12:00 pm – 1:00 pm

Speaker: Zhengzhong Jin
Affiliation: JHU

Title: Deterministic Document Exchange Protocols, and Almost Optimal Binary Codes for Edit Errors

Abstract:
We study two basic problems regarding edit error, i.e. document exchange and error correcting codes for edit errors (insdel codes). For message length n and edit error upper bound k, it is known that in both problems the optimal sketch size or the optimal number of redundant bits is Θ(k log n/k). However, known constructions are far from achieving these bounds.

We significantly improve previous results on both problems. For document exchange, we give an efficient deterministic protocol with sketch size O(k log^2 n/k). This significantly improves the previous best known deterministic protocol, which has sketch size O(k^2+k log^2 n). For binary insdel codes, we obtain the following results:

1. An explicit binary insdel code which encodes an n-bit message x against k errors with redundancy O(k log^2 n/k). In particular this implies an explicit family of binary insdel codes that can correct ε fraction of insertions and deletions with rate 1−O(ε log^2(1/ε))=1−\tilde {O}(ε).

2. An explicit binary insdel code which encodes an n-bit message x against k errors with redundancy O(k log n). This is the first explicit construction of binary insdel codes that has optimal redundancy for a wide range of error parameters k, and this brings our understanding of binary insdel codes much closer to that of standard binary error correcting codes.

In obtaining our results we introduce the notion of ε-self matching hash functions and ε-synchronization hash functions. We believe our techniques can have further applications in the literature.

Oct
3
Wed
[Theory Seminar] Marius Zimand
Oct 3 @ 12:00 pm – 1:00 pm

Speaker: Marius Zimand
Affiliation: Towson University

Title: An operational characterization of mutual information in algorithmic information theory

Abstract: An operational interpretation of the concept of mutual information in the framework of Kolmogorov complexity has been elusive till now. We show that the mutual information of any pair of strings x and y is equal, up to logarithmic precision, to the length of the longest shared secret key that two parties, one having x and the complexity profile of the pair and the other one having y and the complexity profile of the pair, can establish via a probabilistic protocol with interaction on a public channel. We establish the communication complexity of secret key agreement protocols that produce a secret key of maximal length, for protocols with public randomness. We show that if the communication complexity drops below the established threshold then only very short secret keys can be obtained.

This is joint work with Andrei Romashchenko.

Oct
10
Wed
[Theory Seminar] Yasamin Nazari
Oct 10 @ 12:00 pm – 1:00 pm

Speaker: Yasamin Nazari
Affiliation: JHU

Title: TBA

Abstract: TBA

Oct
17
Wed
[Theory Seminar] Karthik Abinav Sankararaman @ Malone 228
Oct 17 @ 12:00 pm – 1:00 pm

Speaker: Karthik Abinav Sankararaman
Affiliation: University of Maryland

Title: TBA

Abstract: TBA

Nov
7
Wed
[Theory Seminar] Jalaj Upadhyay
Nov 7 @ 12:00 pm – 1:00 pm

Speaker: Jalaj Upadhyay
Affiliation: JHU

Title: TBA

Abstract: TBA

Nov
16
Fri
Capital Area Theory Day @ Georgetown University
Nov 16 all-day
Feb
13
Wed
[Theory Seminar] Martin Farach-Colton
Feb 13 @ 12:00 pm – 1:00 pm

Speaker: Martin Farach-Colton
Affiliation: Rutgers University

Title: TBA

Abstract: TBA