Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > ELAZAR GOLDENBERG:
All reports by Author Elazar Goldenberg:

TR19-125 | 27th August 2019
Elazar Goldenberg, Karthik C. S.

Hardness Amplification of Optimization Problems

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 >>>


TR15-128 | 10th August 2015
Roee David, Elazar Goldenberg, Robert Krauthgamer

Local Reconstruction of Low-Rank Matrices and Subspaces

Revisions: 2

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 >>>


TR15-111 | 8th July 2015
Diptarka Chakraborty, Elazar Goldenberg, Michal Koucky

Low Distortion Embedding from Edit to Hamming Distance using Coupling

Revisions: 1


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 >>>


TR14-132 | 23rd October 2014
Diptarka Chakraborty, Elazar Goldenberg, Michal Koucky

Information Complexity for Multiparty Communication

Revisions: 2

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 >>>


TR14-002 | 8th January 2014
Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar

Direct Sum Testing

Revisions: 1

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 >>>


TR13-031 | 22nd February 2013
Irit Dinur, Elazar Goldenberg

Clustering in the Boolean Hypercube in a List Decoding Regime

Revisions: 2

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 >>>




ISSN 1433-8092 | Imprint