Given a large set U where each item a∈ U has weight w(a), we want to estimate the total weight \(W=\sum _{a∈ U} w(a)\) to within factor of 1± ɛ with some constant probability > 1/2. Since n=|U| is large, we want to do this without looking at the ...

We study algorithms for estimating the size of maximum matching. This problem has been subject to extensive research. For n-vertex graphs, Bhattacharya, Kiss, and Saranurak [FOCS’23] (BKS) showed that an estimate that is within є n of the optimal ...

While the search for quantum advantage typically focuses on speed­ups in execution time, quantum algorithms also offer the potential for advantage in space complexity. Previous work has shown such advantages for data stream problems, in which elements ...

We revisit ApproxContributions, the classic local graph exploration algorithm proposed by Andersen, Borgs, Chayes, Hopcroft, Mirrokni, and Teng (WAW ’07, Internet Math. ’08) for computing an є-approximation of the PageRank contribution vector for a ...

We consider the following basic, and very broad, statistical problem: Given a known high-dimensional distribution D over ℝⁿ and a collection of data points in ℝⁿ, distinguish between the two possibilities that (i) the data was drawn from D, versus (ii) ...

We study the following problem: Given an integer k ≥ 3 and a simple graph G, sample a connected induced k-vertex subgraph of G uniformly at random. This is a fundamental graph mining primitive with applications in social network analysis, bioinformatics, ...

Sublinear time algorithms for approximating maximum matching size have long been studied. Much of the progress over the last two decades on this problem has been on the algorithmic side. For instance, an algorithm of [Behnezhad; FOCS’21] obtains a 1/2-...

Vertex connectivity is a well-studied concept in graph theory with numerous applications. A graph is k-connected if it remains connected after removing any k −1 vertices. The vertex connectivity of a graph is the maximum k such that the graph is k-...

We present an algorithmic framework for quantum-inspired classical algorithms on close-to-low-rank matrices, generalizing the series of results started by Tang’s breakthrough quantum-inspired algorithm for recommendation systems [STOC’19]. Motivated by ...

This paper considers standard T-interval dynamic networks, where the N nodes in the network proceed in lock-step rounds, and where the topology of the network can change arbitrarily from round to round, as determined by an adversary. The adversary ...

Let $G$ be a graph with $n$ vertices and maximum degree $d$. Fix some minor-closed property $\mathcal{P}$ (such as planarity). We say that $G$ is $\varepsilon$-far from $\mathcal{P}$ if one has to remove $\varepsilon dn$ edges to make it have $\mathcal{P}$...

We consider the problem of sampling from a distribution on graphs, specifically when the distribution is defined by an evolving graph model, and consider the time, space, and randomness complexities of such samplers.

In the standard approach, the whole ...

We study the graphlet sampling problem: given an integer k ≥ 3 and a graph G=(V,E), sample a connected induced k-node subgraph of G (also called k-graphlet) uniformly at random. This is a fundamental graph mining primitive, with applications in social ...

We consider standard T-interval dynamic networks, under the synchronous timing model and the broadcast CONGEST model. In a T-interval dynamic network, the set of nodes is always fixed and there are no node failures. The edges in the network are always ...

Suppose that we are given an arbitrary graph G=(V, E) and know that each edge in E is going to be realized independently with some probability p. The goal in the stochastic matching problem is to pick a sparse subgraph Q of G such that the realized ...

A longstanding observation, which was partially proven by Li, Nguyen, and Woodruff in 2014, and extended by Ai, Hu, Li, and Woodruff in 2016, is that any turnstile streaming algorithm can be implemented as a linear sketch (the reverse is trivially true)...

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

In hedonic games, players form coalitions based on individual preferences over the group of players they belong to. Several concepts to describe the stability of coalition structures in a game have been proposed and analysed. However, prior research ...

The spectrum of a network or graph $G=(V,E)$ with adjacency matrix A , consists of the eigenvalues of the normalized Laplacian $L= I - D^-1/2 A D^-1/2 $. This set of eigenvalues encapsulates many aspects of the structure of the graph, including the ...

Can one compute the PageRank score of a single, arbitrary node in a graph, exploring only a vanishing fraction of the graph? We provide a positive answer to this extensively researched open question. We develop the first algorithm that, for any n -node ...