Seminar Upcoming

In this talk, I will explain the basics of proof complexity, its connections to NP vs coNP, and SAT solvers lower bounds. One of the frontier proof systems, for which we do not have any lower bounds, is the Res(+) proof system. A recent breakthrough by Efremenko, Garlik, and Itsykson (STOC 2024) established an exponential lower bound for regular Res(+). In our recent work, we proved an exponential lower bound for bounded-depth Res(+).

We will discuss the methods used to prove those lower bounds, such as lifting theorems and Prover-Delayer games.

A history-independent data structure does not reveal the history of operations applied to it, only its current logical state, even if its internal state is examined. While history independence has been extensively studied in sequential data structures, until very recently, it was not studied in a concurrent setting, where the data structure can be accessed by many threads at the same time.

In this talk I will discuss history-independent concurrent dictionaries, in particular, hash tables, and establish inherent bounds on their space requirements. We show that there is a lock-free history-independent concurrent hash table, in which each memory cell stores two elements and two bits, based on Robin Hood hashing. The expected amortized step complexity of the hash table is O(c), where c is an upper bound on the number of concurrent operations that access the same element, assuming the hash table is not overpopulated.

The Lempel-Ziv 77 (LZ77) factorization is a fundamental compression scheme widely used in text processing and data compression. In this work, we investigate the time complexity of maintaining the LZ77 factorization of a dynamic string. By establishing matching upper and lower bounds, we fully characterize the complexity of this problem.

We present an algorithm that efficiently maintains the LZ77 factorization of a string $S$ undergoing edit operations, including character substitutions, insertions, and deletions. Our data structure can be constructed in $tilde{O}(n)$ time for an initial string of length $n$ and supports updates in $tilde{O}(n^{2/3})$ time, where $n$ is the current length of $S$. Additionally, we prove that no algorithm can achieve an update time of $O(n^{2/3-varepsilon})$ unless the Strong Exponential Time Hypothesis fails. This lower bound holds even in the restricted setting where only substitutions are allowed and only the length of the LZ77 factorization is maintained.