Upcoming meetings

Date: December 31, 2025
Time: 14:15-15:15
Place: 58.3.35
Zoom link  

Speaker: Shay Golan (AU)

Title: The Complexity of Dynamic LZ77 is Θ~(n^{2/3})

Abstract: he 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.

Joint work with Itai Boneh and Matan Kraus, to appear in SODA 2026.

past meetings

December 24, 2025

Speaker: Anat Paskin-Cherniavsky (AU)

Title: New notions and results in evolving primitives

Abstract: During my פטמ"ה  year I have worked on several research projects, both ongoing and newly initiated, which I will briefly mention during the talk. Most of the talk will focus on a project that explores broader share complexity notions of so called evolving secret sharing schemes. This is joint work with Laszlo Csirmaz and Tamar Ben David. In a nutshell, in evolving secret sharing, the set of parties {p_1,p_2,p_3,...} is infinite, and the access structure is finitary in the sense that minimal qualified sets are finite. Share complexity in this area is typically measured as a function sc(i) of a party's (arbitrary) index. To better understand the "inherent" share complexity of a finitary access structure, we generalize this notion to consider "best" and "worst" orderings, and obtain several new upper and lower bounds for natural access structure classes.

December 17, 2025

Speaker: Gabriel Nivasch (AU)

Title: On the complexity of the free space of a translating box in R^3

Abstract: Consider a polyhedral robot B that can translate (without rotating) amidst polyhedral obstacles in R^3. It is known that, if B is either a box or a "flat" convex polygon, then complexity of the free space of B is at most O(n^2 alpha(n)), where n is the total number of vertices of the obstacles, and alpha is the inverse Ackermann function (Halperin and Yap, 1993). In this talk we will prove that if B is either a box or a convex polygon whose edges come in parallel pairs, then the complexity of the free space is O(n^2).

December 3, 2025

Speaker: David Garber (HIT)

Title: On saturated (maximal-for-inclusion) triangulation-free convex geometric graphs

Abstract: A convex geometric graph is a graph whose vertices are the corners of a convex polygon P in the plane and whose edges are boundary edges and diagonals of the polygon. Such a graph is called triangulation-free if its non-boundary edges do not contain the set of diagonals of some triangulation of P. Aichholzer et al. (2010) showed that the maximum number of edges in a triangulation-free convex geometric graph on n vertices is ${{n}\choose{2}}-(n-2)$. Keller and Stein (2020) (and independently Ali et al. (2022)) characterized the triangulation-free graphs with this maximum number of edges.

We initiate the study of the saturation version of the problem, namely, characterizing the triangulation-free convex geometric graphs, which are not of the maximum possible size, but yet the addition of any edge to them results in containing a triangulation, i.e. they are maximal with respect to inclusion.

We show that, surprisingly, there exist saturated (maximal-for-inclusion) graphs with only g(n)=O(n log (n)) edges. Furthermore, we prove that for any $n>n_0$ and any $g(n) \leq t \leq {{n}\choose{2}}-(n-2)$, there exists a saturated graph with n vertices and t edges. In addition, we obtain a complete characterization of all saturated graphs whose number of edges is ${{n}\choose{2}}-(n-1)$, which is 1 less than the maximum.

In settings that the extremal size is close to ${{n}\choose{2}}$, it is more convenient to pass to the complement graph and to consider blockers, which are sets of edges which intersect each triangulation. Clearly, the minimal size of a blocker for triangulation is n-2. A blocker is called saturated (or minimal-for-inclusion) if the deletion of any of its edges will transform it into a non-blocker, and it is easy to see that a blocker is saturated if and only if its complement is a saturated triangulation-free graph. 

In the talk, we use the simpler language of blockers, and we present our two main results, and a sketch of their proofs: 

1. The possible sizes of minimal-for-inclusion blockers.

2. The complete characterization of minimal-for-inclusion blockers of size n-1.

Joint work with Chaya Keller (Ariel), Olga Nissenbaum (Ariel) and Shimon Aviram (HIT).

November 19, 2025

Speaker: Erel Segal-Halevi (AU)

Title: It's Not All Black and White: Degree of Truthfulness for Risk-Avoiding Agents

Abstract: When the inputs to an algorithm are supplied by people, and these people have different preferences regarding the possible outputs of the algorithm, they might try to manipulate the algorithm by reporting untrue inputs. An algorithm is called truthful if reporting the true input is the optimal strategy for each participant. Second-price auction is the classic example of a truthful algorithm. However, in many settings a truthful algorithm does not exist. 

