Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Electronic colloquium on computational complexity

On the role of private coins in unbounded-round Information Complexity.

Alexander Kozachinsky

Published Jan 1, 2014• 2 citations
OpenAlex

Related papers

Public vs Private Coin in Bounded-Round Information

Mark Braverman, Ankit Garg

Lecture notes in computer science•Jan 1, 2014•55 citations

A Direct Product Theorem for Two-Party Bounded-Round Public-Coin Communication Complexity

Rahul Jain, Attila Pereszlényi, Penghui Yao

Algorithmica•Dec 18, 2015•10 citations

The information cost of quantum memoryless protocols

André Chailloux, Iordanis Kerenidis, Mathieu Laurière

We consider memoryless quantum communication protocols, where the two parties do not possess any memory besides their classical input and they take turns performing unitary operations on a pure quantum state that they exchange between them. Most known quantum protocols are of this type and recently a deep connection between memoryless protocols and Bell inequality violations has been explored recently by Buhrman et al. We study the information cost of memoryless quantum protocols by looking at a canonical problem: bounded-round quantum communication protocols for the one-bit AND function. We prove directly a tight lower bound of $Θ(\log(k) / k)$ for the information cost of AND for $k$-round memoryless quantum protocols and for the input distribution needed for the Disjointness function. It is not clear if memoryless protocols allow for a reduction between AND and Disjointness, due to the absence of private workspaces. We enhance the model by allowing the players to keep in their private classical workspace apart from their input also some classical private coins. Surprisingly, we show that every quantum protocol can be transformed into an equivalent quantum protocol with private coins that is perfectly private, i.e. the players only learn the value of the function and nothing more. Last, we consider the model where the players are allowed to use one-shot coins, i.e. private coins that can be used only once during the protocol. While in the classical case, private coins and one-shot coins are equivalent, in the quantum case, we prove that they are not. More precisely, we show that every quantum memoryless protocol with one-bit inputs that uses one-shot coins can be transformed into a memoryless quantum protocol without private coins and without increasing too much its information cost. Hence, while private coins always allow for private quantum protocols, one-shot coins do not.

arXiv:1703.01061•Mar 3, 2017•4 citations

Cryptography in an Unbounded Computational Model

David Paul Woodruff, Marten van Dijk

Lecture notes in computer science•Jan 1, 2002•3 citations

A Randomness-Rounds Tradeoff in Private Computation

Eyal Kushilevitz, Adi Rosén

Springer eBooks•Aug 9, 2007•22 citations

An Unbiased Global Coin Flipping Protocol on Synchronous Distributed Systems

Kunikazu Yoda, 寿男 岡部, 正憲 金澤

We present a distributed protocol for achieving totally unbiased global coin flipping in the presence of an adversary.We consider a synchronous system of $n$ processors at most $t$ of which may be corrupted and manipu- lated by a malicious adversary.We assume a complete network where every two processors are connected via a private channel.Our protocol is deterministic and assumes a very powerful adversary.Although it cannot eavesdrop, it is computationally unbounded, capable of rushing and dynamic.This is the same model that is adopted in Yao's global coin flipping protocol [Yao84], which we use as the base of our pro- tocol.Our protocol tolerates almost $n/3$ processor failures and terminates in $t+4$ rounds.The resilience of our protocol is greatly improved from that of Yao's protocol at the expense of running time, which is only added just two rounds.

数理解析研究所講究録•May 1, 1996•1 citation
We consider memoryless quantum communication protocols, where the two parties do not possess any memory besides their classical input and they take turns performing unitary operations on a pure quantum state that they exchange between them. Most known quantum protocols are of this type and recently a deep connection between memoryless protocols and Bell inequality violations has been explored recently by Buhrman et al. We study the information cost of memoryless quantum protocols by looking at a canonical problem: bounded-round quantum communication protocols for the one-bit AND function. We prove directly a tight lower bound of Θ(log⁡(k)/k)Θ(\log(k) / k)Θ(log(k)/k) for the information cost of AND for kkk-round memoryless quantum protocols and for the input distribution needed for the Disjointness function. It is not clear if memoryless protocols allow for a reduction between AND and Disjointness, due to the absence of private workspaces. We enhance the model by allowing the players to keep in their private classical workspace apart from their input also some classical private coins. Surprisingly, we show that every quantum protocol can be transformed into an equivalent quantum protocol with private coins that is perfectly private, i.e. the players only learn the value of the function and nothing more. Last, we consider the model where the players are allowed to use one-shot coins, i.e. private coins that can be used only once during the protocol. While in the classical case, private coins and one-shot coins are equivalent, in the quantum case, we prove that they are not. More precisely, we show that every quantum memoryless protocol with one-bit inputs that uses one-shot coins can be transformed into a memoryless quantum protocol without private coins and without increasing too much its information cost. Hence, while private coins always allow for private quantum protocols, one-shot coins do not.
We present a distributed protocol for achieving totally unbiased global coin flipping in the presence of an adversary.We consider a synchronous system of nnn processors at most ttt of which may be corrupted and manipu- lated by a malicious adversary.We assume a complete network where every two processors are connected via a private channel.Our protocol is deterministic and assumes a very powerful adversary.Although it cannot eavesdrop, it is computationally unbounded, capable of rushing and dynamic.This is the same model that is adopted in Yao's global coin flipping protocol [Yao84], which we use as the base of our pro- tocol.Our protocol tolerates almost n/3n/3n/3 processor failures and terminates in t+4t+4t+4 rounds.The resilience of our protocol is greatly improved from that of Yao's protocol at the expense of running time, which is only added just two rounds.