Chris Peikert, Alon Rosen

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

Chris Peikert, Alon Rosen

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

Chris Peikert

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

Andrej Bogdanov, Chin Ho Lee

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

Oded Goldreich, Guy Rothblum

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

Oded Goldreich, Guy Rothblum

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

Oded Goldreich

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

Lijie Chen, Shuichi Hirahara, Neekon Vafa

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

Reyad Abed Elrazik, Robert Robere, Assaf Schuster, Gal Yehuda

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

Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor Oliveira

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

Vahid Reza Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian

We study the problem of designing worst-case to average-case reductions for quantum algorithms. For all linear problems, we provide an explicit and efficient transformation of quantum algorithms that are only correct on a small (even sub-constant) fraction of their inputs into ones that are correct on all inputs. This stands ... more >>>