80 citations · 174 across the 31 of their papers we have counts for
6 papers · 1 filter
Approximate Trace Reconstruction
Sami Davies, Miklos Z. Racz, Cyrus Rashtchian +1
In the usual trace reconstruction problem, the goal is to exactly reconstruct an unknown string of length after it passes through a deletion channel many times independently, p…
Batch Optimization for DNA Synthesis
Konstantin Makarychev, Miklos Z. Racz, Cyrus Rashtchian +1
Large pools of synthetic DNA molecules have been recently used to reliably store significant volumes of digital data. While DNA as a storage medium has enormous potential because o…
Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems
Cyrus Rashtchian, David P. Woodruff, Hanlin Zhu
We consider the general problem of learning about a matrix through vector-matrix-vector queries. These queries provide the value of $\boldsymbol{u}^{\mathrm{T}}\boldsymbol{M}\bolds…
LSF-Join: Locality Sensitive Filtering for Distributed All-Pairs Set Similarity Under Skew
Cyrus Rashtchian, Aneesh Sharma, David P. Woodruff
All-pairs set similarity is a widely used data mining task, even for large and high-dimensional datasets. Traditionally, similarity search has focused on discovering very similar p…
Edge Estimation with Independent Set Oracles
Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy +2
We study the task of estimating the number of edges in a graph with access to only an independent set oracle. Independent set queries draw motivation from group testing and have ap…
Massively-Parallel Similarity Join, Edge-Isoperimetry, and Distance Correlations on the Hypercube
Paul Beame, Cyrus Rashtchian
We study distributed protocols for finding all pairs of similar vectors in a large dataset. Our results pertain to a variety of discrete metrics, and we give concrete instantiation…