Talya Eden

STOC Conference 2025 Conference Paper

Approximately Counting and Sampling Hamiltonian Motifs in Sublinear Time

• Talya Eden
• Reut Levi
• Dana Ron
• Ronitt Rubinfeld

NeurIPS Conference 2024 Conference Paper

Plant-and-Steal: Truthful Fair Allocations via Predictions

• Ilan R. Cohen
• Alon Eden
• Talya Eden
• Arsen Vasilyan

We study truthful mechanisms for approximating the Maximin-Share (MMS) allocation of agents with additive valuations for indivisible goods. Algorithmically, constant factor approximations exist for the problem for any number of agents. When adding incentives to the mix, a jarring result by Amanatidis, Birmpas, Christodoulou, and Markakis [EC 2017] shows that the best possible approximation for two agents and $m$ items is $\lfloor \frac{m}{2} \rfloor$. We adopt a learning-augmented framework to investigate what is possible when some prediction on the input is given. For two agents, we give a truthful mechanism that takes agents' ordering over items as prediction. When the prediction is accurate, we give a $2$-approximation to the MMS (consistency), and when the prediction is off, we still get an $\lceil \frac{m}{2} \rceil$-approximation to the MMS (robustness). We further show that the mechanism's performance degrades gracefully in the number of ``mistakes" in the prediction; i. e. , we interpolate (up to constant factors) between the two extremes: when there are no mistakes, and when there is a maximum number of mistakes. We also show an impossibility result on the obtainable consistency for mechanisms with finite robustness. For the general case of $n\ge 2$ agents, we give a 2-approximation mechanism for accurate predictions, with relaxed fallback guarantees. Finally, we give experimental results which illustrate when different components of our framework, made to insure consistency and robustness, come into play.

SODA Conference 2022 Conference Paper

Approximating the Arboricity in Sublinear Time

• Talya Eden
• Saleet Mossel
• Dana Ron

We consider the problem of approximating the arboricity of a graph G = (V, E ), which we denote by arb( G ), in sublinear time, where the arboricity of a graph is the minimal number of forests required to cover its edge set. An algorithm for this problem may perform degree and neighbor queries, and is allowed a small error probability. We design an algorithm that outputs an estimate, such that with probability 1–1/poly(n), arb( G ) ≤ ≤ c log 2 n -arb( G ), where n = |V| and c is a constant. The expected query complexity and running time of the algorithm are O ( n /arb( G )) · poly(log n), and this upper bound also holds with high probability. This bound is optimal for such an approximation up to a poly (log n) factor. For the closely related problem of finding the densest subgraph, Bhattacharya et al. (STOC, 2015) showed that there exists a factor-2 approximation algorithm that runs in time O(n ) · poly (log n). In a follow up work, McGregor et al. (MFCS, 2015) improved the approximation factor to (1 + ∊ ) with the same complexity.

ICLR Conference 2022 Conference Paper

Triangle and Four Cycle Counting with Predictions in Graph Streams

• Justin Y. Chen
• Talya Eden
• Piotr Indyk
• Honghao Lin
• Shyam Narayanan
• Ronitt Rubinfeld
• Sandeep Silwal
• Tal Wagner

We propose data-driven one-pass streaming algorithms for estimating the number of triangles and four cycles, two fundamental problems in graph analytics that are widely studied in the graph data stream literature. Recently, Hsu et al. (2019) and Jiang et al. (2020) applied machine learning techniques in other data stream problems, using a trained oracle that can predict certain properties of the stream elements to improve on prior “classical” algorithms that did not use oracles. In this paper, we explore the power of a “heavy edge” oracle in multiple graph edge streaming models. In the adjacency list model, we present a one-pass triangle counting algorithm improving upon the previous space upper bounds without such an oracle. In the arbitrary order model, we present algorithms for both triangle and four cycle estimation with fewer passes and the same space complexity as in previous algorithms, and we show several of these bounds are optimal. We analyze our algorithms under several noise models, showing that the algorithms perform well even when the oracle errs. Our methodology expands upon prior work on “classical” streaming algorithms, as previous multi-pass and random order streaming algorithms can be seen as special cases of our algorithms, where the first pass or random order was used to implement the heavy edge oracle. Lastly, our experiments demonstrate advantages of the proposed method compared to state-of-the-art streaming algorithms.

ICLR Conference 2021 Conference Paper

Learning-based Support Estimation in Sublinear Time

