23 citations · 97 across the 13 of their papers we have counts for
Showing 2015Show all
3 papers · 1 filter
cs.DS2015
Set Membership with a Few Bit Probes
Mohit Garg, Jaikumar Radhakrishnan
We consider the bit-probe complexity of the set membership problem, where a set S of size at most n from a universe of size m is to be represented as a short bit vector in order to…
cs.CC2015
A Sampling Technique of Proving Lower Bounds for Noisy Computations
Chinmoy Dutta, Jaikumar Radhakrishnan
We present a technique of proving lower bounds for noisy computations. This is achieved by a theorem connecting computations on a kind of randomized decision trees and sampling bas…
cs.DC2015★ 1 cited
How Hard is Computing Parity with Noisy Communications?
Chinmoy Dutta, Yashodhan Kanoria, D. Manjunath +1
We show a tight lower bound of on the number of transmissions required to compute the parity of input bits with constant error in a noisy communication networ…