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

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).

Welcome and Introductions

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.

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.

Speaker: Yasamin Nazari

Affiliation: JHU

Title: TBA

Abstract: TBA

Speaker: Karthik Abinav Sankararaman

Affiliation: University of Maryland

Title: TBA

Abstract: TBA

Speaker: Jalaj Upadhyay

Affiliation: JHU

Title: TBA

Abstract: TBA

Speaker: Martin Farach-Colton

Affiliation: Rutgers University

Title: TBA

Abstract: TBA