More Like this

1. On the trace of random walks on random graphs

   Frieze, A; Krivelevich, M; Michaeli, P; Peled, R (January 2017, Journal of the London Mathematical Society)

   We study graph-theoretic properties of the trace of a random walk on a random graph. We show that for any $$\varepsilon>0$$ there exists $C>1$ such that the trace of the simple random walk of length $$(1+\varepsilon)n\ln{n}$$ on the random graph $$G\sim\gnp$$ for $$p>C\ln{n}/n$$ is, with high probability, Hamiltonian and $$\Theta(\ln{n})$$-connected. In the special case $p=1$$ (i.e.\ when $$G=K_n$), we show a hitting time result according to which, with high probability, exactly one step after the last vertex has been visited, the trace becomes Hamiltonian, and one step after the last vertex has been visited for the $$k$$'th time, the trace becomes $2k$-connected. 

   more » « less
2. Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time

   Ene, Alina; Nguyen, Huy L. (January 2019, Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms)

   In this paper, we study the tradeoff between the approximation guarantee and adaptivity for the problem of maximizing a monotone submodular function subject to a cardinality constraint. The adaptivity of an algorithm is the number of sequential rounds of queries it makes to the evaluation oracle of the function, where in every round the algorithm is allowed to make polynomially-many parallel queries. Adaptivity is an important consideration in settings where the objective function is estimated using samples and in applications where adaptivity is the main running time bottleneck. Previous algorithms achieving a nearly-optimal $$1 - 1/e - \epsilon$$ approximation require $$\Omega(n)$$ rounds of adaptivity. In this work, we give the first algorithm that achieves a $$1 - 1/e - \epsilon$$ approximation using $$O(\ln{n} / \epsilon^2)$$ rounds of adaptivity. The number of function evaluations and additional running time of the algorithm are $$O(n \; \mathrm{poly}(\log{n}, 1/\epsilon))$$. 

   more » « less
3. Balanced Allocation Through Random Walk

   Frieze, A.; Petti, S (December 2018, Information processing letters)

   We consider the allocation problem in which $$m \leq (1-\epsilon) dn $$ items are to be allocated to $$n$$ bins with capacity $$d$$. The items $$x_1,x_2,\ldots,x_m$$ arrive sequentially and when item $$x_i$$ arrives it is given two possible bin locations $$p_i=h_1(x_i),q_i=h_2(x_i)$$ via hash functions $$h_1,h_2$$. We consider a random walk procedure for inserting items and show that the expected time insertion time is constant provided $$\epsilon = \Omega\left(\sqrt{ \frac{ \log d}{d}} \right).$$ 

   more » « less
4. Local Access to Huge Random Objects Through Partial Sampling

   Biswas, Amartya Shankha; Rubinfeld, Ronitt; Yodpinyanee, Anak (January 2020, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020)

   null (Ed.)

   Consider an algorithm performing a computation on a huge random object (for example a random graph or a "long" random walk). Is it necessary to generate the entire object prior to the computation, or is it possible to provide query access to the object and sample it incrementally "on-the-fly" (as requested by the algorithm)? Such an implementation should emulate the random object by answering queries in a manner consistent with an instance of the random object sampled from the true distribution (or close to it). This paradigm is useful when the algorithm is sub-linear and thus, sampling the entire object up front would ruin its efficiency. Our first set of results focus on undirected graphs with independent edge probabilities, i.e. each edge is chosen as an independent Bernoulli random variable. We provide a general implementation for this model under certain assumptions. Then, we use this to obtain the first efficient local implementations for the Erdös-Rényi G(n,p) model for all values of p, and the Stochastic Block model. As in previous local-access implementations for random graphs, we support Vertex-Pair and Next-Neighbor queries. In addition, we introduce a new Random-Neighbor query. Next, we give the first local-access implementation for All-Neighbors queries in the (sparse and directed) Kleinberg’s Small-World model. Our implementations require no pre-processing time, and answer each query using O(poly(log n)) time, random bits, and additional space. Next, we show how to implement random Catalan objects, specifically focusing on Dyck paths (balanced random walks on the integer line that are always non-negative). Here, we support Height queries to find the location of the walk, and First-Return queries to find the time when the walk returns to a specified location. This in turn can be used to implement Next-Neighbor queries on random rooted ordered trees, and Matching-Bracket queries on random well bracketed expressions (the Dyck language). Finally, we introduce two features to define a new model that: (1) allows multiple independent (and even simultaneous) instantiations of the same implementation, to be consistent with each other without the need for communication, (2) allows us to generate a richer class of random objects that do not have a succinct description. Specifically, we study uniformly random valid q-colorings of an input graph G with maximum degree Δ. This is in contrast to prior work in the area, where the relevant random objects are defined as a distribution with O(1) parameters (for example, n and p in the G(n,p) model). The distribution over valid colorings is instead specified via a "huge" input (the underlying graph G), that is far too large to be read by a sub-linear time algorithm. Instead, our implementation accesses G through local neighborhood probes, and is able to answer queries to the color of any given vertex in sub-linear time for q ≥ 9Δ, in a manner that is consistent with a specific random valid coloring of G. Furthermore, the implementation is memory-less, and can maintain consistency with non-communicating copies of itself. 

   more » « less
5. Multiplicative Weights Update, Area Convexity and Random Coordinate Descent for Densest Subgraph Problems

   Nguyen, Ta Duy; Ene, Alina (July 2024, International Conference on Machine Learning)

   We study the densest subgraph problem and give algorithms via multiplicative weights update and area convexity that converge in $$O\left(\frac{\log m}{\epsilon^{2}}\right)$$ and $$O\left(\frac{\log m}{\epsilon}\right)$$ iterations, respectively, both with nearly-linear time per iteration. Compared with the work by Bahmani et al. (2014), our MWU algorithm uses a very different and much simpler procedure for recovering the dense subgraph from the fractional solution and does not employ a binary search. Compared with the work by Boob et al. (2019), our algorithm via area convexity improves the iteration complexity by a factor $$\Delta$$ — the maximum degree in the graph, and matches the fastest theoretical runtime currently known via flows (Chekuri et al., 2022) in total time. Next, we study the dense subgraph decomposition problem and give the first practical iterative algorithm with linear convergence rate $$O\left(mn\log\frac{1}{\epsilon}\right)$$ via accelerated random coordinate descent. This significantly improves over $$O\left(\frac{m\sqrt{mn\Delta}}{\epsilon}\right)$$ time of the FISTA-based algorithm by Harb et al. (2022). In the high precision regime $$\epsilon\ll\frac{1}{n}$$ where we can even recover the exact solution, our algorithm has a total runtime of $$O\left(mn\log n\right)$$, matching the state of the art exact algorithm via parametric flows (Gallo et al., 1989). Empirically, we show that this algorithm is very practical and scales to very large graphs, and its performance is competitive with widely used methods that have significantly weaker theoretical guarantees. 

   more » « less