Ronen Shaltiel

A fundamental question of complexity theory is the direct product

question. Namely weather the assumption that a function $f$ is hard on

average for some computational class (meaning that every algorithm from

the class has small advantage over random guessing when computing $f$)

entails that computing $f$ on ...
more >>>

Rahul Jain, Hartmut Klauck, Ashwin Nayak

A basic question in complexity theory is whether the computational

resources required for solving k independent instances of the same

problem scale as k times the resources required for one instance.

We investigate this question in various models of classical

communication complexity.

We define a new measure, the subdistribution bound, ... more >>>

Ronen Shaltiel, Emanuele Viola

Hardness amplification is the fundamental task of

converting a $\delta$-hard function $f : {0,1}^n ->

{0,1}$ into a $(1/2-\eps)$-hard function $Amp(f)$,

where $f$ is $\gamma$-hard if small circuits fail to

compute $f$ on at least a $\gamma$ fraction of the

inputs. Typically, $\eps,\delta$ are small (and

$\delta=2^{-k}$ captures the case ...
more >>>

Neeraj Kayal, Timur Nezhmetdinov

We give a polynomial time algorithm that computes a

decomposition of a finite group G given in the form of its

multiplication table. That is, given G, the algorithm outputs two

subgroups A and B of G such that G is the direct product

of A ...
more >>>

Atri Rudra, Mary Wootters

In this work, we introduce a framework to study the effect of random operations on the combinatorial list decodability of a code.

The operations we consider correspond to row and column operations on the matrix obtained from the code by stacking the codewords together as columns. This captures many natural ...
more >>>

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

Nathan Geier

Assume that $X_0,X_1$ (respectively $Y_0,Y_1$) are $d_X$ (respectively $d_Y$) indistinguishable for circuits of a given size. It is well known that the product distributions $X_0Y_0,\,X_1Y_1$ are $d_X+d_Y$ indistinguishable for slightly smaller circuits. However, in probability theory where unbounded adversaries are considered through statistical distance, it is folklore knowledge that in ... more >>>