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

Lecture notes in computer science

Public vs Private Coin in Bounded-Round Information

Mark Braverman, Ankit Garg

Published Jan 1, 2014• 55 citations
Publisher
DOI
10.1007/978-3-662-43948-7_42

Related papers

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

Alexander Kozachinsky

Electronic colloquium on computational complexity•Jan 1, 2014•2 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

Distributed Property Testing with (Quantum) Carrier Pigeons: Tight Bounds on State Certification

Kenny Chen

Recently, Doosti et al. introduced the problem of distributed quantum state verification, where $m$ distributed nodes are given a copy of an unknown state $ρ$, and can send limited one way communication to a central node, who has a complete description of a known state $σ$. They ask how many distributed nodes $m$ are required, before the central node can succeed at distinguishing whether $ρ=σ$ or $\|ρ-σ\|_1\geq\varepsilon$ with high probability. In the setting where only quantum communication is allowed, Doosti et al. exhibit conditional lower bounds in both the public and private-coin settings, and a matching upper bound in the public-coin setting. We extend these results, and show unconditional lower bounds for when both classical and quantum communication are permitted. We show the public-coin lower bound is tight by giving an algorithm with a matching upper bound. We also show an almost tight upper bound in the private-coin setting when only quantum communication is permitted.

quant-pharXiv:2606.31753•Jul 1, 2026•1 citation

Precise Bounded-Concurrent Zero-Knowledge in Almost Constant Rounds

Ning Ding, Dawu Gu, Bart Preneel

Precise concurrent zero-knowledge is a new notion introduced by Pandey et al. in Eurocrypt'08, which captures the idea that the view of any verifier in concurrent interaction can be reconstructed in almost the same time. They also constructed some (private-coin) concurrent zero-knowledge argument systems for NP which achieve precision in different levels and all these protocols use at least ω (log n) rounds. In this paper we investigate the feasibility of reducing the round complexity and still keeping precision simultaneously. Our main result is that we construct a public-coin precise bounded-concurrent zero-knowledge argument system for NP only using almost constant rounds, i.e., ω (1) rounds. Bounded-concurrency means an a-priori bound on the (polynomial) number of concurrent sessions is specified before the protocol is constructed. Our result doesn't need any setup assumption.

網際網路技術學刊•Jul 1, 2011•0 citations

The Limits of Common Coins: Further Results

Hemanta K. Maji, Manoj Prabhakaran

Lecture notes in computer science•Jan 1, 2011•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.
Recently, Doosti et al. introduced the problem of distributed quantum state verification, where mmm distributed nodes are given a copy of an unknown state ρρρ, and can send limited one way communication to a central node, who has a complete description of a known state σσσ. They ask how many distributed nodes mmm are required, before the central node can succeed at distinguishing whether ρ=σρ=σρ=σ or ∥ρ−σ∥1≥ε\|ρ-σ\|_1\geq\varepsilon∥ρ−σ∥1​≥ε with high probability. In the setting where only quantum communication is allowed, Doosti et al. exhibit conditional lower bounds in both the public and private-coin settings, and a matching upper bound in the public-coin setting. We extend these results, and show unconditional lower bounds for when both classical and quantum communication are permitted. We show the public-coin lower bound is tight by giving an algorithm with a matching upper bound. We also show an almost tight upper bound in the private-coin setting when only quantum communication is permitted.
Precise concurrent zero-knowledge is a new notion introduced by Pandey et al. in Eurocrypt'08, which captures the idea that the view of any verifier in concurrent interaction can be reconstructed in almost the same time. They also constructed some (private-coin) concurrent zero-knowledge argument systems for NP which achieve precision in different levels and all these protocols use at least ω (log n) rounds. In this paper we investigate the feasibility of reducing the round complexity and still keeping precision simultaneously. Our main result is that we construct a public-coin precise bounded-concurrent zero-knowledge argument system for NP only using almost constant rounds, i.e., ω (1) rounds. Bounded-concurrency means an a-priori bound on the (polynomial) number of concurrent sessions is specified before the protocol is constructed. Our result doesn't need any setup assumption.