Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > WORST-CASE TO AVERAGE-CASE REDUCTIONS:
Reports tagged with worst-case to average-case reductions:
TR05-158 | 12th December 2005
Chris Peikert, Alon Rosen

#### Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices

The generalized knapsack function is defined as $f_{\a}(\x) = \sum_i a_i \cdot x_i$, where $\a = (a_1, \ldots, a_m)$ consists of $m$
elements from some ring $R$, and $\x = (x_1, \ldots, x_m)$ consists
of $m$ coefficients from a specified subset $S \subseteq R$.
Micciancio ... more >>>

TR06-147 | 27th November 2006
Chris Peikert, Alon Rosen

#### Lattices that Admit Logarithmic Worst-Case to Average-Case Connection Factors

Revisions: 1

We demonstrate an \emph{average-case} problem which is as hard as
finding $\gamma(n)$-approximate shortest vectors in certain
$n$-dimensional lattices in the \emph{worst case}, where $\gamma(n) = O(\sqrt{\log n})$. The previously best known factor for any class
of lattices was $\gamma(n) = \tilde{O}(n)$.

To obtain our ... more >>>

TR06-148 | 4th December 2006
Chris Peikert

#### Limits on the Hardness of Lattice Problems in $\ell_p$ Norms

Revisions: 1

We show that for any $p \geq 2$, lattice problems in the $\ell_p$
norm are subject to all the same limits on hardness as are known
for the $\ell_2$ norm. In particular, for lattices of dimension
$n$:

* Approximating the shortest and closest vector in ... more >>>

TR12-156 | 12th November 2012
Andrej Bogdanov, Chin Ho Lee

#### Limits of provable security for homomorphic encryption

Revisions: 1

We show that public-key bit encryption schemes which support weak homomorphic evaluation of parity or majority cannot be proved message indistinguishable beyond AM intersect coAM via general (adaptive) reductions, and beyond statistical zero-knowledge via reductions of constant query complexity.

Previous works on the limitation of reductions for proving security of ... more >>>

TR17-130 | 30th August 2017
Oded Goldreich, Guy Rothblum

#### Worst-case to Average-case reductions for subclasses of P

Revisions: 4

For every polynomial $q$, we present worst-case to average-case (almost-linear-time) reductions for a class of problems in $\cal P$ that are widely conjectured not to be solvable in time $q$.
These classes contain, for example, the problems of counting the number of $k$-cliques in a graph, for any fixed $k\geq3$.
more >>>

TR18-046 | 9th March 2018
Oded Goldreich, Guy Rothblum

#### Counting $t$-cliques: Worst-case to average-case reductions and Direct interactive proof systems

Revisions: 2

We present two main results regarding the complexity of counting the number of $t$-cliques in a graph.

\begin{enumerate}
\item{\em A worst-case to average-case reduction}:
We reduce counting $t$-cliques in any $n$-vertex graph to counting $t$-cliques in typical $n$-vertex graphs that are drawn from a simple distribution of min-entropy ${\widetilde\Omega}(n^2)$. For ... more >>>

TR20-104 | 12th July 2020
Oded Goldreich

#### On Counting $t$-Cliques Mod 2

Revisions: 3

For a constant integer $t$, we consider the problem of counting the number of $t$-cliques $\bmod 2$ in a given graph.
We show that this problem is not easier than determining whether a given graph contains a $t$-clique, and present a simple worst-case to average-case reduction for it. The ... more >>>

TR21-166 | 21st November 2021
Lijie Chen, Shuichi Hirahara, Neekon Vafa

#### Average-case Hardness of NP and PH from Worst-case Fine-grained Assumptions

What is a minimal worst-case complexity assumption that implies non-trivial average-case hardness of NP or PH? This question is well motivated by the theory of fine-grained average-case complexity and fine-grained cryptography. In this paper, we show that several standard worst-case complexity assumptions are sufficient to imply non-trivial average-case hardness ... more >>>

TR21-170 | 25th November 2021
Reyad Abed Elrazik, Robert Robere, Assaf Schuster, Gal Yehuda

#### Pseudorandom Self-Reductions for NP-Complete Problems

A language $L$ is random-self-reducible if deciding membership in $L$ can be reduced (in polynomial time) to deciding membership in $L$ for uniformly random instances. It is known that several "number theoretic" languages (such as computing the permanent of a matrix) admit random self-reductions. Feigenbaum and Fortnow showed that NP-complete ... more >>>

TR22-072 | 15th May 2022
Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor Oliveira

#### Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity

Understanding the relationship between the worst-case and average-case complexities of $\mathrm{NP}$ and of other subclasses of $\mathrm{PH}$ is a long-standing problem in complexity theory. Over the last few years, much progress has been achieved in this front through the investigation of meta-complexity: the complexity of problems that refer to the ... more >>>

ISSN 1433-8092 | Imprint