BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We show that n-bit integers can be factorized by independently running a quantum circuit with O~(n3/2) gates for n+4 times, and then using polynomial-time classical post-processing. The correctness of the algorithm relies on a number-theoretic heuristic assumption reminiscent of those used in subexponential classical factorization algorithms. It is currently not clear if the algorithm can lead to improved physical implementations in practice.
Our main result is a reduction from worst-case lattice problems such as GapSVP and SIVP to a certain learning problem. This learning problem is a natural extension of the `learning from parity with error' problem to higher moduli. It can also be viewed as the problem of decoding from a random linear code. This, we believe, gives a strong indication that these problems are hard. Our reduction, however, is quantum. Hence, an efficient solution to the learning problem implies a quantum algorithm for GapSVP and SIVP. A main open question is whether this reduction can be made classical (i.e., non-quantum). We also present a (classical) public-key cryptosystem whose security is based on the hardness of the learning problem. By the main result, its security is also based on the worst-case quantum hardness of GapSVP and SIVP. The new cryptosystem is much more efficient than previous lattice-based cryptosystems: the public key is of size O~(n2) and encrypting a message increases its size by a factor of O~(n) (in previous cryptosystems these values are O~(n4) and O~(n2), respectively). In fact, under the assumption that all parties share a random bit string of length O~(n2), the size of the public key can be reduced to O~(n).
We prove that for any n∈N there is a convex body K⊆Rn whose surface area is at most n21+o(1), yet the translates of K by the integer lattice Zn tile Rn.
$ \newcommand{\R}{\mathbb{R}} \newcommand{\lat}{\mathcal{L}} $We prove a conjecture due to Dadush, showing that if $\lat \subset \R^n$ is a lattice such that $\det(\lat') \ge 1$ for all sublattices $\lat' \subseteq \lat$, then \[ \sum_{\vec y \in \lat} e^{-πt^2 \|\vec y\|^2} \le 3/2 \; , \] where t:=10(logn+2). From this we derive bounds on the number of short lattice vectors, which can be viewed as a partial converse to Minkowski's celebrated first theorem. We also derive a bound on the covering radius.
The classical Grothendieck inequality has applications to the design of approximation algorithms for $\cclass{NP}$-hard optimization problems. We show that an algorithmic interpretation may also be given for a noncommutative generalization of the Grothendieck inequality due to Pisier and Haagerup. Our main result, an efficient rounding procedure for this inequality, leads to a polynomial-time constant-factor approximation algorithm for an optimization problem which generalizes the Cut Norm problem of Frieze and Kannan, and is shown here to have additional applications to robust principal component analysis and the orthogonal Procrustes problem.
Entangled quantum systems can exhibit correlations that cannot be simulated classically. For historical reasons such correlations are called "Bell inequality violations." We give two new two-player games with Bell inequality violations that are stronger, fully explicit, and arguably simpler than earlier work. The first game is based on the Hidden Matching problem of quantum communication complexity, introduced by Bar-Yossef, Jayram, and Kerenidis. This game can be won with probability 1 by a strategy using a maximally entangled state with local dimension n (e.g., logn EPR-pairs), while we show that the winning probability of any classical strategy differs from 1/2 by at most O((logn)/n). The second game is based on the integrality gap for Unique Games by Khot and Vishnoi and the quantum rounding procedure of Kempe, Regev, and Toner. Here n-dimensional entanglement allows the game to be won with probability 1/(logn)2, while the best winning probability without entanglement is 1/n. This near-linear ratio is almost optimal, both in terms of the local dimension of the entangled state, and in terms of the number of possible outputs of the two players.
We show that for sufficiently large n≥1 and d=Cn3/4 for some universal constant C>0, a random spectrahedron with matrices drawn from Gaussian orthogonal ensemble has Gaussian surface area Θ(n1/8) with high probability.
We prove that for any $\eps > 0$ it is NP-hard to approximate the non-commutative Grothendieck problem to within a factor $1/2 + \eps$, which matches the approximation ratio of the algorithm of Naor, Regev, and Vidick (STOC'13). Our proof uses an embedding of ℓ2 into the space of matrices endowed with the trace norm with the property that the image of standard basis vectors is longer than that of unit vectors with no large coordinates. We also observe that one can obtain a tight NP-hardness result for the commutative Little Grothendieck problem; previously, this was only known based on the Unique Games Conjecture (Khot and Naor, Mathematika 2009).
We show that for any n-dimensional lattice L⊆Rn, the torus Rn/L can be embedded into Hilbert space with O(nlogn) distortion. This improves the previously best known upper bound of O(nlogn) shown by Haviv and Regev (APPROX 2010) and approaches the lower bound of Ω(n) due to Khot and Naor (FOCS 2005, Math. Annal. 2006).
We obtain new upper bounds on the minimal density of lattice coverings of Euclidean space by dilates of a convex body K. We also obtain bounds on the probability (with respect to the natural Haar-Siegel measure on the space of lattices) that a randomly chosen lattice L satisfies that L+K is all of space. As a step in the proof, we utilize and strengthen results on the discrete Kakeya problem.
$ \newcommand{\R}{\mathbb{R}} \newcommand{\Z}{\mathbb{Z}} \renewcommand{\vec}[1]{\mathbf{#1}} $We show that if K⊂Rd is an origin-symmetric convex body, then there exists a vector y∈Zd such that \begin{align*} |K \cap \Z^d \cap \vec{y}^\perp| / |K \cap \Z^d| \ge \min(1,c \cdot d^{-1} \cdot \mathrm{vol}(K)^{-1/(d-1)}) \; , \end{align*} for some absolute constant c>0, where y⊥ denotes the subspace orthogonal to y. This gives a partial answer to a question by Koldobsky.
We present a natural reverse Minkowski-type inequality for lattices, which gives upper bounds on the number of lattice points in a Euclidean ball in terms of sublattice determinants, and conjecture its optimal form. The conjecture exhibits a surprising wealth of connections to various areas in mathematics and computer science, including a conjecture motivated by integer programming by Kannan and Lovász (Annals of Math. 1988), a question from additive combinatorics asked by Green, a question on Brownian motions asked by Saloff-Coste (Colloq. Math. 2010), a theorem by Milman and Pisier from convex geometry (Ann. Probab. 1987), worst-case to average-case reductions in lattice-based cryptography, and more. We present these connections, provide evidence for the conjecture, and discuss possible approaches towards a proof. Our main technical contribution is in proving that our conjecture implies the ℓ2 case of the Kannan and Lovász conjecture. The proof relies on a novel convex relaxation for the covering radius, and a rounding procedure for based on "uncrossing" lattice subspaces.
For a finite undirected graph G=(V,E), let pu,v(t) denote the probability that a continuous-time random walk starting at vertex u is in v at time t. In this note we give an example of a Cayley graph G and two vertices u,v∈G for which the function ru,v(t)=pu,u(t)pu,v(t)t≥0 is not monotonically non-decreasing. This answers a question asked by Peres in 2013.
We show that for any odd k and any instance of the Max-kXOR constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a 21+Ω(1/D) fraction of constraints, where D is a bound on the number of constraints that each variable occurs in. This improves both qualitatively and quantitatively on the recent work of Farhi, Goldstone, and Gutmann (2014), which gave a \emph{quantum} algorithm to find an assignment satisfying a 21+Ω(D−3/4) fraction of the equations. For arbitrary constraint satisfaction problems, we give a similar result for "triangle-free" instances; i.e., an efficient algorithm that finds an assignment satisfying at least a μ+Ω(1/D) fraction of constraints, where μ is the fraction that would be satisfied by a uniformly random assignment.
In the k-junta testing problem, a tester has to efficiently decide whether a given function f:{0,1}n→{0,1} is a k-junta (i.e., depends on at most k of its input bits) or is ε-far from any k-junta. Our main result is a quantum algorithm for this problem with query complexity O~(k/ε) and time complexity O~(nk/ε). This quadratically improves over the query complexity of the previous best quantum junta tester, due to Atıcı and Servedio. Our tester is based on a new quantum algorithm for a gapped version of the combinatorial group testing problem, with an up to quartic improvement over the query complexity of the best classical algorithm. For our upper bound on the time complexity we give a near-linear time implementation of a shallow variant of the quantum Fourier transform over the symmetric group, similar to the Schur-Weyl transform. We also prove a lower bound of Ω(k1/3) queries for junta-testing (for constant ε).
A function defined on the Boolean hypercube is k-Fourier-sparse if it has at most k nonzero Fourier coefficients. For a function f:F2n→R and parameters k and d, we prove a strong upper bound on the number of k-Fourier-sparse Boolean functions that disagree with f on at most d inputs. Our bound implies that the number of uniform and independent random samples needed for learning the class of k-Fourier-sparse Boolean functions on n variables exactly is at most O(n⋅klogk). As an application, we prove an upper bound on the query complexity of testing Booleanity of Fourier-sparse functions. Our bound is tight up to a logarithmic factor and quadratically improves on a result due to Gur and Tamuz (Chicago J. Theor. Comput. Sci., 2013).
A matrix A∈Cq×N satisfies the restricted isometry property of order k with constant ε if it preserves the ℓ2 norm of all k-sparse vectors up to a factor of 1±ε. We prove that a matrix A obtained by randomly sampling q=O(k⋅log2k⋅logN) rows from an N×N Fourier matrix satisfies the restricted isometry property of order k with a fixed ε with high probability. This improves on Rudelson and Vershynin (Comm. Pure Appl. Math., 2008), its subsequent improvements, and Bourgain (GAFA Seminar Notes, 2014).
We analyze the distribution of $\sum_{i=1}^m v_i \bx_i$ where $\bx_1,...,\bx_m$ are fixed vectors from some lattice $\cL \subset \R^n$ (say Zn) and v1,...,vm are chosen independently from a discrete Gaussian distribution over Z. We show that under a natural constraint on $\bx_1,...,\bx_m$, if the vi are chosen from a wide enough Gaussian, the sum is statistically close to a discrete Gaussian over $\cL$. We also analyze the case of $\bx_1,...,\bx_m$ that are themselves chosen from a discrete Gaussian distribution (and fixed). Our results simplify and qualitatively improve upon a recent result by Agrawal, Gentry, Halevi, and Sahai \cite{AGHS13}.
We show that the Learning with Errors (LWE) problem is classically at least as hard as standard worst-case lattice problems, even with polynomial modulus. Previously this was only known under quantum reductions. Our techniques capture the tradeoff between the dimension and the modulus of LWE instances, leading to a much better understanding of the landscape of the problem. The proof is inspired by techniques from several recent cryptographic constructions, most notably fully homomorphic encryption schemes.
We study the Lattice Isomorphism Problem (LIP), in which given two lattices L_1 and L_2 the goal is to decide whether there exists an orthogonal linear transformation mapping L_1 to L_2. Our main result is an algorithm for this problem running in time n^{O(n)} times a polynomial in the input size, where n is the rank of the input lattices. A crucial component is a new generalized isolation lemma, which can isolate n linearly independent vectors in a given subset of Z^n and might be useful elsewhere. We also prove that LIP lies in the complexity class SZK.
We prove an optimal Ω(n) lower bound on the randomized communication complexity of the much-studied Gap-Hamming-Distance problem. As a consequence, we obtain essentially optimal multi-pass space lower bounds in the data stream model for a number of fundamental problems, including the estimation of frequency moments. The Gap-Hamming-Distance problem is a communication problem, wherein Alice and Bob receive n-bit strings x and y, respectively. They are promised that the Hamming distance between x and y is either at least n/2+n or at most n/2−n, and their goal is to decide which of these is the case. Since the formal presentation of the problem by Indyk and Woodruff (FOCS, 2003), it had been conjectured that the naive protocol, which uses n bits of communication, is asymptotically optimal. The conjecture was shown to be true in several special cases, e.g., when the communication is deterministic, or when the number of rounds of communication is limited. The proof of our aforementioned result, which settles this conjecture fully, is based on a new geometric statement regarding correlations in Gaussian space, related to a result of C. Borell (1985). To prove this geometric statement, we show that random projections of not-too-small sets in Gaussian space are close to a mixture of translated normal variables.
We provide alternative proofs of two recent Grothendieck theorems for jointly completely bounded bilinear forms, originally due to Pisier and Shlyakhtenko (Invent. Math. 2002) and Haagerup and Musat (Invent. Math. 2008). Our proofs are elementary and are inspired by the so-called embezzlement states in quantum information theory. Moreover, our proofs lead to quantitative estimates.
We consider Grover's unstructured search problem in the setting where each oracle call has some small probability of failing. We show that no quantum speed-up is possible in this case.
It is shown that for every k∈N there exists a Borel probability measure μ on {−1,1}Rk×{−1,1}Rk such that for every m,n∈N and x1,...,xm,y1,...,yn∈Sm+n−1 there exist x1′,...,xm′,y1′,...,yn′∈Sm+n−1 such that if G:Rm+n→Rk is a random k×(m+n) matrix whose entries are i.i.d. standard Gaussian random variables then for all (i,j)∈1,...,m×1,...,n we have \E_G[\int_{{-1,1}^{\R^{k}}\times {-1,1}^{\R^{k}}}f(Gx_i')g(Gy_j')dμ(f,g)]=\frac{<x_i,y_j>}{(1+C/k)K_G}, where KG is the real Grothendieck constant and C∈(0,∞) is a universal constant. This establishes that Krivine's rounding method yields an arbitrarily good approximation of KG.
It is shown that for every p∈(1,∞) there exists a Banach space X of finite cotype such that the projective tensor product $\ell_p\tp X$ fails to have finite cotype. More generally, if p1,p2,p3∈(1,∞) satisfy p11+p21+p31≤1 then $\ell_{p_1}\tp\ell_{p_2}\tp\ell_{p_3}$ does not have finite cotype. This is a proved via a connection to the theory of locally decodable codes.
We introduce quantum XOR games, a model of two-player one-round games that extends the model of XOR games by allowing the referee's questions to the players to be quantum states. We give examples showing that quantum XOR games exhibit a wide range of behaviors that are known not to exist for standard XOR games, such as cases in which the use of entanglement leads to an arbitrarily large advantage over the use of no entanglement. By invoking two deep extensions of Grothendieck's inequality, we present an efficient algorithm that gives a constant-factor approximation to the best performance players can obtain in a given game, both in case they have no shared entanglement and in case they share unlimited entanglement. As a byproduct of the algorithm we prove some additional interesting properties of quantum XOR games, such as the fact that sharing a maximally entangled state of arbitrary dimension gives only a small advantage over having no entanglement at all.
In a recent paper, Junge and Palazuelos presented two two-player games exhibiting interesting properties. In their first game, entangled players can perform notably better than classical players. The quantitative gap between the two cases is remarkably large, especially as a function of the number of inputs to the players. In their second game, entangled players can perform notably better than players that are restricted to using a maximally entangled state (of arbitrary dimension). This was the first game exhibiting such a behavior. The analysis of both games is heavily based on non-trivial results from Banach space theory and operator space theory. Here we present two games exhibiting a similar behavior, but with proofs that are arguably simpler, using elementary probabilistic techniques and standard quantum information arguments. Our games also give better quantitative bounds.
We show that for every large enough integer N, there exists an N-point subset of L1 such that for every D>1, embedding it into ℓ1d with distortion D requires dimension d at least NΩ(1/D2), and that for every $\eps>0$ and large enough integer N, there exists an N-point subset of L1 such that embedding it into ℓ1d with distortion $1+\eps$ requires dimension d at least $N^{1-O(1/\log(1/\eps))}$. These results were previously proven by Brinkman and Charikar [JACM, 2005] and by Andoni, Charikar, Neiman, and Nguyen [FOCS 2011]. We provide an alternative and arguably more intuitive proof based on an entropy argument.
In STOC 1999, Raz presented a (partial) function for which there is a quantum protocol communicating only O(logn) qubits, but for which any classical (randomized, bounded-error) protocol requires $\poly(n)$ bits of communication. That quantum protocol requires two rounds of communication. Ever since Raz's paper it was open whether the same exponential separation can be achieved with a quantum protocol that uses only one round of communication. Here we settle this question in the affirmative.
Thin viscous Keplerian accretion disks are considered asymptotically stable, even though they can show significant dynamic activity on short timescales. In this paper the dynamics of non-axisymmetric hydrodynamical disturbances of disks are investigated analytically building upon the steady state three-dimensional structure and evolution of axisymmetric perturbations explored in previous work. Assuming a polytropic equation of state solutions are found by means of an asymptotic expansion in the small parameter measuring the ratio of the disk thickness to characteristic radius. In-depth analysis shows that every perturbation that disturbs the radial velocity induces significant transient growth in the (acoustic) energy of the evolving disturbance. This effect is most evident in the density and vertical velocity. The transient growth observed is tied to the non-separable nature of the solutions where, in particular, pattern evolution is controlled by a similarity variable composed of the radial coordinate and time. This leads to growing winding perturbations that display successive radial peaks and troughs. We argue that these transient non-axisymmetric structures may precipitate secondary instabilities which, consequently, may be a critical element for a new alternative picture of turbulence arousal in non-magnetized astrophysical disks.
The Bonami-Beckner hypercontractive inequality is a powerful tool in Fourier analysis of real-valued functions on the Boolean cube. In this paper we present a version of this inequality for matrix-valued functions on the Boolean cube. Its proof is based on a powerful inequality by Ball, Carlen, and Lieb. We also present a number of applications. First, we analyze maps that encode n classical bits into m qubits, in such a way that each set of k bits can be recovered with some probability by an appropriate measurement on the quantum encoding; we show that if m<0.7n, then the success probability is exponentially small in k. This result may be viewed as a direct product version of Nayak's quantum random access code bound. It in turn implies strong direct product theorems for the one-way quantum communication complexity of Disjointness and other problems. Second, we prove that error-correcting codes that are locally decodable with 2 queries require length exponential in the length of the encoded string. This gives what is arguably the first ``non-quantum'' proof of a result originally derived by Kerenidis and de Wolf using quantum information theory, and answers a question by Trevisan.
Methods and techniques of the theory of nonlinear dynamical systems and patterns can be useful in astrophysical applications. Some works on the subjects of dynamical astronomy, stellar pulsation and variability, as well as spatial complexity in extended systems, in which such approaches have already been utilized, are reviewed. Prospects for future directions in applications of this kind are outlined.
We consider the problem of bounded-error quantum state identification: given either state α_0 or state α_1, we are required to output `0', `1' or `?' ("don't know"), such that conditioned on outputting `0' or `1', our guess is correct with high probability. The goal is to maximize the probability of not outputting `?'. We prove a direct product theorem: if we're given two such problems, with optimal probabilities a and b, respectively, and the states in the first problem are pure, then the optimal probability for the joint bounded-error state identification problem is O(ab). Our proof is based on semidefinite programming duality and may be of wider interest. Using this result, we present two exponential separations in the simultaneous message passing model of communication complexity. Both are shown in the strongest possible sense. First, we describe a relation that can be computed with O(log n) classical bits of communication in the presence of shared randomness, but needs Omega(n^{1/3}) communication if the parties don't share randomness, even if communication is quantum. This shows the optimality of Yao's recent exponential simulation of shared-randomness protocols by quantum protocols without shared randomness. Second, we describe a relation that can be computed with O(log n) classical bits of communication in the presence of shared entanglement, but needs Omega((n/log n)^{1/3}) communication if the parties share randomness but no entanglement, even if communication is quantum. This is the first example in communication complexity of a situation where entanglement buys you much more than quantum communication does.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.