Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > HARDNESS AMPLIFICATION:
Reports tagged with hardness amplification:
TR04-020 | 8th March 2004
Emanuele Viola

The Complexity of Constructing Pseudorandom Generators from Hard Functions

We study the complexity of building
pseudorandom generators (PRGs) from hard functions.

We show that, starting from a function f : {0,1}^l -> {0,1} that
is mildly hard on average, i.e. every circuit of size 2^Omega(l)
fails to compute f on at least a 1/poly(l)
fraction of inputs, we can ... more >>>


TR04-074 | 26th August 2004
Emanuele Viola

On Parallel Pseudorandom Generators

Revisions: 1

We study pseudorandom generator (PRG) constructions $G^f : {0,1}^l \to {0,1}^{l+s}$ from one-way functions $f : {0,1}^n \to {0,1}^m$. We consider PRG constructions of the form $G^f(x) = C(f(q_{1}) \ldots f(q_{poly(n)}))$
where $C$ is a polynomial-size constant depth circuit
and $C$ and the $q$'s are generated from $x$ arbitrarily.
more >>>


TR04-087 | 13th October 2004
Alexander Healy, Salil Vadhan, Emanuele Viola

Using Nondeterminism to Amplify Hardness

We revisit the problem of hardness amplification in $\NP$, as
recently studied by O'Donnell (STOC `02). We prove that if $\NP$
has a balanced function $f$ such that any circuit of size $s(n)$
fails to compute $f$ on a $1/\poly(n)$ fraction of inputs, then
$\NP$ has a function $f'$ such ... more >>>


TR05-057 | 19th May 2005
Venkatesan Guruswami, Valentine Kabanets

Hardness amplification via space-efficient direct products

We prove a version of the derandomized Direct Product Lemma for
deterministic space-bounded algorithms. Suppose a Boolean function
$g:\{0,1\}^n\to\{0,1\}$ cannot be computed on more than $1-\delta$
fraction of inputs by any deterministic time $T$ and space $S$
algorithm, where $\delta\leq 1/t$ for some $t$. Then, for $t$-step
walks $w=(v_1,\dots, v_t)$ ... more >>>


TR05-135 | 19th November 2005
Iftach Haitner, Danny Harnik, Omer Reingold

On the Power of the Randomized Iterate

