Arrow Research search

Author name cluster

David Eisenstat

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.

8 papers
2 author rows

Possible papers

8

NeurIPS Conference 2022 Conference Paper

Hierarchical Agglomerative Graph Clustering in Poly-Logarithmic Depth

  • Laxman Dhulipala
  • David Eisenstat
  • Jakub Lacki
  • Vahab Mirrokni
  • Jessica Shi

Obtaining scalable algorithms for \emph{hierarchical agglomerative clustering} (HAC) is of significant interest due to the massive size of real-world datasets. At the same time, efficiently parallelizing HAC is difficult due to the seemingly sequential nature of the algorithm. In this paper, we address this issue and present ParHAC, the first efficient parallel HAC algorithm with sublinear depth for the widely-used average-linkage function. In particular, we provide a $(1+\epsilon)$-approximation algorithm for this problem on $m$ edge graphs using $\tilde{O}(m)$ work and poly-logarithmic depth. Moreover, we show that obtaining similar bounds for \emph{exact} average-linkage HAC is not possible under standard complexity-theoretic assumptions. We complement our theoretical results with a comprehensive study of the ParHAC algorithm in terms of its scalability, performance, and quality, and compare with several state-of-the-art sequential and parallel baselines. On a broad set of large publicly-available real-world datasets, we find that ParHAC obtains a 50. 1x speedup on average over the best sequential baseline, while achieving quality similar to the exact HAC algorithm. We also show that ParHAC can cluster one of the largest publicly available graph datasets with 124 billion edges in a little over three hours using a commodity multicore machine.

PDF Details

ICML Conference 2021 Conference Paper

Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time

  • Laxman Dhulipala
  • David Eisenstat
  • Jakub Lacki
  • Vahab Mirrokni
  • Jessica Shi 0001

We study the widely-used hierarchical agglomerative clustering (HAC) algorithm on edge-weighted graphs. We define an algorithmic framework for hierarchical agglomerative graph clustering that provides the first efficient $\tilde{O}(m)$ time exact algorithms for classic linkage measures, such as complete- and WPGMA-linkage, as well as other measures. Furthermore, for average-linkage, arguably the most popular variant of HAC, we provide an algorithm that runs in $\tilde{O}(n\sqrt{m})$ time. For this variant, this is the first exact algorithm that runs in subquadratic time, as long as $m=n^{2-\epsilon}$ for some constant $\epsilon > 0$. We complement this result with a simple $\epsilon$-close approximation algorithm for average-linkage in our framework that runs in $\tilde{O}(m)$ time. As an application of our algorithms, we consider clustering points in a metric space by first using $k$-NN to generate a graph from the point set, and then running our algorithms on the resulting weighted graph. We validate the performance of our algorithms on publicly available datasets, and show that our approach can speed up clustering of point datasets by a factor of 20. 7–76. 5x.

Details

SODA Conference 2017 Conference Paper

Time-Space Trade-offs in Population Protocols

  • Dan Alistarh
  • James Aspnes
  • David Eisenstat
  • Rati Gelashvili
  • Ronald L. Rivest

Population protocols are a popular model of distributed computing, in which randomly-interacting agents with little computational power cooperate to jointly perform computational tasks. Inspired by developments in molecular computation, and in particular DNA computing, recent algorithmic work has focused on the complexity of solving simple yet fundamental tasks in the population model, such as leader election (which requires convergence to a single agent in a special “leader” state), and majority (in which agents must converge to a decision as to which of two possible initial states had higher initial count). Known results point towards an inherent trade-off between the time complexity of such algorithms, and the space complexity, i. e. size of the memory available to each agent. In this paper, we explore this trade-off and provide new upper and lower bounds for majority and leader election. First, we prove a unified lower bound, which relates the space available per node with the time complexity achievable by a protocol: for instance, our result implies that any protocol solving either of these tasks for n agents using O (log log n ) states must take Ω( n /polylog n ) expected time. This is the first result to characterize time complexity for protocols which employ super-constant number of states per node, and proves that fast, poly-logarithmic running times require protocols to have relatively large space costs. On the positive side, we give algorithms showing that fast, poly-logarithmic convergence time can be achieved using O (log 2 n ) space per node, in the case of both tasks. Overall, our results highlight a time complexity separation between O (log log n ) and Θ(log 2 n ) state space size for both majority and leader election in population protocols, and introduce new techniques, which should be applicable more broadly.

Details

SODA Conference 2014 Conference Paper

Approximating k -center in planar graphs

  • David Eisenstat
  • Philip N. Klein
  • Claire Mathieu

We consider variants of the metric k -center problem. Imagine that you must choose locations for k firehouses in a city so as to minimize the maximum distance of a house from the nearest firehouse. An instance is specified by a graph with arbitrary nonnegative edge lengths, a set of vertices that can serve as firehouses (i. e. , centers) and a set of vertices that represent houses. For general graphs, this problem is exactly equivalent to the metric k -center problem, which is APX-hard. We give a polynomial-time bicriteria approximation scheme when the input graph is a planar graph. We also give polynomial-time bicriteria approximation schemes for several generalizations: if, instead of all houses, we wish to cover a specified proportion of the houses; if the candidate locations for firehouses have rental costs and we wish to minimize not the number of firehouses but the sum of their rental costs; and if the input graph is not planar but is of bounded genus.

Details

I&C Journal 2014 Journal Article

Effective storage capacity of labeled graphs

  • Dana Angluin
  • James Aspnes
  • Rida A. Bazzi
  • Jiang Chen
  • David Eisenstat
  • Goran Konjevod

We consider the question of how much information can be stored by labeling the vertices of a connected undirected graph G using a constant-size set of labels, when isomorphic labelings are not distinguishable. Specifically, we are interested in the effective capacity of members of some class of graphs, the number of states distinguishable by a Turing machine that uses the labeled graph itself in place of the usual linear tape. We show that the effective capacity is related to the information-theoretic capacity which we introduce in the paper. It equals the information-theoretic capacity of the graph up to constant factors for trees, random graphs with polynomial edge probabilities, and bounded-degree graphs.

Details DOI

JMLR Journal 2009 Journal Article

Learning Acyclic Probabilistic Circuits Using Test Paths

  • Dana Angluin
  • James Aspnes
  • Jiang Chen
  • David Eisenstat
  • Lev Reyzin

We define a model of learning probabilistic acyclic circuits using value injection queries, in which fixed values are assigned to an arbitrary subset of the wires and the value on the single output wire is observed. We adapt the approach of using test paths from the Circuit Builder algorithm (Angluin et al., 2009) to show that there is a polynomial time algorithm that uses value injection queries to learn acyclic Boolean probabilistic circuits of constant fan-in and log depth. We establish upper and lower bounds on the attenuation factor for general and transitively reduced Boolean probabilistic circuits of test paths versus general experiments. We give computational evidence that a polynomial time learning algorithm using general value injection experiments may not do much better than one using test paths. For probabilistic circuits with alphabets of size three or greater, we show that the test path lemmas (Angluin et al., 2009, 2008b) fail utterly. To overcome this obstacle, we introduce function injection queries, in which the values on a wire may be mapped to other values rather than just to themselves or constants, and prove a generalized test path lemma for this case. [abs] [ pdf ][ bib ] &copy JMLR 2009. ( edit, beta )

PDF Details
v2026.09.13