78 citations · 335 across the 44 of their papers we have counts for
Showing 2016 · cs.CCShow all
2 papers · 2 filters
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
Quantum automata cannot detect biased coins, even in the limit
Guy Kindler, Ryan O`Donnell
Aaronson and Drucker (2011) asked whether there exists a quantum finite automaton that can distinguish fair coin tosses from biased ones by spending significantly more time in acce…