All reports by Author Oded Regev:

__
TR21-178
| 3rd December 2021
__

Srinivasan Arunachalam, Oded Regev, Penghui Yao#### On the Gaussian surface area of spectrahedra

__
TR20-080
| 19th May 2020
__

Joan Bruna, Oded Regev, Min Jae Song, Yi Tang#### Continuous LWE

Revisions: 1

__
TR20-057
| 20th April 2020
__

Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein#### Polynomial Data Structure Lower Bounds in the Group Model

Revisions: 1

__
TR16-110
| 19th July 2016
__

Alexander Golovnev, Oded Regev, Omri Weinstein#### The Minrank of Random Graphs

Revisions: 1

__
TR15-082
| 13th May 2015
__

Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright#### Beating the random assignment on constraint satisfaction problems of bounded degree

__
TR10-143
| 19th September 2010
__

Bo'az Klartag, Oded Regev#### Quantum One-Way Communication is Exponentially Stronger Than Classical Communication

__
TR10-140
| 17th September 2010
__

Amit Chakrabarti, Oded Regev#### An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance

__
TR05-039
| 13th April 2005
__

Irit Dinur, Elchanan Mossel, Oded Regev#### Conditional Hardness for Approximate Coloring

__
TR03-070
| 19th August 2003
__

Amit Chakrabarti, Oded Regev#### An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching

Srinivasan Arunachalam, Oded Regev, Penghui Yao

We show that for sufficiently large $n\geq 1$ and $d=C n^{3/4}$ for some universal constant $C>0$, a random spectrahedron with matrices drawn from Gaussian orthogonal ensemble has Gaussian surface area $\Theta(n^{1/8})$ with high probability.

more >>>Joan Bruna, Oded Regev, Min Jae Song, Yi Tang

We introduce a continuous analogue of the Learning with Errors (LWE) problem, which we name CLWE. We give a polynomial-time quantum reduction from worst-case lattice problems to CLWE, showing that CLWE enjoys similar hardness guarantees to those of LWE. Alternatively, our result can also be seen as opening new avenues ... more >>>

Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein

Proving super-logarithmic data structure lower bounds in the static \emph{group model} has been a fundamental challenge in computational geometry since the early 80's. We prove a polynomial ($n^{\Omega(1)}$) lower bound for an explicit range counting problem of $n^3$ convex polygons in $\R^2$ (each with $n^{\tilde{O}(1)}$ facets/semialgebraic-complexity), against linear storage arithmetic ... more >>>

Alexander Golovnev, Oded Regev, Omri Weinstein

The minrank of a graph $G$ is the minimum rank of a matrix $M$ that can be obtained from the adjacency matrix of $G$ by switching ones to zeros (i.e., deleting edges) and setting all diagonal entries to one. This quantity is closely related to the fundamental information-theoretic problems of ... more >>>

Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright

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 $\frac{1}{2} + \Omega(1/\sqrt{D})$ fraction of constraints, where $D$ is a bound on the number of constraints that each variable occurs in. ... more >>>

Bo'az Klartag, Oded Regev

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's paper it was open whether the ...
more >>>

Amit Chakrabarti, Oded Regev

We prove an optimal $\Omega(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 ... more >>>

Irit Dinur, Elchanan Mossel, Oded Regev

We study the approximate-coloring(q,Q) problem: Given a graph G, decide

whether \chi(G) \le q or \chi(G)\ge Q. We derive conditional

hardness for this problem for any constant 3\le q < Q. For q \ge

4, our result is based on Khot's 2-to-1 conjecture [Khot'02].

For q=3, we base our hardness ...
more >>>

Amit Chakrabarti, Oded Regev

We consider the approximate nearest neighbour search problem on the

Hamming Cube $\b^d$. We show that a randomised cell probe algorithm that

uses polynomial storage and word size $d^{O(1)}$ requires a worst case

query time of $\Omega(\log\log d/\log\log\log d)$. The approximation

factor may be as loose as $2^{\log^{1-\eta}d}$ for any ...
more >>>