Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Revision(s):

Revision #4 to TR17-130 | 20th February 2019 11:46

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

Revision #4
Authors: Oded Goldreich, Guy Rothblum
Accepted on: 20th February 2019 11:46
Keywords:

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.

Changes to previous version:

Adding reference to our follow-up work TR18-046

Revision #3 to TR17-130 | 7th August 2018 12:00

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

Revision #3
Authors: Oded Goldreich, Guy Rothblum
Accepted on: 7th August 2018 12:00
Keywords:

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.

Changes to previous version:

fixed a typo in Def 1.4

Revision #2 to TR17-130 | 22nd January 2018 17:38

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

Revision #2
Authors: Oded Goldreich, Guy Rothblum
Accepted on: 22nd January 2018 17:38
Keywords:

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.

Changes to previous version:

minor revision

Revision #1 to TR17-130 | 21st January 2018 16:03

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

Revision #1
Authors: Oded Goldreich, Guy Rothblum
Accepted on: 21st January 2018 16:03
Keywords:

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.

Changes to previous version:

Added an overview of the techniques (Sec 1.3),
and a comment on worst-case to average-case reductions for a uniform version of AC0[2].

Paper:

TR17-130 | 30th August 2017 11:41

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

TR17-130
Authors: Oded Goldreich, Guy Rothblum
Publication: 30th August 2017 11:42
Keywords:

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.

ISSN 1433-8092 | Imprint