User loick - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T03:50:40Z http://mathoverflow.net/feeds/user/6673 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/71600/equivalence-constante-between-factorization-norm-and-trace-norm Equivalence constante between factorization norm and trace norm Loick 2011-07-29T18:49:34Z 2011-07-29T20:20:56Z <p>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:</p> <p>$\gamma_2(A) = \max || A \circ uv^t||_{\mathrm{tr}}$ where the maximization runs over all unit vectors $u$ and $v$ ($||u||=||v||=1$)</p> <p>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$.</p> <p>And the trace norm is defined by $||A||_{\mathrm{tr}}=\mathrm{tr}\sqrt{A^\dagger A}$.</p> <blockquote> <p>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$?</p> </blockquote> <p>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)$.</p> <p>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)}$.</p> http://mathoverflow.net/questions/32801/is-there-a-two-party-multiplicative-and-additive-secret-sharing-scheme/33884#33884 Answer by Loick for Is there a two-party multiplicative and additive secret sharing scheme ? Loick 2010-07-30T02:44:29Z 2010-07-30T02:44:29Z <p>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.</p> http://mathoverflow.net/questions/32999/association-scheme-on-injective-functions Association scheme on injective functions Loick 2010-07-22T20:15:27Z 2010-07-28T12:49:31Z <p>This problem arises while studying the complexity of algorithms and I am quite unfamiliar with the subject.</p> <p>Consider the set F of injective functions from {1..N} to {1..M}</p> <p>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$.</p> <p>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.</p> <blockquote> <p>Q1: Has this association scheme ever been studied? What is its name?</p> <p>Q2: Can this scheme be obtained by a combination (tensor product? suprema?) of the Johnson scheme and another quantity?</p> </blockquote> <p>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.</p> <blockquote> <p>Q3: How can we construct/characterize these eigenspaces? </p> </blockquote> <p>--</p> <p>Some background on Association Schemes.</p> <p>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 )$</p> <p>The matrices $A_i$ can be seen as adjency matrix for some graph (but I don't think it might help here)</p> <p>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.</p> <p>--</p> <p>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$.</p> <p>--</p> <p>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$}.</p> <p>$[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$.</p> http://mathoverflow.net/questions/27508/factors-of-p-1-when-p-is-prime Factors of p-1 when p is prime. Loick 2010-06-08T19:38:02Z 2010-06-10T04:12:23Z <p>Hi,</p> <p>I have no idea where to look for, so I'm hoping you can give me some pointers.</p> <p>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?</p> <p>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?</p> <p>Thanks.</p> http://mathoverflow.net/questions/71600/equivalence-constante-between-factorization-norm-and-trace-norm/71612#71612 Comment by Loick Loick 2011-07-29T20:20:38Z 2011-07-29T20:20:38Z And this solves the general case. http://mathoverflow.net/questions/71600/equivalence-constante-between-factorization-norm-and-trace-norm Comment by Loick Loick 2011-07-29T20:16:37Z 2011-07-29T20:16:37Z Oh yes, you are totally right. I miss it somewhere. This solve the case for positive matrices. http://mathoverflow.net/questions/71600/equivalence-constante-between-factorization-norm-and-trace-norm Comment by Loick Loick 2011-07-29T19:51:41Z 2011-07-29T19:51:41Z I'm not sure to understand what you mean. http://mathoverflow.net/questions/35151/what-impact-would-pnp-have-on-the-characterization-of-bqp Comment by Loick Loick 2010-08-10T19:19:25Z 2010-08-10T19:19:25Z Let be clear: proving P $\neq$ NP will not have a <i>direct</i> 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 &quot;quantized&quot;. Though it might give some insights on the path to follow. http://mathoverflow.net/questions/34524/roulette-probability Comment by Loick Loick 2010-08-04T16:21:32Z 2010-08-04T16:21:32Z The place to ask is <a href="http://math.stackexchange.com/" rel="nofollow">math.stackexchange.com</a> http://mathoverflow.net/questions/32801/is-there-a-two-party-multiplicative-and-additive-secret-sharing-scheme/33884#33884 Comment by Loick Loick 2010-08-04T15:46:09Z 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) http://mathoverflow.net/questions/34252/eigenvalues-of-ab-where-a-is-symmetric-positive-definite-and-b-is-diagonal Comment by Loick Loick 2010-08-02T14:45:23Z 2010-08-02T14:45:23Z Is B also positive? http://mathoverflow.net/questions/33011/what-is-the-probability-the-other-side-is-white Comment by Loick Loick 2010-07-22T21:40:51Z 2010-07-22T21:40:51Z Greg, it's in beta. <a href="http://area51.stackexchange.com/proposals/3355/mathematics" rel="nofollow">area51.stackexchange.com/proposals/3355/&hellip;</a> http://mathoverflow.net/questions/33011/what-is-the-probability-the-other-side-is-white Comment by Loick Loick 2010-07-22T21:39:23Z 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? http://mathoverflow.net/questions/32996/solving-nlognx-and-nx-with-precision Comment by Loick Loick 2010-07-22T20:44:32Z 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.