论文标题
随机$ k $ -xor的更简单的强烈反驳
A simpler strong refutation of random $k$-XOR
论文作者
论文摘要
随机CSP的强烈反驳是理论计算机科学中的一个基本问题，由于信息理论极限与计算限制之间的长期差距，因此受到了特别关注。该差距最近由Raghavendra，Rao和Schramm桥接，在那里他们研究了两个限制之间的次数算法。在这项工作中，我们采用更简单的方法来进行其算法和分析。
Strong refutation of random CSPs is a fundamental question in theoretical computer science that has received particular attention due to the long-standing gap between the information-theoretic limit and the computational limit. This gap is recently bridged by Raghavendra, Rao and Schramm where they study sub-exponential algorithms for the regime between the two limits. In this work, we take a simpler approach to their algorithm and analysis.
