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

IEEE International Symposium on Information Theory (ISIT)

Improved Bounds On Interactive Communication

Moni Naor, Alon Orlitsky

Published Aug 24, 2005• 0 citations
Publisher
DOI
10.1109/isit.1991.695270

Related papers

Indirect measurement for optimal quantum communication enhanced by binary non-standard coherent states

Min Namkung, Jeong San Kim

It is well known that the Helstrom bound can be improved by generalizing the form of a coherent state. Thus, designing a quantum measurement achieving the improved Helstrom bound is important for novel quantum communication. In this paper, we analytically show that the improved Helstrom bound can be achieved by a projective measurement composed of orthogonal non-standard Schrödinger cat states. Moreover, we numerically show that the improved Helstrom bound can be nearly achieved by an indirect measurement based on the Jaynes–Cummings model. As the Jaynes–Cummings model describes an interaction between a light and a two-level atom, we emphasize that the indirect measurement considered in this paper has potential to be experimentally implemented.

arXiv:2112.02312•Journal of the Optical Society of America B•Feb 28, 2022•2 citations

Upper Bounds on Communication in Terms of Approximate Rank

Anna Gál, Ridwan Syed

Lecture notes in computer science•Jan 1, 2021•5 citations

Towards Optimal Non-interactive Secure Multiparty Computation for Abelian Programs

Maki Yoshida

Non-interactive secure multiparty computation is a method to share and compute a private function$f$among$n$parties holding private inputs xi with 1$n$in the information theoretical setting. Each party locally computes a message from a share of$f$and send it to a referee in parallel. The referee obtains the output f (xi,… , xn) while keeping$f$and xi private other than what can be inferred from the output. The communication complexity is evaluated by the maximum length of shares and messages. In the previous work, several kinds of function families, upper and lower bounds have been improved and the only gaps remaining are for the group products and the Abelian programs (including symmetric functions). This paper improves the communication complexity of both function families towards the optimum by deriving a new lower bound for the group products that matches the previous upper bound (up to a constant factor) and the first asymptotically optimal upper bound for the Abelian programs.

IEEE International Symposium on Information Theory (ISIT)•Jul 7, 2024•1 citation

Upper Bounds on Communication in Terms of Approximate Rank

Anna Gál, Ridwan Syed

Theory of Computing Systems•Dec 12, 2023•3 citations

New bounds on the information-theoretic key agreement of multiple terminals

Amin Gohari, Venkat Anantharam

We study the problem of information-theoretically secure secret key agreement under the well-known source model and channel model. In both of these models the parties wish to create a shared secret key that is secure from an eavesdropper with unlimited computational resources. In the channel model, the first party can choose a sequence of inputs to a discrete memoryless channel, which has outputs at the other parties and at the eavesdropper. After each channel use, the parties can engage in arbitrarily many rounds of interactive authenticated communication over a public channel. At the end, each party should be able to generate the key. In the source model, the parties wishing to generate a secret key (as well as the eavesdropper) receive a certain number of independent identically distributed copies of jointly distributed random variables after which the parties are allowed interactive authenticated public communication, at the end of which each party should be able to generate the key. We derive new lower and upper bounds on the secret key rate under the source model and the channel model, and introduce a technique for proving that a given expression bounds the secrecy rate from above in the channel model. Our lower bounds strictly improve what is essentially the best known lower bound in both the source model and the channel model. Our upper bound in the channel model strictly improves the current state of art upper bound. We do not know whether our new upper bound in the source model represents an strict improvement but it includes the current best known bound as a special case.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2008•13 citations

Tight Bounds on the Randomized Communication Complexity of Vector-in-Subspace

Chengu Wang

We prove that the randomized communication complexity of Vector-in-Subspace in $\mathbb R^n$ with error at most $1/3$ is $Θ(\sqrt n)$. Alice holds a unit vector $u$ and Bob holds an $n/2$-dimensional subspace $H$; they must distinguish $u\in H$ from $u\in H^\perp$. An exact one-way quantum protocol uses $O(\log n)$ qubits, making the problem a geometric example of an exponential quantum advantage over interactive classical communication. Our lower bound matches Raz's $O(\sqrt n)$ upper bound, improves the $Ω(n^{1/3})$ lower bound of Klartag and Regev, and removes the total-rank restriction in Grupel's $Ω(\sqrt n)$ result. The proof establishes a Gaussian moment bound over complete rectangle partitions. A complex Gaussian representation yields a vanishing even moment whose cancellation is preserved when averaging over the partition. We control the signed conditional moments around a real center by decomposing conditional Gaussian measures into fixed coordinates and sub-Gaussian components. Combining this estimate with spherical harmonic analysis gives the communication lower bound.