We consider two of the most fundamental theorems in Cryptography. The first, due to Haastad et. al. [HILL99], is that pseudorandom generators can be constructed from any one-way function. The second due to Yao [Yao82] states that the existence of weak one-way functions (i.e. functions on which every efficient algorithm ... more >>>


TR06-154 | 13th December 2006
Joshua Buresh-Oppenheim, Valentine Kabanets, Rahul Santhanam

Uniform Hardness Amplification in NP via Monotone Codes

We consider the problem of amplifying uniform average-case hardness
of languages in $\NP$, where hardness is with respect to $\BPP$
algorithms. We introduce the notion of \emph{monotone}
error-correcting codes, and show that hardness amplification for
$\NP$ is essentially equivalent to constructing efficiently
\emph{locally} encodable and \emph{locally} list-decodable monotone
codes. The ... more >>>


TR07-089 | 13th September 2007
Parikshit Gopalan, Venkatesan Guruswami

Deterministic Hardness Amplification via Local GMD Decoding

We study the average-case hardness of the class NP against
deterministic polynomial time algorithms. We prove that there exists
some constant $\mu > 0$ such that if there is some language in NP
for which no deterministic polynomial time algorithm can decide L
correctly on a $1- (log n)^{-\mu}$ fraction ... more >>>


TR07-102 | 4th October 2007
Andrej Bogdanov, Muli Safra

Hardness amplification for errorless heuristics

An errorless heuristic is an algorithm that on all inputs returns either the correct answer or the special symbol "I don't know." A central question in average-case complexity is whether every distributional decision problem in NP has an errorless heuristic scheme: This is an algorithm that, for every δ > ... 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-079 | 31st August 2008
Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson

Uniform Direct-Product Theorems: Simplified, Optimized, and Derandomized

The classical Direct-Product Theorem for circuits says
that if a Boolean function $f:\{0,1\}^n\to\{0,1\}$ is somewhat hard
to compute on average by small circuits, then the corresponding
$k$-wise direct product function
$f^k(x_1,\dots,x_k)=(f(x_1),\dots,f(x_k))$ (where each
$x_i\in\{0,1\}^n$) is significantly harder to compute on average by
slightly smaller ... more >>>


TR09-027 | 2nd April 2009
Iftach Haitner

A Parallel Repetition Theorem for Any Interactive Argument

Revisions: 2

The question whether or not parallel repetition reduces the soundness error is a fundamental question in the theory of protocols. While parallel repetition reduces (at an exponential rate) the error in interactive proofs and (at a weak exponential rate) in special cases of interactive arguments (e.g., 3-message protocols - Bellare, ... more >>>


TR11-012 | 2nd February 2011
Andrej Bogdanov, Alon Rosen

Input locality and hardness amplification

We establish new hardness amplification results for one-way functions in which each input bit influences only a small number of output bits (a.k.a. input-local functions). Our transformations differ from previous ones in that they approximately preserve input locality and at the same time retain the input size of the original ... more >>>


TR11-016 | 7th February 2011
Sergei Artemenko, Ronen Shaltiel

Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification

Revisions: 1

Hardness amplification results show that for every function $f$ there exists a function $Amp(f)$ such that the following holds: if every circuit of size $s$ computes $f$ correctly on at most a $1-\delta$ fraction of inputs, then every circuit of size $s'$ computes $Amp(f)$ correctly on at most a $1/2+\eps$ ... more >>>


TR13-151 | 7th November 2013
Mark Bun, Justin Thaler

Hardness Amplification and the Approximate Degree of Constant-Depth Circuits

Revisions: 3

We establish a generic form of hardness amplification for the approximability of constant-depth Boolean circuits by polynomials. Specifically, we show that if a Boolean circuit cannot be pointwise approximated by low-degree polynomials to within constant error in a certain one-sided sense, then an OR of disjoint copies of that circuit ... more >>>


TR14-095 | 24th July 2014
Mark Braverman, Ankit Garg

Small value parallel repetition for general games

Revisions: 1

We prove a parallel repetition theorem for general games with value tending to 0. Previously Dinur and Steurer proved such a theorem for the special case of projection games. We use information theoretic techniques in our proof. Our proofs also extend to the high value regime (value close to 1) ... more >>>


TR15-060 | 14th April 2015
Omri Weinstein

Information Complexity and the Quest for Interactive Compression

Revisions: 1

Information complexity is the interactive analogue of Shannon's classical information theory. In recent years this field has emerged as a powerful tool for proving strong communication lower bounds, and for addressing some of the major open problems in communication complexity and circuit complexity. A notable achievement of information complexity is ... more >>>


TR16-160 | 26th October 2016
Irit Dinur, Prahladh Harsha, Rakesh Venkat, Henry Yuen

Multiplayer parallel repetition for expander games

Revisions: 1

We investigate the value of parallel repetition of one-round games with any number of players $k\ge 2$. It has been an open question whether an analogue of Raz's Parallel Repetition Theorem holds for games with more than two players, i.e., whether the value of the repeated game decays exponentially ... more >>>


TR17-173 | 6th November 2017
Igor Carboni Oliveira, Ruiwen Chen, Rahul Santhanam

An Average-Case Lower Bound against ACC^0

In a seminal work, Williams [Wil14] showed that NEXP (non-deterministic exponential time) does not have polynomial-size ACC^0 circuits. Williams' technique inherently gives a worst-case lower bound, and until now, no average-case version of his result was known.

We show that there is a language L in NEXP (resp. EXP^NP) ... more >>>


TR18-034 | 15th February 2018
Young Kun Ko

On Symmetric Parallel Repetition : Towards Equivalence of MAX-CUT and UG

Unique Games Conjecture (UGC), proposed by [Khot02], lies in the center of many inapproximability results. At the heart of UGC lies approximability of MAX-CUT, which is a special instance of Unique Game.[KhotKMO04, MosselOO05] showed that assuming Unique Games Conjecture, it is NP-hard to distinguish between MAX-CUT instance that has a ... more >>>


TR18-095 | 11th May 2018
Marco Carmosino, Russell Impagliazzo, Shachar Lovett, Ivan Mihajlin

Hardness Amplification for Non-Commutative Arithmetic Circuits

We show that proving mildly super-linear lower bounds on non-commutative arithmetic circuits implies exponential lower bounds on non-commutative circuits. That is, non-commutative circuit complexity is a threshold phenomenon: an apparently weak lower bound actually suffices to show the strongest lower bounds we could desire.

This is part of a recent ... more >>>


TR19-081 | 31st May 2019
Iftach Haitner, Noam Mazor, Ronen Shaltiel, Jad Silbak

Channels of Small Log-Ratio Leakage and Characterization of Two-Party Differentially Private Computation

Revisions: 1

Consider a PPT two-party protocol ?=(A,B) in which the parties get no private inputs and obtain outputs O^A,O^B?{0,1}, and let V^A and V^B denote the parties’ individual views. Protocol ? has ?-agreement if Pr[O^A=O^B]=1/2+?. The leakage of ? is the amount of information a party obtains about the event {O^A=O^B}; ... 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 >>>


TR20-143 | 16th September 2020
Shuichi Hirahara

Characterizing Average-Case Complexity of PH by Worst-Case Meta-Complexity

We exactly characterize the average-case complexity of the polynomial-time hierarchy (PH) by the worst-case (meta-)complexity of GapMINKT(PH), i.e., an approximation version of the problem of determining if a given string can be compressed to a short PH-oracle efficient program. Specifically, we establish the following equivalence:

DistPH is contained in ... more >>>


TR22-108 | 18th July 2022
Shuichi Hirahara, Nobutaka Shimizu

Hardness Self-Amplification from Feasible Hard-Core Sets

We consider the question of hardness self-amplification: Given a Boolean function $f$ that is hard to compute on a $o(1)$-fraction of inputs drawn from some distribution, can we prove that $f$ is hard to compute on a $(\frac{1}{2} - o(1))$-fraction of inputs drawn from the same distribution? We prove hardness ... more >>>


TR23-026 | 15th March 2023
Shuichi Hirahara, Nobutaka Shimizu

Hardness Self-Amplification: Simplified, Optimized, and Unified

Strong (resp. weak) average-case hardness refers to the properties of a computational problem in which a large (resp. small) fraction of instances are hard to solve. We develop a general framework for proving hardness self-amplification, that is, the equivalence between strong and weak average-case hardness. Using this framework, we prove ... more >>>


TR23-060 | 17th April 2023
Sagnik Saha, Nikolaj Schwartzbach, Prashant Nalini Vasudevan

The Planted $k$-SUM Problem: Algorithms, Lower Bounds, Hardness Amplification, and Cryptography

Revisions: 1

In the average-case $k$-SUM problem, given $r$ integers chosen uniformly at random from $\{0,\ldots,M-1\}$, the objective is to find a set of $k$ numbers that sum to $0$ modulo $M$ (this set is called a ``solution''). In the related $k$-XOR problem, given $k$ uniformly random Boolean vectors of length $\log{M}$, ... more >>>


TR23-176 | 15th November 2023
William Hoza

A Technique for Hardness Amplification Against $\mathrm{AC}^0$

Revisions: 2

We study hardness amplification in the context of two well-known "moderate" average-case hardness results for $\mathrm{AC}^0$ circuits. First, we investigate the extent to which $\mathrm{AC}^0$ circuits of depth $d$ can approximate $\mathrm{AC}^0$ circuits of some larger depth $d + k$. The case $k = 1$ is resolved by Håstad, Rossman, ... more >>>




ISSN 1433-8092 | Imprint