Sublinear algorithms for massive data problems by Mahabadi, Sepideh

Get full text

Sublinear algorithms for Earth Mover's Distance by Do Ba, Khanh

Get full text

Sublinear Algorithms for Approximating String Compressibility by Raskhodnikova, Sofya, Ron, Dana, Rubinfeld, Ronitt, Smith, Adam

“…We study this question in detail for two popular lossless compression schemes: run-length encoding (RLE) and a variant of Lempel-Ziv (LZ77), and present sublinear algorithms for approximating compressibility with respect to both schemes. …”
Get full text
Get full text

New directions in sublinear algorithms and testing properties of distributions by Gouleakis, Themistoklis

Get full text

An average-case sublinear forward algorithm for the haploid Li and Stephens model by Yohei M. Rosen, Benedict J. Paten

Subjects: Get full text

Communication Locality in Secure Multi-party Computation by Boyle, Elette Chantae, Goldwasser, Shafrira, Tessaro, Stefano

“…We then focus on the particularly interesting setting in which the function to be computed is a sublinear algorithm: An evaluation of f depends on the inputs of at most q = o(n) of the parties, where the identity of these parties can be chosen randomly and possibly adaptively. …”
Get full text

A near-Optimal Sublinear-Time Algorithm for Approximating the Minimum Vertex Cover Size by Onak, Krzysztof, Ron, Dana, Rosen, Michal, Rubinfeld, Ronitt

“…The best previously known sublinear algorithm, of Yoshida et al. (STOC 2009), has query complexity and running time O(d[superscript 4]/ε[superscript 2]), where d is the maximum degree in the graph. …”
Get full text
Get full text

Secure multi-party protocols under a modern lens by Boyle, Elette Chantae

Get full text

Learning noisy characters, multiplication codes, and cryptographic hardcore predicates by Akavia, Adi

Get full text

Dynamic Approximate Vertex Cover and Maximum Matching by Onak, Krzysztof, Rubinfeld, Ronitt

“…This leads us to wonder whether there are other connections between sublinear algorithms and dynamic data structures.…”
Get full text
Get full text

Space-Efficient Local Computation Algorithms by Alon, Noga, Rubinfeld, Ronitt, Vardi, Shai, Xie, Ning

“…(ICS 2011, pp. 223--238) proposed a new model of sublinear algorithms called local computation algorithms. …”
Get full text
Get full text

Testing Closeness of Discrete Distributions by Batu, Tugkan, Fortnow, Lance, Rubinfeld, Ronitt, Smith, Warren D., White, Patrick

“…Our algorithm has applications to the problem of testing whether a given Markov process is rapidly mixing. We present sublinear algorithms for several variants of this problem as well.…”
Get full text
Get full text

Efficient Algorithms for Vector Similarities by Silwal, Sandeep B.

“…Overall, the main message of this thesis is that sublinear algorithms design principles are instrumental in designing scalable algorithms for big data.…”
Get full text

New sublinear methods in the struggle against classical problems by Onak, Krzysztof (Krzysztof Piotr)

Get full text