Orr Fischer

Dmitrii Avdiukhin, Grigory Yaroslavtsev, Danny Vainstein et al.

We study the problem of learning a hierarchical tree representation of data from labeled samples, taken from an arbitrary (and possibly adversarial) distribution. Consider a collection of data tuples labeled according to their hierarchical structure. The smallest number of such tuples required in order to be able to accurately label subsequent tuples is of interest for data collection in machine learning. We present optimal sample complexity bounds for this problem in several learning settings, including (agnostic) PAC learning and online learning. Our results are based on tight bounds of the Natarajan and Littlestone dimensions of the associated problem. The corresponding tree classifiers can be constructed efficiently in near-linear time.

Orr Fischer, Ran Gelles

We study the Task Completion problem, in which $M$ abstract tasks must be completed by a network of $n$ crash-prone nodes, where up to $αn$ nodes may crash for some constant $α<1$. Our main result is a deterministic congested-clique algorithm that completes all $M$ tasks in $O(\lceil M/n\rceil \log n)$ rounds. This round complexity is optimal up to $\log\log n$ terms. The key technical ingredient underlying our algorithm is a novel combinatorial structure, which we call a \emph{load balancing covering family}. In essence, this covering family induces, for each task, a subset of nodes responsible for attempting to complete it. The properties of the load balancing covering family guarantee that, regardless of which tasks remain incomplete and which nodes crash, (i) no node is overloaded with incomplete tasks, and (ii) no task is left with too few potential assigned nodes. This yields a balanced per-node workload and prevents non-crashed nodes from being concentrated on a small subset of tasks, thereby ensuring sufficient progress in completing the remaining tasks. As an application of our task completion method, we give a deterministic algorithm for simulating any $T$-round congested-clique algorithm in the presence of up to $αn$ crash faults in $O(T^2 \log n + T \log^2 n)$ rounds. This improves upon a recent result by Censor-Hillel et al. (DISC~2025), which requires $T^2\cdot 2^{O(\sqrt{\log n}\log\log n)}$ rounds.

Arnold Filtser, Orr Fischer

In the $t$-Proof Labeling Scheme model ($t$-PLS model), our goal is to certify that a network of nodes satisfies a given property $P$. A prover assigns a label to each node, and each node decides to accept or reject based on its labeled $t$-hop neighborhood. If $P$ holds, there exists a labeling that makes all nodes accept. If $P$ does not hold, in all labelings at least one node rejects. The cost of a scheme is its maximum label size. The Tradeoff Conjecture [Feuilloley, Fraigniaud, Hirvonen, Paz, and Perry, DISC 18, Dist. Comput.~21] hypothesizes that the existence of a $1$-PLS for a property $P$ with cost $p$ implies the existence of a $t$-PLS for $P$ with cost $O(\lceil p/t \rceil)$. The conjecture was initially shown to hold for specific graph classes, such as trees, cycles, and grids. Later, a weaker $\widetilde{O}(\lceil Δp/\sqrt{t} \rceil)$ cost was shown for fixed minor-free graphs, where $Δ$ is the maximum degree. In this work we resolve the Tradeoff Conjecture, up to a single logarithmic factor. In general graphs, we show that the existence of a $1$-PLS with cost $p$ implies the existence of an $O(t\log{n})$-PLS with cost $O(\lceil p/t \rceil)$ for the same property. For fixed minor-free graphs (which include e.g. planar graphs), we show that the existence of a $1$-PLS with cost $p$ implies the existence of a $t$-PLS with cost $O(\lceil p/t \rceil+\log{n})$ for the same property. We also refute a previously suggested stronger variant of the Tradeoff Conjecture, and show that having very large $t$-hop neighborhoods is an insufficient condition for obtaining a tradeoff better than $O(\lceil p/t \rceil)$.

Gilad Yehudai, Clayton Sanford, Maya Bechler-Speicher et al.

Transformers have revolutionized the field of machine learning. In particular, they can be used to solve complex algorithmic problems, including graph-based tasks. In such algorithmic tasks a key question is what is the minimal size of a transformer that can implement a task. Recent work has begun to explore this problem for graph-based tasks, showing that for sub-linear embedding dimension (i.e., model width) logarithmic depth suffices. However, an open question, which we address here, is what happens if width is allowed to grow linearly. Here we analyze this setting, and provide the surprising result that with linear width, constant depth suffices for solving a host of graph-based problems. This suggests that a moderate increase in width can allow much shallower models, which are advantageous in terms of inference time. For other problems, we show that quadratic width is required. Our results demonstrate the complex and intriguing landscape of transformer implementations of graph-based algorithms. We support our theoretical results with empirical evaluations.