Arrow Research search

Author name cluster

Amit LeVi

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

10 papers
2 author rows

Possible papers

10

AAAI Conference 2026 Conference Paper

Silenced Biases: The Dark Side LLMs Learned to Refuse

  • Rom Himelstein
  • Amit LeVi
  • Brit Youngmann
  • Yaniv Nemcovsky
  • Avi Mendelson

Safety-aligned large language models (LLMs) are becoming increasingly widespread, especially in sensitive applications where fairness is essential and biased outputs can cause significant harm. However, evaluating the fairness of models is a complex challenge, and approaches that do so typically utilize standard question-answer (QA) styled schemes. Such methods often overlook deeper issues by interpreting the model's refusal responses as positive fairness measurements, which creates a false sense of fairness. In this work, we introduce the concept of silenced biases, which are unfair preferences encoded within models' latent space and are effectively concealed by safety-alignment. Previous approaches that considered similar indirect biases often relied on prompt manipulation or handcrafted implicit queries, which present limited scalability and risk contaminating the evaluation process with additional biases. We propose the Silenced Bias Benchmark (SBB), which aims to uncover these biases by employing activation steering to reduce model refusals during QA. SBB supports easy expansion to new demographic groups and subjects, presenting a fairness evaluation framework that encourages the future development of fair models and tools beyond the masking effects of alignment training. We demonstrate our approach over multiple LLMs, where our findings expose an alarming distinction between models' direct responses and their underlying fairness issues.

STOC Conference 2025 Conference Paper

Testing vs Estimation for Index-Invariant Properties in the Huge Object Model

  • Sourav Chakraborty 0001
  • Eldar Fischer
  • Arijit Ghosh
  • Amit Levi
  • Gopinath Mishra
  • Sayantan Sen

The Huge Object model of property testing [Goldreich and Ron, TheoretiCS 23] concerns properties of distributions supported on {0,1} n , where n is so large that even reading a single sampled string is unrealistic. Instead, query access is provided to the samples, and the efficiency of the algorithm is measured by the total number of queries that were made to them. Index-invariant properties under this model were defined in [Chakraborty et al., COLT 23], as a compromise between enduring the full intricacies of string testing when considering unconstrained properties, and giving up completely on the string structure when considering label-invariant properties. Index-invariant properties are those that are invariant through a consistent reordering of the bits of the involved strings. Here we provide an adaptation of Szemerédi’s regularity method for this setting, and in particular show that if an index-invariant property admits an є-test with a number of queries depending only on the proximity parameter є, then it also admits a distance estimation algorithm whose number of queries depends only on the approximation parameter.

JMLR Journal 2023 Journal Article

Graph Attention Retrospective

  • Kimon Fountoulakis
  • Amit LeVi
  • Shenghao Yang
  • Aseem Baranwal
  • Aukosh Jagannath

Graph-based learning is a rapidly growing sub-field of machine learning with applications in social networks, citation networks, and bioinformatics. One of the most popular models is graph attention networks. They were introduced to allow a node to aggregate information from features of neighbor nodes in a non-uniform way, in contrast to simple graph convolution which does not distinguish the neighbors of a node. In this paper, we theoretically study the behaviour of graph attention networks. We prove multiple results on the performance of the graph attention mechanism for the problem of node classification for a contextual stochastic block model. Here, the node features are obtained from a mixture of Gaussians and the edges from a stochastic block model. We show that in an "easy" regime, where the distance between the means of the Gaussians is large enough, graph attention is able to distinguish inter-class from intra-class edges. Thus it maintains the weights of important edges and significantly reduces the weights of unimportant edges. Consequently, we show that this implies perfect node classification. In the "hard" regime, we show that every attention mechanism fails to distinguish intra-class from inter-class edges. In addition, we show that graph attention convolution cannot (almost) perfectly classify the nodes even if intra-class edges could be separated from inter-class edges. Beyond perfect node classification, we provide a positive result on graph attention's robustness against structural noise in the graph. In particular, our robustness result implies that graph attention can be strictly better than both the simple graph convolution and the best linear classifier of node features. We evaluate our theoretical results on synthetic and real-world data. [abs] [ pdf ][ bib ] [ code ] &copy JMLR 2023. ( edit, beta )

