ECCC-Report TR17-130https://eccc.weizmann.ac.il/report/2017/130Comments and Revisions published for TR17-130en-usWed, 20 Feb 2019 11:46:00 +0200
Revision 4
| Worst-case to Average-case reductions for subclasses of P |
Oded Goldreich,
Guy Rothblum
https://eccc.weizmann.ac.il/report/2017/130#revision4For 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.Wed, 20 Feb 2019 11:46:00 +0200https://eccc.weizmann.ac.il/report/2017/130#revision4
Revision 3
| Worst-case to Average-case reductions for subclasses of P |
Oded Goldreich,
Guy Rothblum
https://eccc.weizmann.ac.il/report/2017/130#revision3For 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.Tue, 07 Aug 2018 12:00:23 +0300https://eccc.weizmann.ac.il/report/2017/130#revision3
Revision 2
| Worst-case to Average-case reductions for subclasses of P |
Oded Goldreich,
Guy Rothblum
https://eccc.weizmann.ac.il/report/2017/130#revision2For 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.Mon, 22 Jan 2018 17:38:25 +0200https://eccc.weizmann.ac.il/report/2017/130#revision2
Revision 1
| Worst-case to Average-case reductions for subclasses of P |
Oded Goldreich,
Guy Rothblum
https://eccc.weizmann.ac.il/report/2017/130#revision1For 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.Sun, 21 Jan 2018 16:03:14 +0200https://eccc.weizmann.ac.il/report/2017/130#revision1
Paper TR17-130
| Worst-case to Average-case reductions for subclasses of P |
Oded Goldreich,
Guy Rothblum
https://eccc.weizmann.ac.il/report/2017/130For 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.Wed, 30 Aug 2017 11:42:08 +0300https://eccc.weizmann.ac.il/report/2017/130