72 citations · 399 across the 60 of their papers we have counts for
Showing 2016Show all
2 papers · 1 filter
cs.CC2016★ 2 cited
Optimal mean-based algorithms for trace reconstruction
Anindya De, Ryan O'Donnell, Rocco Servedio
In the (deletion-channel) trace reconstruction problem, there is an unknown -bit source string . An algorithm is given access to independent traces of , where a trace is f…
cs.CC2016★ 5 cited
Degree and Sensitivity: tails of two distributions
Parikshit Gopalan, Rocco Servedio, Avishay Tal +1
The sensitivity of a Boolean function f is the maximum over all inputs x, of the number of sensitive coordinates of x. The well-known sensitivity conjecture of Nisan (see also Nisa…