Title: Worst-Case to Average-Case Reductions for Subclasses of P
Abstract: For every polynomial q, we present (almost-linear-time) worst-case to average-case reductions for a class of problems in $$\mathcal P$$ that are widely conjectured not to be solvable in time q. These classes contain, for example, the problems of counting the number of t-cliques in a graph, for any fixed $$t\ge 3$$. Specifically, 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. We show an almost-linear-time reduction from solving any such problem in the worst-case to solving some other problem (in the same class) on typical inputs. Furthermore, for some of these problems, we show that their average-case complexity almost equals their worst-case complexity. En route we highlight a few issues and ideas such as sample-aided reductions, average-case analysis of randomized algorithms, and average-case emulation of arithmetic circuits by Boolean circuits. We also observe that adequately uniform versions of $$\mathcal{AC}^0[2]$$ admit worst-case to average-case reductions that run in almost linear-time.
Publication Year: 2020
Publication Date: 2020-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 11
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot