BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Oded Regev

Oded Regev contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
quant-phComputational Complexitymath.MGmath.FAData Structures and Algorithmsmath.COmath.NTCryptography and SecurityDiscrete MathematicsInformation Theorymath.ITmath.OAmath.PR

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
21works
0followers
13topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

21 published item(s)

preprint2024arXiv

An Efficient Quantum Factoring Algorithm

We show that $n$-bit integers can be factorized by independently running a quantum circuit with $\tilde{O}(n^{3/2})$ gates for $\sqrt{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.

0 citations0 reviewsNo code linkedOpen access
preprint2024arXiv

On Lattices, Learning with Errors, Random Linear Codes, and Cryptography

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 $\tilde{O}(n^2)$ and encrypting a message increases its size by a factor of $\tilde{O}(n)$ (in previous cryptosystems these values are $\tilde{O}(n^4)$ and $\tilde{O}(n^2)$, respectively). In fact, under the assumption that all parties share a random bit string of length $\tilde{O}(n^2)$, the size of the public key can be reduced to $\tilde{O}(n)$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

A Reverse Minkowski Theorem

$ \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(\log n + 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.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Efficient Rounding for the Noncommutative Grothendieck Inequality

$ \newcommand{\cclass}[1]{\textsf{#1}} $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.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Near-Optimal and Explicit Bell Inequality Violations

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., $\log n$ EPR-pairs), while we show that the winning probability of any classical strategy differs from ${1}/{2}$ by at most $O((\log n)/\sqrt{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/(\log n)^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.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Tight Hardness of the Non-commutative Grothendieck Problem

$\newcommand{\eps}{\varepsilon} $We prove that for any $\eps > 0$ it is $\textsf{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 $\ell_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 $\textsf{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).

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Nearly Optimal Embeddings of Flat Tori

We show that for any $n$-dimensional lattice $\mathcal{L} \subseteq \mathbb{R}^n$, the torus $\mathbb{R}^n/\mathcal{L}$ can be embedded into Hilbert space with $O(\sqrt{n\log n})$ distortion. This improves the previously best known upper bound of $O(n\sqrt{\log n})$ shown by Haviv and Regev (APPROX 2010) and approaches the lower bound of $Ω(\sqrt{n})$ due to Khot and Naor (FOCS 2005, Math. Annal. 2006).

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

New bounds on the density of lattice coverings

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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On the Lattice Isomorphism Problem

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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance

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+\sqrt{n}$ or at most $n/2-\sqrt{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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Elementary Proofs of Grothendieck Theorems for Completely Bounded Norms

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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Krivine schemes are optimal

It is shown that for every $k\in \N$ there exists a Borel probability measure $μ$ on $\{-1,1\}^{\R^{k}}\times \{-1,1\}^{\R^{k}}$ such that for every $m,n\in \N$ and $x_1,..., x_m,y_1,...,y_n\in S^{m+n-1}$ there exist $x_1&#39;,...,x_m&#39;,y_1&#39;,...,y_n&#39;\in S^{m+n-1}$ such that if $G:\R^{m+n}\to \R^k$ is a random $k\times (m+n)$ matrix whose entries are i.i.d. standard Gaussian random variables then for all $(i,j)\in {1,...,m}\times {1,...,n}$ we have \E_G[\int_{{-1,1}^{\R^{k}}\times {-1,1}^{\R^{k}}}f(Gx_i&#39;)g(Gy_j&#39;)dμ(f,g)]=\frac{<x_i,y_j>}{(1+C/k)K_G}, where $K_G$ is the real Grothendieck constant and $C\in (0,\infty)$ is a universal constant. This establishes that Krivine&#39;s rounding method yields an arbitrarily good approximation of $K_G$.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Locally decodable codes and the failure of cotype for projective tensor products

It is shown that for every $p\in (1,\infty)$ 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 $p_1,p_2,p_3\in (1,\infty)$ satisfy $\frac{1}{p_1}+\frac{1}{p_2}+\frac{1}{p_3}\le 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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Quantum XOR Games

We introduce quantum XOR games, a model of two-player one-round games that extends the model of XOR games by allowing the referee&#39;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&#39;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.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Bell Violations through Independent Bases Games

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.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Entropy-based Bounds on Dimension Reduction in L_1

We show that for every large enough integer $N$, there exists an $N$-point subset of $L_1$ such that for every $D>1$, embedding it into $\ell_1^d$ with distortion $D$ requires dimension $d$ at least $N^{Ω(1/D^2)}$, and that for every $\eps>0$ and large enough integer $N$, there exists an $N$-point subset of $L_1$ such that embedding it into $\ell_1^d$ 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.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Quantum One-Way Communication is Exponentially Stronger Than Classical Communication

In STOC 1999, Raz presented a (partial) function for which there is a quantum protocol communicating only $O(\log n)$ 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&#39;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.

0 citations0 reviewsNo code linkedOpen access
preprint2005arXiv

Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity

We consider the problem of bounded-error quantum state identification: given either state α_0 or state α_1, we are required to output `0&#39;, `1&#39; or `?&#39; (&#34;don&#39;t know&#34;), such that conditioned on outputting `0&#39; or `1&#39;, our guess is correct with high probability. The goal is to maximize the probability of not outputting `?&#39;. We prove a direct product theorem: if we&#39;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&#39;t share randomness, even if communication is quantum. This shows the optimality of Yao&#39;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.

0 citations0 reviewsNo code linkedOpen access