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 "onthefly" (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 sublinear and thus, sampling the entire objectmore »
Sublinear Time Hypergraph Sparsification via Cut and Edge Sampling Queries
The problem of sparsifying a graph or a hypergraph while approximately preserving its cut structure has been extensively studied and has many applications. In a seminal work, Benczúr and Karger (1996) showed that given any nvertex undirected weighted graph G and a parameter ε ∈ (0,1), there is a nearlinear time algorithm that outputs a weighted subgraph G' of G of size Õ(n/ε²) such that the weight of every cut in G is preserved to within a (1 ± ε)factor in G'. The graph G' is referred to as a (1 ± ε)approximate cut sparsifier of G. Subsequent recent work has obtained a similar result for the more general problem of hypergraph cut sparsifiers. However, all known sparsification algorithms require Ω(n + m) time where n denotes the number of vertices and m denotes the number of hyperedges in the hypergraph. Since m can be exponentially large in n, a natural question is if it is possible to create a hypergraph cut sparsifier in time polynomial in n, independent of the number of edges. We resolve this question in the affirmative, giving the first sublinear time algorithm for this problem, given appropriate query access to the hypergraph.
Specifically, we design an more »
 Publication Date:
 NSFPAR ID:
 10290894
 Journal Name:
 48th International Colloquium on Automata, Languages, and Programming
 Sponsoring Org:
 National Science Foundation
More Like this


The cumulative pebbling complexity of a directed acyclic graph G is defined as cc(G) = min_P ∑_i P_i, where the minimum is taken over all legal (parallel) black pebblings of G and P_i denotes the number of pebbles on the graph during round i. Intuitively, cc(G) captures the amortized SpaceTime complexity of pebbling m copies of G in parallel. The cumulative pebbling complexity of a graph G is of particular interest in the field of cryptography as cc(G) is tightly related to the amortized AreaTime complexity of the DataIndependent MemoryHard Function (iMHF) f_{G,H} [Joël Alwen and Vladimir Serbinenko, 2015] definedmore »

Consider an algorithm performing a computation on a huge random object. Is it necessary to generate the entire object up front, or is it possible to provide query access to the object and sample it incrementally "onthefly"? Such an implementation should emulate the object by answering queries in a manner consistent with a random instance sampled from the true distribution. Our first set of results focus on undirected graphs with independent edge probabilities, under certain assumptions. Then, we use this to obtain the first efficient implementations for the ErdosRenyi model and the Stochastic Block model. As in previous localaccess implementationsmore »

For a graph G on n vertices, naively sampling the position of a random walk of at time t requires work Ω(t). We desire local access algorithms supporting positionG(t) queries, which return the position of a random walk from some fixed start vertex s at time t, where the joint distribution of returned positions is 1/ poly(n) close to those of a uniformly random walk in ℓ1 distance. We first give an algorithm for local access to random walks on a given undirected dregular graph with eO( 1 1−λ √ n) runtime per query, where λ is the secondlargest eigenvaluemore »

Let f be a drawing in the Euclidean plane of a graph G, which is understood to be a 1dimensional simplicial complex. We assume that every edge of G is drawn by f as a curve of constant algebraic complexity, and the ratio of the length of the longest simple path to the the length of the shortest edge is poly(n). In the drawing f, a path P of G, or its image in the drawing π = f(P), is βstretch if π is a simple (nonselfintersecting) curve, and for every pair of distinct points p ∈ P and qmore »