Alain Tapp

ICML Conference 2019 Conference Paper

Fairwashing: the risk of rationalization

• Ulrich Aïvodji
• Hiromi Arai
• Olivier Fortineau
• Sébastien Gambs
• Satoshi Hara 0001
• Alain Tapp

Black-box explanation is the problem of explaining how a machine learning model – whose internal logic is hidden to the auditor and generally complex – produces its outcomes. Current approaches for solving this problem include model explanation, outcome explanation as well as model inspection. While these techniques can be beneficial by providing interpretability, they can be used in a negative manner to perform fairwashing, which we define as promoting the false perception that a machine learning model respects some ethical values. In particular, we demonstrate that it is possible to systematically rationalize decisions taken by an unfair black-box model using the model explanation as well as the outcome explanation approaches with a given fairness metric. Our solution, LaundryML, is based on a regularized rule list enumeration algorithm whose objective is to search for fair rule lists approximating an unfair black-box model. We empirically evaluate our rationalization technique on black-box models trained on real-world datasets and show that one can obtain rule lists with high fidelity to the black-box model while being considerably less unfair at the same time.

FOCS Conference 2014 Conference Paper

Noisy Interactive Quantum Communication

• Gilles Brassard
• Ashwin Nayak 0001
• Alain Tapp
• Dave Touchette
• Falk Unger

We study the problem of simulating protocols in a quantum communication setting over noisy channels. This problem falls at the intersection of quantum information theory and quantum communication complexity, and will be of importance for eventual real-world applications of interactive quantum protocols, which can be proved to have exponentially lower communication costs than their classical counterparts for some problems. These are the first results concerning the quantum version of this problem, originally studied by Schulman in a classical setting (FOCS '92, STOC '93). We simulate a length N quantum communication protocol by a length O(N) protocol with arbitrarily small error. Our simulation strategy has a far higher communication rate than a naive one that encodes separately each particular round of communication to achieve comparable success. Such a strategy would have a communication rate going to 0 in the worst interaction case as the length of the protocols increases, in contrast to our strategy, which has a communication rate proportional to the capacity of the channel used. Under adversarial noise, our strategy can withstand, for arbitrarily small ε > 0, error rates as high as 1/2 -- ε when parties preshare perfect entanglement, but the classical channel is noisy. We show that this is optimal. Note that in this model, the naive strategy would not work for any constant fraction of errors. We provide extension of these results in several other models of communication, including when also the entanglement is noisy, and when there is no pre-shared entanglement but communication is quantum and noisy. We also study the case of random noise, for which we provide simulation protocols with positive communication rates and no pre-shared entanglement over some quantum channels with quantum capacity Q = 0, proving that Q is in general not the right characterization of a channel's capacity for interactive quantum communication. Our results are stated for a general quantum communication protocol in which Alice and Bob collaborate, and hold in particular in the quantum communication complexity settings of the Yao and Cleve-Buhrman models.

TCS Journal 2013 Journal Article

Deterministic quantum non-locality and graph colorings

• Viktor Galliard
• Alain Tapp
• Stefan Wolf

One of the most fascinating consequences of quantum theory are non-local correlations: Two–possibly distant–parts of a system can have a behavior under measurements unexplainable by shared information. A manifestation thereof is so-called pseudo-telepathy: Tasks that can be performed by two parties who share a quantum state, whereas classically, communication would be necessary to always succeed. We show that pseudo-telepathy games can often be modeled by graphs: The classical strategy to win the game is a coloring of this graph with a given number of colors. We discuss these parallels and study the class of graphs corresponding to the first two-party pseudo-telepathy game, proposed by Brassard, Cleve, and Tapp in 1999. This leads to a proof that the game indeed has the desired property.

TCS Journal 2013 Journal Article

Preface

• Tal Mor
• Alain Tapp

TCS Journal 2013 Journal Article

Quantum entanglement and the communication complexity of the inner product function

• Richard Cleve
• Wim van Dam
• Michael Nielsen
• Alain Tapp

We consider the communication complexity of the binary inner product function in a variation of the two-party scenario where the parties have an a priori supply of particles in an entangled quantum state. We prove linear lower bounds for both exact protocols, as well as for protocols that determine the answer with bounded-error probability. Our proofs employ a novel kind of “quantum” reduction from a quantum information theory problem to the problem of computing the inner product. The communication required for the former problem can then be bounded by an application of Holevo’s theorem. We also give a specific example of a probabilistic scenario where entanglement reduces the communication complexity of the inner product function by one bit.

FOCS Conference 2002 Conference Paper

Authentication of Quantum Messages

• Howard Barnum
• Claude Crépeau
• Daniel Gottesman
• Adam Smith 0006
• Alain Tapp

Authentication is a well-studied area of classical cryptography: a sender A and a receiver B sharing a classical secret key want to exchange a classical message with the guarantee that the message has not been modified or replaced by a dishonest party with control of the communication line. In this paper we study the authentication of messages composed of quantum states. We give a formal definition of authentication in the quantum setting. Assuming A and B have access to an insecure quantum channel and share a secret, classical random key, we provide a non-interactive scheme that enables A to both encrypt and authenticate an m qubit message by encoding it into m+s qubits, where the error probability decreases exponentially in the security parameter s. The scheme requires a secret key of size 2m+O(s). To achieve this, we give a highly efficient protocol for testing the purity of shared EPR pairs. It has long been known that learning information about a general quantum state will necessarily disturb it. We refine this result to show that such a disturbance can be done with few side effects, allowing it to circumvent cryptographic protections. Consequently, any scheme to authenticate quantum messages must also encrypt them. In contrast, no such constraint exists classically. This reasoning has two important consequences: It allows us to give a lower bound of 2m key bits for authenticating m qubits, which makes our protocol asymptotically optimal. Moreover, we use it to show that digitally signing quantum states is impossible.

FOCS Conference 2000 Conference Paper

Private Quantum Channels

• Andris Ambainis
• Michele Mosca
• Alain Tapp
• Ronald de Wolf

We investigate how a classical private key can be used by two players, connected by an insecure one-way quantum channel, to perform private communication of quantum information. In particular, we show that in order to transmit n qubits privately, 2n bits of shared private key are necessary and sufficient. This result may be viewed as the quantum analogue of the classical one-time pad encryption scheme.