Mohammad Saneian

Amir Azarmehr, Soheil Behnezhad, Shane Ferrante et al.

We study streaming algorithms for the maximum directed cut problem. The edges of an $n$-vertex directed graph arrive one by one in an arbitrary order, and the goal is to estimate the value of the maximum directed cut using a single pass and small space. With $O(n)$ space, a $(1-\varepsilon)$-approximation can be trivially obtained for any fixed $\varepsilon > 0$ using additive cut sparsifiers. The question that has attracted significant attention in the literature is the best approximation achievable by algorithms that use truly sublinear (i.e., $n^{1-Ω(1)}$) space. A lower bound of Kapralov and Krachun (STOC'19) implies .5-approximation is the best one can hope for. The current best algorithm for general graphs obtains a .485-approximation due to the work of Saxena, Singer, Sudan, and Velusamy (FOCS'23). The same authors later obtained a $(1/2-\varepsilon)$-approximation, assuming that the graph is constant-degree (SODA'25). In this paper, we show that for any $\varepsilon > 0$, a $(1/2-\varepsilon)$-approximation of maximum dicut value can be obtained with $n^{1-Ω_\varepsilon(1)}$ space in *general graphs*. This shows that the lower bound of Kapralov and Krachun is generally tight, settling the approximation complexity of this fundamental problem. The key to our result is a careful analysis of how correlation propagates among high- and low-degree vertices, when simulating a suitable local algorithm.

Saeed Saadatnejad, Mohammadhossein Bahari, Pedram Khorsandi et al.

Our field has recently witnessed an arms race of neural network-based trajectory predictors. While these predictors are at the core of many applications such as autonomous navigation or pedestrian flow simulations, their adversarial robustness has not been carefully studied. In this paper, we introduce a socially-attended attack to assess the social understanding of prediction models in terms of collision avoidance. An attack is a small yet carefully-crafted perturbations to fail predictors. Technically, we define collision as a failure mode of the output, and propose hard- and soft-attention mechanisms to guide our attack. Thanks to our attack, we shed light on the limitations of the current models in terms of their social understanding. We demonstrate the strengths of our method on the recent trajectory prediction models. Finally, we show that our attack can be employed to increase the social understanding of state-of-the-art models. The code is available online: https://s-attack.github.io/