cs.CCCross-listedarXiv:2610.30052•Oct 22, 2026•0 citations
It is well known that the Helstrom bound can be improved by generalizing the form of a coherent state. Thus, designing a quantum measurement achieving the improved Helstrom bound is important for novel quantum communication. In this paper, we analytically show that the improved Helstrom bound can be achieved by a projective measurement composed of orthogonal non-standard Schrödinger cat states. Moreover, we numerically show that the improved Helstrom bound can be nearly achieved by an indirect measurement based on the Jaynes–Cummings model. As the Jaynes–Cummings model describes an interaction between a light and a two-level atom, we emphasize that the indirect measurement considered in this paper has potential to be experimentally implemented.
Non-interactive secure multiparty computation is a method to share and compute a private functionfffamongnnnparties holding private inputs xi with 1nnnin the information theoretical setting. Each party locally computes a message from a share offffand send it to a referee in parallel. The referee obtains the output f (xi,… , xn) while keepingfffand xi private other than what can be inferred from the output. The communication complexity is evaluated by the maximum length of shares and messages. In the previous work, several kinds of function families, upper and lower bounds have been improved and the only gaps remaining are for the group products and the Abelian programs (including symmetric functions). This paper improves the communication complexity of both function families towards the optimum by deriving a new lower bound for the group products that matches the previous upper bound (up to a constant factor) and the first asymptotically optimal upper bound for the Abelian programs.
We study the problem of information-theoretically secure secret key agreement under the well-known source model and channel model. In both of these models the parties wish to create a shared secret key that is secure from an eavesdropper with unlimited computational resources. In the channel model, the first party can choose a sequence of inputs to a discrete memoryless channel, which has outputs at the other parties and at the eavesdropper. After each channel use, the parties can engage in arbitrarily many rounds of interactive authenticated communication over a public channel. At the end, each party should be able to generate the key. In the source model, the parties wishing to generate a secret key (as well as the eavesdropper) receive a certain number of independent identically distributed copies of jointly distributed random variables after which the parties are allowed interactive authenticated public communication, at the end of which each party should be able to generate the key. We derive new lower and upper bounds on the secret key rate under the source model and the channel model, and introduce a technique for proving that a given expression bounds the secrecy rate from above in the channel model. Our lower bounds strictly improve what is essentially the best known lower bound in both the source model and the channel model. Our upper bound in the channel model strictly improves the current state of art upper bound. We do not know whether our new upper bound in the source model represents an strict improvement but it includes the current best known bound as a special case.
We prove that the randomized communication complexity of Vector-in-Subspace in Rn\mathbb R^nRn with error at most 1/31/31/3 is Θ(n)Θ(\sqrt n)Θ(n​). Alice holds a unit vector uuu and Bob holds an n/2n/2n/2-dimensional subspace HHH; they must distinguish u∈Hu\in Hu∈H from u∈H⊥u\in H^\perpu∈H⊥. An exact one-way quantum protocol uses O(log⁡n)O(\log n)O(logn) qubits, making the problem a geometric example of an exponential quantum advantage over interactive classical communication. Our lower bound matches Raz's O(n)O(\sqrt n)O(n​) upper bound, improves the Ω(n1/3)Ω(n^{1/3})Ω(n1/3) lower bound of Klartag and Regev, and removes the total-rank restriction in Grupel's Ω(n)Ω(\sqrt n)Ω(n​) result. The proof establishes a Gaussian moment bound over complete rectangle partitions. A complex Gaussian representation yields a vanishing even moment whose cancellation is preserved when averaging over the partition. We control the signed conditional moments around a real center by decomposing conditional Gaussian measures into fixed coordinates and sub-Gaussian components. Combining this estimate with spherical harmonic analysis gives the communication lower bound.