ICLR Conference 2023 Conference Paper

Learnable Graph Convolutional Attention Networks

  • Adrián Javaloy
  • Pablo Sánchez-Martín
  • Amit Levi
  • Isabel Valera

Existing Graph Neural Networks (GNNs) compute the message exchange between nodes by either aggregating uniformly (convolving) the features of all the neighbor- ing nodes, or by applying a non-uniform score (attending) to the features. Recent works have shown the strengths and weaknesses of the resulting GNN architectures, respectively, GCNs and GATs. In this work, we aim at exploiting the strengths of both approaches to their full extent. To this end, we first introduce the graph convolutional attention layer (CAT), which relies on convolutions to compute the attention scores. Unfortunately, as in the case of GCNs and GATs, we show that there exists no clear winner between the three—neither theoretically nor in practice—as their performance directly depends on the nature of the data (i.e., of the graph and features). This result brings us to the main contribution of our work, the learnable graph convolutional attention network (L-CAT): a GNN architecture that automatically interpolates between GCN, GAT and CAT in each layer, by adding only two scalar parameters. Our results demonstrate that L-CAT is able to efficiently combine different GNN layers along the network, outperforming competing methods in a wide range of datasets, and resulting in a more robust model that reduces the need of cross-validating.

STOC Conference 2023 Conference Paper

Streaming Euclidean MST to a Constant Factor

  • Xi Chen 0001
  • Vincent Cohen-Addad
  • Rajesh Jayaram
  • Amit Levi
  • Erik Waingarten

We study streaming algorithms for the fundamental geometric problem of computing the cost of the Euclidean Minimum Spanning Tree (MST) on an n -point set X ⊂ ℝ d . In the streaming model, the points in X can be added and removed arbitrarily, and the goal is to maintain an approximation in small space. In low dimensions, (1+є) approximations are possible in sublinear space [Frahling, Indyk, Sohler, SoCG ’05]. However, for high dimensional spaces the best known approximation for this problem was Õ(log n ), due to [Chen, Jayaram, Levi, Waingarten, STOC ’22], improving on the prior O (log 2 n ) bound due to [Indyk, STOC ’04] and [Andoni, Indyk, Krauthgamer, SODA ’08]. In this paper, we break the logarithmic barrier, and give the first constant factor sublinear space approximation to Euclidean MST. For any є≥ 1, our algorithm achieves an Õ(є −2 ) approximation in n O (є) space. We complement this by proving that any single pass algorithm which obtains a better than 1.10-approximation must use Ω(√ n ) space, demonstrating that (1+є) approximations are not possible in high-dimensions, and that our algorithm is tight up to a constant. Nevertheless, we demonstrate that (1+є) approximations are possible in sublinear space with O (1/є) passes over the stream. More generally, for any α ≥ 2, we give a α-pass streaming algorithm which achieves a (1+ O (logα + 1/ α є)) approximation in n O (є) d O (1) space. All our streaming algorithms are linear sketches, and therefore extend to the massively-parallel computation model (MPC). Thus, our results imply the first (1+є)-approximation to Euclidean MST in a constant number of rounds in the MPC model. Previously, such a result was only known for low-dimensional space [Andoni, Nikolov, Onak, Yaroslavtsev, STOC ’15], or required either O (log n ) rounds or a O (log n ) approximation.

SODA Conference 2021 Conference Paper

Random Restrictions of High Dimensional Distributions and Uniformity Testing with Subcube Conditioning

  • Clément L. Canonne
  • Xi Chen 0001
  • Gautam Kamath 0001
  • Amit Levi
  • Erik Waingarten

