36 citations · 176 across the 38 of their papers we have counts for
4 papers · 1 filter
A Chasm Between Identity and Equivalence Testing with Conditional Queries
Jayadev Acharya, Clément L. Canonne, Gautam Kamath
A recent model for property testing of probability distributions (Chakraborty et al., ITCS 2013, Canonne et al., SICOMP 2015) enables tremendous savings in the sample complexity of…
Communication with Imperfectly Shared Randomness
Clément L. Canonne, Venkatesan Guruswami, Raghu Meka +1
The communication complexity of many fundamental problems reduces greatly when the communicating parties share randomness that is independent of the inputs to the communication tas…
Learning circuits with few negations
Eric Blais, Clément L. Canonne, Igor C. Oliveira +2
Monotone Boolean functions, and the monotone Boolean circuits that compute them, have been intensively studied in complexity theory. In this paper we study the structure of Boolean…
Testing probability distributions underlying aggregated data
Clément Canonne, Ronitt Rubinfeld
In this paper, we analyze and study a hybrid model for testing and learning probability distributions. Here, in addition to samples, the testing algorithm is provided with one of t…