38 citations · 53 across the 13 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2017
Simulation Theorems via Pseudorandom Properties
Arkadev Chattopadhyay, Michal Koucký, Bruno Loff +1
We generalize the deterministic simulation theorem of Raz and McKenzie [RM99], to any gadget which satisfies certain hitting property. We prove that inner-product and gap-Hamming s…
cs.CC2016★ 2 cited
Tribes Is Hard in the Message Passing Model
Arkadev Chattopadhyay, Sagnik Mukhopadhyay
We consider the point-to-point message passing model of communication in which there are processors with individual private inputs, each -bit long. Each processor is located…
cs.CC2015★ 1 cited
Towards Better Separation between Deterministic and Randomized Query Complexity
Sagnik Mukhopadhyay, Swagato Sanyal
We show that there exists a Boolean function which observes the following separations among deterministic query complexity , randomized zero error query complexity $(R_…