We give a nearly-optimal algorithm for testing uniformity of distributions supported on {–1, 1} n, which makes many queries to a subcube conditional sampling oracle (Bhattacharyya and Chakraborty (2018)). The key technical component is a natural notion of random restrictions for distributions on {–1, 1} n, and a quantitative analysis of how such a restriction affects the mean vector of the distribution. Along the way, we consider the problem of mean testing with independent samples and provide a nearly-optimal algorithm.

SODA Conference 2020 Conference Paper

Nearly optimal edge estimation with independent set queries

  • Xi Chen 0001
  • Amit Levi
  • Erik Waingarten

We study the problem of estimating the number of edges of an unknown, undirected graph G = ([ n ], E ) with access to an independent set oracle. When queried about a subset S ⊆ [ n ] of vertices, the independent set oracle answers whether S is an independent set in G or not. Our first main result is an algorithm that computes a (1 + ϵ )-approximation of the number of edges m of the graph using · poly(log n, 1/ ϵ ) independent set queries. This improves the upper bound of · poly(log n, 1/ ε ) by Beame et al. [3]. Our second main result shows that /polylog( n ) independent set queries are necessary, thus establishing that our algorithm is optimal up to a factor of poly(log n, 1/ ϵ ).

SODA Conference 2018 Conference Paper

Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism

  • Eric Blais
  • Clément L. Canonne
  • Talya Eden
  • Amit Levi
  • Dana Ron

The function f: { – 1, 1} n → {– 1, 1} is a k -junta if it depends on at most k of its variables. We consider the problem of tolerant testing of k -juntas, where the testing algorithm must accept any function that is ∊-close to some k -junta and reject any function that is e ′-far from every k ′-junta for some ∊ ′ = O ( ∊ ) and k ′ = O ( k ). Our first result is an algorithm that solves this problem with query complexity polynomial in k and 1/ ∊. This result is obtained via a new polynomial-time approximation algorithm for submodular function minimization (SFM) under large cardinality constraints, which holds even when only given an approximate oracle access to the function. Our second result considers the case where k′ = k. We show how to obtain a smooth tradeoff between the amount of tolerance and the query complexity in this setting. Specifically, we design an algorithm that given ρ ∊ (0, 1/2) accepts any function that is -close to some k -junta and rejects any function that is ∊ -far from every k -junta. The query complexity of the algorithm is. Finally, we show how to apply the second result to the problem of tolerant isomorphism testing between two unknown Boolean functions f and g. We give an algorithm for this problem whose query complexity only depends on the (unknown) smallest k such that either f or g is close to being a k -junta.

FOCS Conference 2015 Conference Paper

Approximately Counting Triangles in Sublinear Time

  • Talya Eden
  • Amit Levi
  • Dana Ron
  • C. Seshadhri 0001

We consider the problem of estimating the number of triangles in a graph. This problem has been extensively studied in both theory and practice, but all existing algorithms read the entire graph. In this work we design a sublinear-time algorithm for approximating the number of triangles in a graph, where the algorithm is given query access to the graph. The allowed queries are degree queries, vertex-pair queries and neighbor queries. We show that for any given approximation parameter 0<; epsilon<; 1, the algorithm provides an estimate hat{t} such that with high constant probability, (1-epsilon) t<; hat{t}κ(1+epsilon)t, where t is the number of triangles in the graph G. The expected query complexity of the algorithm is O(n/t̂{1/3} + min {m, m̂{3/2}/t}) poly(log n, 1/epsilon), where n is the number of vertices in the graph and m is the number of edges, and the expected running time is (n/t̂{1/3} + m̂{3/2}/t) poly(log n, 1/epsilon). We also prove that Omega(n/t̂{1/3} + min {m, m̂{3/2}/t}) queries are necessary, thus establishing that the query complexity of this algorithm is optimal up to polylogarithmic factors in n (and the dependence on 1/epsilon).