 Home
 Search Results
 Page 1 of 1
Search for: All records

Total Resources3
 Resource Type

30
 Availability

30
 Author / Contributor
 Filter by Author / Creator


Biswas, Amartya Shankha (3)

Rubinfeld, Ronitt (3)

Yodpinyanee, Anak (3)

Aliakbarpour, Maryam (1)

Gouleakis, Themis (1)

Peebles, John (1)

#Tyler Phillips, Kenneth E. (0)

& *Soto, E. (0)

& Ahmed, Khadija. (0)

& AkcilOkan, O. (0)

& Akuom, D. (0)

& AndrewsLarson, C. (0)

& Archibald, J. (0)

& Attari, S. Z. (0)

& Ayala, O. (0)

& Babbitt, W. (0)

& Baek, Y. (0)

& Bai, F. (0)

& BarthCohen, L. (0)

& Bassett, L. (0)

 Filter by Editor


& Ahn, J. (0)

& Bateiha, S. (0)

& Chen, B. (0)

& Chen, Bodong (0)

& Kali, Y. (0)

& RuizArias, P.M. (0)

& Spitzer, S. (0)

& Spitzer, S.M. (0)

:Chaosong Huang, Gang Lu (0)

A. Beygelzimer (0)

A. Ghate, K. Krishnaiyer (0)

A. I. Sacristán, J. C. (0)

A. Weinberg, D. MooreRusso (0)

A. Weinberger (0)

A.I. Sacristán, J.C. CortésZavala (0)

A.I., Dimitrova (0)

ACS (0)

AIAA (0)

AIAA Propulsion and Energy 2021 (0)

AIAA SciTech (0)


Have feedback or suggestions for a way to improve these results?
!
Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

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 »

Biswas, Amartya Shankha ; Rubinfeld, Ronitt ; Yodpinyanee, Anak ( , 11th Innovations in Theoretical Computer Science (ITCS 2020))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 random graphs, we support VertexPair and NextNeighbor queries. We also introduce a new RandomNeighbor query. Next, we show how to implement random Catalan objects, specifically focusing on Dyck paths (always positive random walks on the integer line). Here, we support Height queries to find the position of the walk, and FirstReturn queries to find the time when the walk returns to a specified height. This in turn can be used to implement NextNeighbor queries on random rooted/binary trees, and MatchingBracket queries on random well bracketed expressions. Finally, we define a new model that: (1) allows multiple independent simultaneous instantiations of the same implementation to be consistent with each other without 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 qcolorings of an input graph G with max degree Δ. The distribution over valid colorings is specified via a "huge" underlying graph G, that is far too large to be read in sublinear time. Instead, we access G through local neighborhood probes. We are able to answer queries to the color of any vertex in sublinear time for q>9Δ.« less

Aliakbarpour, Maryam ; Biswas, Amartya Shankha ; Gouleakis, Themis ; Peebles, John ; Rubinfeld, Ronitt ; Yodpinyanee, Anak ( , Algorithmica)We study the problem of estimating the value of sums of the form Sp≜∑(xip) when one has the ability to sample xi≥0 with probability proportional to its magnitude. When p=2, this problem is equivalent to estimating the selectivity of a selfjoin query in database systems when one can sample rows randomly. We also study the special case when {xi} is the degree sequence of a graph, which corresponds to counting the number of pstars in a graph when one has the ability to sample edges randomly. Our algorithm for a (1±ε)multiplicative approximation of Sp has query and time complexities O(mloglognϵ2S1/pp).more »Here, m=∑xi/2 is the number of edges in the graph, or equivalently, half the number of records in the database table. Similarly, n 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 {xi} 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 Sp≤n, and p=2, our upper bound is O~(n/S1/2p), in contrast to their Ω(n/S1/3p) 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 indegree and outdegree 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.« less