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

#### Webpage for a paper by Oded Goldreich and Guy Rothblum

#### Abstract

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$.
In general, we consider the class of problems that consist
of counting the number of local neighborhoods in the input
that satisfy some predetermined conditions, where the number
of neighborhoods is polynomial, and the neighborhoods
as well as the conditions
can be specified by small uniform Boolean formulas.
Hence, we show an almost-linear-time reduction from
solving one such problem in the worst-case to solving
some other problem (in the same class) on typical inputs.

#### Material available on-line

Back to
either Oded Goldreich's homepage
or general list of papers.