All reports by Author Elazar Goldenberg:

__
TR19-125
| 27th August 2019
__

Elazar Goldenberg, Karthik C. S.#### Hardness Amplification of Optimization Problems

__
TR15-128
| 10th August 2015
__

Roee David, Elazar Goldenberg, Robert Krauthgamer#### Local Reconstruction of Low-Rank Matrices and Subspaces

Revisions: 2

__
TR15-111
| 8th July 2015
__

Diptarka Chakraborty, Elazar Goldenberg, Michal Koucky#### Low Distortion Embedding from Edit to Hamming Distance using Coupling

Revisions: 1

__
TR14-132
| 23rd October 2014
__

Diptarka Chakraborty, Elazar Goldenberg, Michal Koucky#### Information Complexity for Multiparty Communication

Revisions: 2

__
TR14-002
| 8th January 2014
__

Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar#### Direct Sum Testing

Revisions: 1

__
TR13-031
| 22nd February 2013
__

Irit Dinur, Elazar Goldenberg#### Clustering in the Boolean Hypercube in a List Decoding Regime

Revisions: 2

Elazar Goldenberg, Karthik C. S.

In this paper, we prove a general hardness amplification scheme for optimization problems based on the technique of direct products.

We say that an optimization problem $\Pi$ is direct product feasible if it is possible to efficiently aggregate any $k$ instances of $\Pi$ and form one large instance ...
more >>>

Roee David, Elazar Goldenberg, Robert Krauthgamer

We study the problem of \emph{reconstructing a low-rank matrix}, where the input is an $n\times m$ matrix $M$ over a field $\mathbb{F}$ and the goal is to reconstruct a (near-optimal) matrix $M'$ that is low-rank and close to $M$ under some distance function $\Delta$.

Furthermore, the reconstruction must be local, ...
more >>>

Diptarka Chakraborty, Elazar Goldenberg, Michal Koucky

The Hamming and the edit metrics are two common notions of measuring distances between pairs of strings $x,y$ lying in the Boolean hypercube. The edit distance between $x$ and $y$ is defined as the minimum number of character insertion, deletion, and bit flips needed for converting $x$ into $y$. ...
more >>>

Diptarka Chakraborty, Elazar Goldenberg, Michal Koucky

In this paper, we have studied the information complexity for the communication model involving more than two parties. A lot of work has already been done on the information complexity in two party communication model and the question of extending the definition of information complexity to the multiparty communication model ... more >>>

Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar

For a string $a \in \{0,1\}^n$ its $k$-fold direct sum encoding is a function $f_a$ that takes as input sets $S \subseteq [n]$ of

size $k$ and outputs $f_a(S) = \sum_{i \in S} a_i$.

In this paper we are interested in the Direct Sum Testing Problem,

where we are given ...
more >>>

Irit Dinur, Elazar Goldenberg

We consider the following clustering with outliers problem: Given a set of points $X \subset \{-1,1\}^n$, such that there is some point $z \in \{-1,1\}^n$ for which at least $\delta$ of the points are $\epsilon$-correlated with $z$, find $z$. We call such a point $z$ a $(\delta,\epsilon)$-center of X.

In ... more >>>