• Talya Eden
• Piotr Indyk
• Shyam Narayanan
• Ronitt Rubinfeld
• Sandeep Silwal
• Tal Wagner

We consider the problem of estimating the number of distinct elements in a large data set (or, equivalently, the support size of the distribution induced by the data set) from a random sample of its elements. The problem occurs in many applications, including biology, genomics, computer systems and linguistics. A line of research spanning the last decade resulted in algorithms that estimate the support up to $ \pm \varepsilon n$ from a sample of size $O(\log^2(1/\varepsilon) \cdot n/\log n)$, where $n$ is the data set size. Unfortunately, this bound is known to be tight, limiting further improvements to the complexity of this problem. In this paper we consider estimation algorithms augmented with a machine-learning-based predictor that, given any element, returns an estimation of its frequency. We show that if the predictor is correct up to a constant approximation factor, then the sample complexity can be reduced significantly, to $$ \ \log (1/\varepsilon) \cdot n^{1-\Theta(1/\log(1/\varepsilon))}. $$ We evaluate the proposed algorithms on a collection of data sets, using the neural-network based estimators from {Hsu et al, ICLR'19} as predictors. Our experiments demonstrate substantial (up to 3x) improvements in the estimation accuracy compared to the state of the art algorithm.

SODA Conference 2020 Conference Paper

Faster sublinear approximation of the number of k -cliques in low-arboricity graphs

• Talya Eden
• Dana Ron
• C. Seshadhri 0001

STOC Conference 2018 Conference Paper

On approximating the number of k-cliques in sublinear time

• Talya Eden
• Dana Ron
• C. Seshadhri 0001

We study the problem of approximating the number of k -cliques in a graph when given query access to the graph. We consider the standard query model for general graphs via (1) degree queries, (2) neighbor queries and (3) pair queries. Let n denote the number of vertices in the graph, m the number of edges, and C k the number of k -cliques. We design an algorithm that outputs a (1+ε)-approximation (with high probability) for C k , whose expected query complexity and running time are O ( n / C k 1/ k + m k /2 / C k )(log n , 1/ε, k ). Hence, the complexity of the algorithm is sublinear in the size of the graph for C k = ω( m k /2−1 ). Furthermore, we prove a lower bound showing that the query complexity of our algorithm is essentially optimal (up to the dependence on log n , 1/ε and k ). The previous results in this vein are by Feige (SICOMP 06) and by Goldreich and Ron (RSA 08) for edge counting ( k =2) and by Eden et al. (FOCS 2015) for triangle counting ( k =3). Our result matches the complexities of these results. The previous result by Eden et al. hinges on a certain amortization technique that works only for triangle counting, and does not generalize for larger cliques. We obtain a general algorithm that works for any k ≥ 3 by designing a procedure that samples each k -clique incident to a given set S of vertices with approximately equal probability. The primary difficulty is in finding cliques incident to purely high-degree vertices, since random sampling within neighbors has a low success probability. This is achieved by an algorithm that samples uniform random high degree vertices and a careful tradeoff between estimating cliques incident purely to high-degree vertices and those that include a low-degree vertex.

SODA Conference 2018 Conference Paper

Testing bounded arboricity

• Talya Eden
• Reut Levi
• Dana Ron

In this paper we consider the problem of testing whether a graph has bounded arboricity. The family of graphs with bounded arboricity includes, among others, bounded-degree graphs, all minor-closed graph classes (e. g. planar graphs, graphs with bounded treewidth) and randomly generated preferential attachment graphs. Graphs with bounded arboricity have been studied extensively in the past, in particular since for many problems they allow for much more efficient algorithms and/or better approximation ratios. We present a tolerant tester in the sparse-graphs model. The sparse-graphs model allows access to degree queries and neighbor queries, and the distance is defined with respect to the actual number of edges. More specifically, our algorithm distinguishes between graphs that are e-close to having arboricity α and graphs that c · ∊ -far from having arboricity 3 α, where c is an absolute small constant. The query complexity and running time of the algorithm are 1 where n denotes the number of vertices and m denotes the number of edges. In terms of the dependence on n and m this bound is optimal up to poly-logarithmic factors since queries are necessary (and the arboricity of a graph is always. We leave it as an open question whether the dependence on 1/ ∊ can be improved from quasi-polynomial to polynomial. Our techniques include an efficient local simulation for approximating the outcome of a global (almost) forest-decomposition algorithm as well as a tailored procedure of edge sampling.

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).