Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Direct product:
TR01-009 | 5th January 2001
Ronen Shaltiel

Towards proving strong direct product theorems

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

TR07-064 | 19th June 2007
Rahul Jain, Hartmut Klauck, Ashwin Nayak

Direct Product Theorems for Communication Complexity via Subdistribution Bounds

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

TR07-130 | 3rd December 2007
Ronen Shaltiel, Emanuele Viola

Hardness amplification proofs require majority

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

TR08-074 | 19th July 2008
Neeraj Kayal, Timur Nezhmetdinov

Factoring groups efficiently

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

TR14-104 | 9th August 2014
Atri Rudra, Mary Wootters

It'll probably work out: improved list-decoding through random operations

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

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

TR21-140 | 27th September 2021
Nathan Geier

Tight Computational Indistinguishability Bound of Product Distributions

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

ISSN 1433-8092 | Imprint