Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSign-Rank Can Increase Under Intersection
72
0
0.0
(
0
)
Added by
Nikhil Mande
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The communication class $mathbf{UPP}^{text{cc}}$ is a communication analog of the Turing Machine complexity class $mathbf{PP}$. It is characterized by a matrix-analytic complexity measure called sign-rank (also called dimension complexity), and is essentially the most powerful communication class against which we know how to prove lower bounds. For a communication problem $f$, let $f wedge f$ denote the function that evaluates $f$ on two disjoint inputs and outputs the AND of the results. We exhibit a communication problem $f$ with $mathbf{UPP}(f)= O(log n)$, and $mathbf{UPP}(f wedge f) = Theta(log^2 n)$. This is the first result showing that $mathbf{UPP}$ communication complexity can increase by more than a constant factor under intersection. We view this as a first step toward showing that $mathbf{UPP}^{text{cc}}$, the class of problems with polylogarithmic-cost $mathbf{UPP}$ communication protocols, is not closed under intersection. Our result shows that the function class consisting of intersections of two majorities on $n$ bits has dimension complexity $n^{Omega(log n)}$. This matches an upper bound of (Klivans, ODonnell, and Servedio, FOCS 2002), who used it to give a quasipolynomial time algorithm for PAC learning intersections of polylogarithmically many majorities. Hence, fundamentally new techniques will be needed to learn this class of functions in polynomial time.
rate research
Read More
A $left(n,ell,gammaright)$-sharing set family of size $m$ is a family of sets $S_1,ldots,S_msubseteq [n]$ s.t. each set has size $ell$ and each pair of sets shares at most $gamma$ elements. We let $mleft(n,ell,gammaright)$ denote the maximum size of any such set family and we consider the following question: How large can $mleft(n,ell,gammaright)$ be? $left(n,ell,gammaright)$-sharing set families have a rich set of applications including the construction of pseudorandom number generators and usable and secure password management schemes. We analyze the explicit construction of Blocki et al using recent bounds on the value of the $t$th Ramanujan prime. We show that this explicit construction produces a $left(4ell^2ln 4ell,ell,gammaright)$-sharing set family of size $left(2 ell ln 2ellright)^{gamma+1}$ for any $ellgeq gamma$. We also show that the construction of Blocki et al can be used to obtain a weak $left(n,ell,gammaright)$-sharing set family of size $m$ for any $m >0$. These results are competitive with the inexplicit construction of Raz et al for weak $left(n,ell,gammaright)$-sharing families. We show that our explicit construction of weak $left(n,ell,gammaright)$-sharing set families can be used to obtain a parallelizable pseudorandom number generator with a low memory footprint by using the pseudorandom number generator of Nisan and Wigderson. We also prove that $mleft(n,n/c_1,c_2nright)$ must be a constant whenever $c_2 leq frac{2}{c_1^3+c_1^2}$. We show that this bound is nearly tight as $mleft(n,n/c_1,c_2nright)$ grows exponentially fast whenever $c_2 > c_1^{-2}$.
Set disjointness is a central problem in communication complexity. Here Alice and Bob each receive a subset of an n-element universe, and they need to decide whether their inputs intersect or not. The communication complexity of this problem is relatively well understood, and in most models, including $-$ most famously $-$ interactive randomised communication with bounded error, the problem requires much communication. In this work we were looking for a variation of the set disjointness problem, as natural and simple as possible, for which the known lower bound methods would fail, and thus a new approach would be required in order to understand its complexity. The problem that we have found is a relational one: each player receives a subset as input, and the goal is to find an element that belongs to both players. We call it inevitable intersection.
Cryptography with quantum states exhibits a number of surprising and counterintuitive features. In a 2002 work, Barnum et al. argue that these features imply that digital signatures for quantum states are impossible (Barnum et al., FOCS 2002). In this work, we ask: can all forms of signing quantum data, even in a possibly weak sense, be completely ruled out? We give two results which shed significant light on this basic question. First, we prove an impossibility result for digital signatures for quantum data, which extends the result of Barnum et al. Specifically, we show that no nontrivial combination of correctness and security requirements can be fulfilled, beyond what is achievable simply by measuring the quantum message and then signing the outcome. In other words, only classical signature schemes exist. We then show a positive result: a quantum state can be signed with the same security guarantees as classically, provided that it is also encrypted with the public key of the intended recipient. Following classical nomenclature, we call this notion quantum signcryption. Classically, signcryption is only interesting if it provides superior performance to encypt-then-sign. Quantumly, it is far more interesting: it is the only signing method available. We develop as-strong-as-classical security definitions for quantum signcryption and give secure constructions based on post-quantum public-key primitives. Along the way, we show that a natural hybrid method of combining classical and quantum schemes can be used to upgrade a secure classical scheme to the fully-quantum setting, in a wide range of cryptographic settings including signcryption, authenticated encryption, and CCA security.
Say that A is a Hadamard factorization of the identity I_n of size n if the entrywise product of A and the transpose of A is I_n. It can be easily seen that the rank of any Hadamard factorization of the identity must be at least sqrt{n}. Dietzfelbinger et al. raised the question if this bound can be achieved, and showed a boolean Hadamard factorization of the identity of rank n^{0.792}. More recently, Klauck and Wolf gave a construction of Hadamard factorizations of the identity of rank n^{0.613}. Over finite fields, Friesen and Theis resolved the question, showing for a prime p and r=p^t+1 a Hadamard factorization of the identity A of size r(r-1)+1 and rank r over F_p. Here we resolve the question for fields of zero characteristic, up to a constant factor, giving a construction of Hadamard factorizations of the identity of rank r and size (r+1)r/2. The matrices in our construction are blockwise Toeplitz, and have entries whose magnitudes are binomial coefficients.
One of the strongest techniques available for showing lower bounds on quantum communication complexity is the logarithm of the approximation rank of the communication matrix--the minimum rank of a matrix which is entrywise close to the communication matrix. This technique has two main drawbacks: it is difficult to compute, and it is not known to lower bound quantum communication complexity with entanglement. Linial and Shraibman recently introduced a norm, called gamma_2^{alpha}, to quantum communication complexity, showing that it can be used to lower bound communication with entanglement. Here the parameter alpha is a measure of approximation which is related to the allowable error probability of the protocol. This bound can be written as a semidefinite program and gives bounds at least as large as many techniques in the literature, although it is smaller than the corresponding alpha-approximation rank, rk_alpha. We show that in fact log gamma_2^{alpha}(A)$ and log rk_{alpha}(A)$ agree up to small factors. As corollaries we obtain a constant factor polynomial time approximation algorithm to the logarithm of approximate rank, and that the logarithm of approximation rank is a lower bound for quantum communication complexity with entanglement.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
