Amartya Shankha Biswas, Ronitt Rubinfeld, Anak Yodpinyanee
Innovations in Theoretical Computer Science Conference (ITCS) 2020
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 Erdos-Renyi model for all values of , 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 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 -colorings of an input graph with maximum degree . This is in contrast to prior work in the area, where the relevant random objects are defined as a distribution with parameters (for example, and in the model). The distribution over valid colorings is instead specified via a “huge” input (the underlying graph ), that is far too large to be read by a sub-linear time algorithm. Instead, our implementation accesses through local neighborhood probes, and is able to answer queries to the color of any given vertex in sub-linear time for , in a manner that is consistent with a specific random valid coloring of . Furthermore, the implementation is memory-less, and can maintain consistency with non-communicating copies of itself.
Maryam Aliakbarpour, Amartya Shankha Biswas, Themis Gouleakis, John Peebles, Ronitt Rubinfeld, Anak Yodpinyanee
We study the problem of estimating the value of sums of the form when one has the ability to sample with probability proportional to its magnitude. When , this problem is equivalent to estimating the selectivity of a self-join query in database systems when one can sample rows randomly. We also study the special case when is the degree sequence of a graph, which corresponds to counting the number of -stars in a graph when one has the ability to sample edges randomly. Our algorithm for a -multiplicative approximation of has query and time complexities . Here, is the number of edges in the graph, or equivalently, half the number of records in the database table. Similarly, is the number of vertices in the graph and the number of unique values in the database table. We also provide tight lower bounds (up to polylogarithmic factors) in almost all cases, even when is a degree sequence and one is allowed to use the structure of the graph to try to get a better estimate. We are not aware of any prior lower bounds on the problem of join selectivity estimation. For the graph problem, prior work which assumed the ability to sample only vertices uniformly gave algorithms with matching lower bounds (Gonen et al. in SIAM J Comput 25:1365–1411, 2011). With the ability to sample edges randomly, we show that one can achieve faster algorithms for approximating the number of star subgraphs, bypassing the lower bounds in this prior work. For example, in the regime where , and , our upper bound is , in contrast to their lower bound when no random edge queries are available. In addition, we consider the problem of counting the number of directed paths of length two when the graph is directed. This problem is equivalent to estimating the selectivity of a join query between two distinct tables. We prove that the general version of this problem cannot be solved in sublinear time. However, when the ratio between in-degree and out-degree is bounded—or equivalently, when the ratio between the number of occurrences of values in the two columns being joined is bounded—we give a sublinear time algorithm via a reduction to the undirected case.
Amartya Shankha Biswas, Erik D Demaine
Canadian Conference on Computational Geometry (CCCG) 2017
We construct an uncountably infinite family of flat unfoldings, each of which can be folded into twelve distinct convex solids, while also tiling the plane.
Amartya Shankha Biswas, Erik D Demaine, Jason S Ku
International Meeting on Origami in Science, Mathematics and Education (7OSME) 2017
We introduce a new method of origami construction, using cross section diagrams. Instead of beginning our construction from a 2-dimensional sheet of paper, we consider a 1-dimensional cross section moving forwards in time. We obtain conditions for the validity of a particular cross section evolution sequence, and prove that the resulting folded state is isometric to a flat sheet of paper. Subsequently, we use this machinery to design an efficient construction of orthogonal terrains, with arbitrary rational extrusion heights.