516 citations · 2.7k across the 47 of their papers we have counts for
Showing 2012 · cs.CCShow all
2 papers · 2 filters
cs.CC2012
Optimal Hitting Sets for Combinatorial Shapes
Aditya Bhaskara, Devendra Desai, Srikanth Srinivasan
We consider the problem of constructing explicit Hitting sets for Combinatorial Shapes, a class of statistical tests first studied by Gopalan, Meka, Reingold, and Zuckerman (STOC 2…
cs.CC2012
Streaming algorithms for recognizing nearly well-parenthesized expressions
Andreas Krebs, Nutan Limaye, Srikanth Srinivasan
We study the streaming complexity of the membership problem of 1-turn-Dyck2 and Dyck2 when there are a few errors in the input string. 1-turn-Dyck2 with errors: We prove that there…