论文标题
证明精细粒度平均硬度硬度的新技术
New Techniques for Proving Fine-Grained Average-Case Hardness
论文作者
论文摘要
最近的细粒密码学的出现强烈激励了发展平均细粒复杂性（FGC）的平均类似物。 本文定义了新版本的OV，$ K $ SUM和ZERO-K $ -Clique，它们是FGC的核心假设，它们既最差案例又是平均细胞细粒度。然后，我们将其用作其他问题的细粒硬度和平均硬度硬度的基础。新问题以某种````cotored''''形式代表了他们的输入。我们称它们为````货运'' - ov，``````''''' - 零 - $ k $ -clique和````toxored''' - $ 3 $ sum。我们表明 - $ k $ -ov and contored $ k $ sum等同于$ k $ ov，对于在布尔函数上定义的一类问题都是完整的。对于不同类别的问题，零$ K $ -Clique也已完成。 我们棘手的问题也很简单，我们可以将它们减少到许多其他问题，例如〜编辑距离，$ k $ -lcs和max-flow版本。我们进一步考虑计算分类问题的变体，并为它们提供自然分布的WCTOACFG减少。然后，通过减少FGC，我们获得了经过深入研究的问题的平均案例硬度，例如与标准最差的FGC假设相匹配的正则表达式匹配。 为了获得我们的WCTOACFG减少，我们正式化了[Boix-Adsera等人的框架。 [2019年]用于减少$ k $ cliques的WCTOACFG。我们定义了问题的明确属性，以便如果一个问题有该属性，就可以使用问题上的框架来获得WCTOACFG自减少。然后，我们使用该框架稍微扩展了Boix-Adsera等人的平均计数$ k $ cliques结果的平均值硬度，以计算$ K $ - $ - 分段图的任意子图模式...
The recent emergence of fine-grained cryptography strongly motivates developing an average-case analogue of Fine-Grained Complexity (FGC). This paper defines new versions of OV, $k$SUM and zero-$k$-clique that are both worst-case and average-case fine-grained hard assuming the core hypotheses of FGC. We then use these as a basis for fine-grained hardness and average-case hardness of other problems. The new problems represent their inputs in a certain ``factored'' form. We call them ``factored''-OV, ``factored''-zero-$k$-clique and ``factored''-$3$SUM. We show that factored-$k$-OV and factored $k$SUM are equivalent and are complete for a class of problems defined over Boolean functions. Factored zero-$k$-clique is also complete, for a different class of problems. Our hard factored problems are also simple enough that we can reduce them to many other problems, e.g.~to edit distance, $k$-LCS and versions of Max-Flow. We further consider counting variants of the factored problems and give WCtoACFG reductions for them for a natural distribution. Through FGC reductions we then get average-case hardness for well-studied problems like regular expression matching from standard worst-case FGC assumptions. To obtain our WCtoACFG reductions, we formalize the framework of [Boix-Adsera et al. 2019] that was used to give a WCtoACFG reduction for counting $k$-cliques. We define an explicit property of problems such that if a problem has that property one can use the framework on the problem to get a WCtoACFG self reduction. We then use the framework to slightly extend Boix-Adsera et al.'s average-case counting $k$-cliques result to average-case hardness for counting arbitrary subgraph patterns of constant size in $k$-partite graphs...
