User loick - MathOverflow

Equivalence constante between factorization norm and trace norm

2011-07-29T18:49:34Z

The factorization norm, sometimes also called $\gamma_2$ norm play an important role in (quantum) communication complexity and is defined for a $n\times n$ matrix $A$ by:

$\gamma_2(A) = \max || A \circ uv^t||_{\mathrm{tr}}$ where the maximization runs over all unit vectors $u$ and $v$ ($||u||=||v||=1$)

We can find many equivalent definitions such as: $\gamma_2(A) = \min \lambda$ such that $(A)_{ij} = \langle u_i | v_j\rangle$ and $\forall i,j$ we have $ ||u_i||\leq \lambda$ and $||v_j|| \leq \lambda$.

And the trace norm is defined by $||A||_{\mathrm{tr}}=\mathrm{tr}\sqrt{A^\dagger A}$.

These two norms are equivalent, so there exists a constant $C_n$ such that $||A||_{\mathrm{tr}} \geq C_n\gamma_2(A)$. What is the value of $C_n$?

Having played with a few examples I conjecture that $C_n=1$. Also note that the reverse inequality can be easily obtained: $||A||_\mathrm{tr} \leq n\cdot \gamma_2(a)$.

In particular, I am interested by the case where $A$ is definite positive. In this case the trace norm is simply the trace of $A$, and I can prove that $\gamma_2(A) \geq \sqrt{tr(A)}$.

Answer by Loick for Is there a two-party multiplicative and additive secret sharing scheme ?

2010-07-30T02:44:29Z

Unconditionnaly secure 2-party computation does not exist (unfortunately). This is derived from the impossibility of Oblivious Transfer. Also note that unconditionnaly secure OT is also impossible if the 2 parties are quantum.

Association scheme on injective functions

2010-07-22T20:15:27Z

This problem arises while studying the complexity of algorithms and I am quite unfamiliar with the subject.

Consider the set F of injective functions from {1..N} to {1..M}

we can define an association scheme on F x F by (f,f') and (g,g') are in the same class if there is a permutation $\pi\in S_M$ and a permutation $\tau \in S_N$ such that $g = \pi \circ f \circ \tau$ and $g' = \pi \circ f' \circ \tau$.

I checked that this really defines an association scheme. In a way it is an "ordered" version of the Johnson scheme. It seems to me that it is a natural extension of the Johnson scheme, but I did not find any reference about it.

Q1: Has this association scheme ever been studied? What is its name?

Q2: Can this scheme be obtained by a combination (tensor product? suprema?) of the Johnson scheme and another quantity?

More precisely, I am interested in the "Bose-Mesner Algebra" point of view on this scheme. It is known that all the matrices in the algebra defined by this association scheme diagonalize in the same basis.

Q3: How can we construct/characterize these eigenspaces?

Some background on Association Schemes.

An association scheme is a set of symmetric boolean matrices $A_1, \dots , A_S$ such that 1) $\sum_{i=1}^s A_i =J$ the all-one-matrix 2) $A_1 = I$ the identity matrix 3) $\forall i,j \; A_iA_j \in {\rm span} ( A_i )$

The matrices $A_i$ can be seen as adjency matrix for some graph (but I don't think it might help here)

The span{$A_i$} defines an algebra called the Bose-Mesner Algebra. Condition (3) implies that all matrices commute so they diagonalize in the same basis.

In the case I'm considering here, the dimension of the $A_i$ is ${M \choose N}N!\times {M \choose N}N!$. The $A_i$ are not explicitly defined but we know that $[A_i]_{fg}=[A_i]_{f'g'}$ if there is a permutation $\pi\in S_M$ and a permutation $\tau \in S_N$ such that $g = \pi \circ f \circ \tau$ and $g' = \pi \circ f' \circ \tau$.

About the Johnson scheme: The $A_i$ have size ${M \choose N}$. The rows and the columns of the matrices are labeled by subsets of size $N$ of {$1,\dots,M$}. (in my case, the labels are injective functions, ie. ordered sets of subsets of size $N$ of {$1,\dots,M$}.

$[A_i]_{ab}=[A_i]_{a'b'}$ if there is a permutation $\pi\in S_M$ such that $\pi(a) = a'$ and $\pi(b) = b'$. (where $\pi(a)$ denotes the subset of {$1,\dots,M$} obtained by applying the permutation $\pi$ to the elements of the sets $a$.

Factors of p-1 when p is prime.

2010-06-08T19:38:02Z

Hi,

I have no idea where to look for, so I'm hoping you can give me some pointers.

I'm interested by numbers of form $p-1$ when $p$ is a prime number. Do they have a name, so that I can google them?

More precisely, I'm interested in their factors. Ok, obviously 2 is a factor, but what about the others? Are there a lot of small factors? Do we know the rate of the growth of its larger factor, is it linear, logarithmic?

Thanks.

Comment by Loick

2011-07-29T20:20:38Z

And this solves the general case.

Comment by Loick

2011-07-29T20:16:37Z

Oh yes, you are totally right. I miss it somewhere. This solve the case for positive matrices.

Comment by Loick

2011-07-29T19:51:41Z

I'm not sure to understand what you mean.

Comment by Loick

2010-08-10T19:19:25Z

Let be clear: proving P $\neq$ NP will not have a direct impact on quantum complexity: showing that there is no NP-complete problem in BQP and that BQP $\neq$ QMA will still be open. There is no reason that a proof that P $\neq$ NP will "quantized". Though it might give some insights on the path to follow.

Comment by Loick

2010-08-04T16:21:32Z

The place to ask is math.stackexchange.com

Comment by Loick

2010-08-04T15:46:09Z

I do not know much about classical cryptography. The sketch of the proof I know: classical OT is not unconditionally secure because quantum OT is not. Quantum OT is equivalent to Quantum Bit-Commitment. Quantum Bit-Commitment is not unconditionally secure (First proof by Mayers [PRL 78, 3414] and Lo and Chau [PRL 78, 3410]. Most complete paper by d'Ariano et al.[arxiv 0905.3801]) Please note that classical OT and classical bit-commitment are NOT equivalent, bit-commitment is a weaker primitive. I guess there are direct proofs of these no-go result without going through all these reductions)

Comment by Loick

2010-08-02T14:45:23Z

Is B also positive?

Comment by Loick

2010-07-22T21:40:51Z

Greg, it's in beta. area51.stackexchange.com/proposals/3355/…

Comment by Loick

2010-07-22T21:39:23Z

2/3. You have twice the chance oh having the card with both white sides than the other one. This is the same that another famous riddle. the probability of a couple to have a son is 1/2. Alice and Bob have 2 kids, one of them is a girl. What is the probability that the other kid is also a girl?

Comment by Loick

2010-07-22T20:44:32Z

2d question: If $n!=x$ (you are promised that a preimage of x exists) and you do not care about the running time, the greedy method (divide x by 2, then 3, then 4, etc.) will give you an exact answer. Otherwise your question is about inverting the Gamma function. Or maybe I did not get your question.