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

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

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

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

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

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