This work presents a relaxation of truthfulness. It assumes that people would try to manipulate the algorithm only if this manipulation is safe, that is, there is no situation in which the manipulation makes the outcome worse for them. Usually, finding a safe manipulation requires information on the strategies of some or all other participants. We define the RAT-degree of an algorithm as the number of other participants that an agent must spy on, in order to have a safe manipulation. This allows us to rate various algorithms according to how close they are to the ideal of truthfulness. We analyze the RAT-degree of prominent mechanisms from five different domains: auctions, fair cake cutting, fair item allocation, voting, and stable matching.

May 7, 2025

Speaker: Edward A. Hirsch (AU)

Title: Upper and Lower Bounds for the Linear Ordering Principle

Abstract: I am going to talk about our recent paper where we resolved two open problems concerning symmetric classes of the polynomial-time hierarchy (I talked about one of these problems a bit at our theory seminar last year, but the present talk is absolutely independent of that). 

Korten and Pitassi (FOCS, 2024) defined a new complexity class L_2 as the polynomial-time Turing closure of the Linear Ordering Principle. They asked whether a Karp-Lipton-style collapse can be proven for L_2.  We are proving a lower and an upper bound for this class thus placing L_2 in a narrow niche between two known classes (polynomial-time computations with an oracle for a promise problem decided by Merlin-Arthur protocols and by small-bounded-probability computations, respectively) thus answering both this question and an earlier open question by Chakaravarthy and Roy (Computational Complexity, 2011).

The talk should be accessible to everyone who is familiar with P and NP -- all other definitions will be given / reminded.

I will also talk about additional questions that are surprisingly open.

(This is a joint work with Ilya Volkovich.) 

November 20, 2024 

Speaker: Aryeh Kontorovich (BGU)

Title: Local Glivenko-Cantelli (or: estimating the mean in infinite dimensions)

Abstract: If μ is a distribution over the d-dimensional Boolean cube {0,1}ᵈ, our goal is to estimate its mean p∈[0,1]ᵈ based on n iid draws from μ. Specifically, we consider the empirical mean estimator p̂ₙ and study the maximal deviation M=max_j∈[d]| p̂ₙ(j)-p(j)|. In the classical Universal Glivenko-Cantelli setting, we seek distribution-free (i.e., independent of μ) bounds on M. This regime is well-understood: for all μ, we have 𝔼[M]≲√log(d)/n up to universal constants, and the bound is tight.
Our present work seeks to establish dimension-free (i.e., without an explicit dependence on d) estimates on M, including those that hold for d=∞. As such bounds must necessarily depend on μ, we refer to this regime as Local Glivenko-Cantelli, and are aware of very few previous bounds of this type — which are quite sub-optimal. Already the special case of product measures μ is quite non-trivial. We give necessary and sufficient conditions on μ for 𝔼[M]→0, and discover a novel sub-Gamma-type maximal inequality for shifted Bernoullis.
A number of challenging open problems are posed for future research. Joint work with Doron Cohen and Roi Weiss, presented at COLT 2023 and COLT 2024.

June 19, 2024 

Speaker: Edward A. Hirsch (AU)

Title: A survey of recent advances in lower bounds for symmetric complexity classes

Abstract: While we are still unable to prove P \neq NP, one can ask whether we can prove that a certain NP language has no size-n^k Boolean circuits. Or, at least, for which class C instead of NP can we prove it?

I will remind the classical results and then move towards explaining the implications of a recent sequence of papers Korten-Chen-Hirahara-Ren-Li-Gajulapalli-Volkovich-Pitassi that improved the classical results down to small symmetric classes including a new class based on the Linear Ordering Problem.

The talk should be accessible to everyone who is familiar with P, NP, and the Cook-Levin NP-completeness theorem. I will remind everything else.

June 5, 2024 

Speaker: Gabriel Nivasch (AU)

Title: Feeding a random permutation to a maximum-stack

Abstract: I will present a problem in probability I encountered in my research many years ago. The problem is still open as far as I know. Perhaps someone in the audience will manage to make progress on it.

May 28, 2024 

Speaker: Elad Aigner-Horev (AU)

Title: Tensorisation through tail probabilities

