80 citations · 174 across the 31 of their papers we have counts for
4 papers · 1 filter
Average-Case Communication Complexity of Statistical Problems
Cyrus Rashtchian, David P. Woodruff, Peng Ye +1
We study statistical problems, such as planted clique, its variants, and sparse principal component analysis in the context of average-case communication complexity. Our motivation…
Trace Reconstruction Problems in Computational Biology
Vinnu Bhardwaj, Pavel A. Pevzner, Cyrus Rashtchian +1
The problem of reconstructing a string from its error-prone copies, the trace reconstruction problem, was introduced by Vladimir Levenshtein two decades ago. While there has been c…
Equivalence of Systematic Linear Data Structures and Matrix Rigidity
Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian
Recently, Dvir, Golovnev, and Weinstein have shown that sufficiently strong lower bounds for linear data structures would imply new bounds for rigid matrices. However, their result…
Reconstructing Trees from Traces
Sami Davies, Miklos Z. Racz, Cyrus Rashtchian
We study the problem of learning a node-labeled tree given independent traces from an appropriately defined deletion channel. This problem, tree trace reconstruction, generalizes s…