Abstract: More times than not, Analysis of High-Dimensional Data summons for us encounters with high-dimensional distributions formed as an amalgamation of rudimentary univariate ones. Thus compelling us to wonder to what extent does the multivariate distribution inherits, so to speak, various properties exhibited by its univariate parts.

In my part of the world, tensorisation focuses on the inheritance of anti-concentration properties (though the term is also used in broader contexts with the same spirit in mind). Due to a problem with which Michael Trushkin is working on, I have been summoned, in the last day or so, to an encounter with this property. It seems like I have an argument which for now has me believing that it is perhaps more flexible than other arguments I have seen for this property by, say, Rudelson and Vershynin and some others.

I aim at a “work” talk on the board.

If time permits, then Daniel Rosenberg (student of Roi and mine) will show us a decoupling argument for random Gaussian polynomials following a paper by Shachar Lovett.

May 8, 2024 

Speaker: Chaya Keller (AU)

Title: New Bounds for Zarankiewicz's Problem via $\epsilon$-t-Nets

Abstract: The classical Zarankiewicz's problem asks for the maximum number of edges in a bipartite graph on $n$ vertices which does not contain the complete bipartite graph $K_{t,t}$. In one of the cornerstones of extremal graph theory, K{\H o}vari, S{\'o}s and Tur{\'a}n proved an upper bound of $O(n^{2-\frac{1}{t}})$. In a celebrated result, Fox, Pach, Sheffer, Suk and Zahl obtained an improved bound of $O(n^{2-\frac{1}{d}})$ for graphs of VC-dimension $d$ (where $d<t$). Recently, Chan and Har-Peled presented (quasi-)linear upper bounds for several classes of geometrically-defined incidence graphs, including a bound of $O(n \log \log n)$ for the incidence graph of points and pseudo-discs in the plane.

In this talk we present a new approach to Zarankiewicz's problem, via $\epsilon$-t-nets -- a recently introduced generalization of the classical notion of $\epsilon$-nets. We show that the existence of `small'-sized $\epsilon$-t-nets implies upper bounds for Zarankiewicz's problem. Using the new approach, we obtain a new proof of the $O(n^{2-\frac{1}{d}})$ bound of Fox et al., and a sharp bound of $O(n)$ for the intersection graph of two families of pseudo-discs, thus both improving and generalizing the result of Chan and Har-Peled from incidence graphs to intersection graphs.

We also obtain improved bounds for several other classes of geometric intersection graphs, including a sharp $O(n\frac{\log n}{\log \log n})$ bound for the intersection graph of two families of axis-parallel rectangles. 

Joint work with Shakhar Smorodinsky.

February 21, 2024 

Speaker: Erel Segal-Halevi (AU)

Title: Computing Approximate Roots of Monotone Functions

Abstract: Given a function f: [a,b] -> R, if f(a) < 0 and f(b) > 0 and f is continuous, the Intermediate Value Theorem implies that f has a root in [a,b]. Moreover, given a value-oracle for f, an approximate root of f can be computed using the bisection method, and the number of required evaluations is polynomial in the number of accuracy digits.

The goal of this note is to identify conditions under which this polynomiality result extends to a multi-dimensional function that satisfies the conditions of Miranda's theorem --- the natural multi-dimensional extension of the Intermediate Value Theorem.

In general, finding an approximate root might require an exponential number of evaluations even for a two-dimensional function. We show that, if f is two-dimensional and satisfies a single monotonicity condition, then the number of required evaluations is polynomial in the accuracy.

For any fixed dimension d, if f is a d-dimensional function that satisfies all d^2-d ``ex-diagonal'' monotonicity conditions (that is, component i of f is monotonically decreasing with respect to variable j for all i != j), then the number of required evaluations is polynomial in the accuracy.

But if f satisfies only d^2-d-2 ex-diagonal conditions, then the number of required evaluations may be exponential in the accuracy.

As an example application, we show that computing approximate roots of monotone functions can be used for approximate envy-free cake-cutting.

Joint work with: Alexandros Hollender, Chester Lawrence.

January 17, 2024 

Speaker: Aryeh Kontorovich (BGU)

Title: Estimating the distribution in various norms

Abstract: We consider the problem of estimating a discrete distribution in various natural norms that also come up in common applications: ℓ₁, ℓ₂, ℓ∞. We will discuss the distinct behaviors of all of these estimates and their minimax risk rates, as well as the best-case and worst-case distributions for estimation in each of the norms.

Some applications will be presented.

Joint work with Amichai Painsky.