Polynomial Representations of Threshold Functions and Algorithmic Applications
Polynomial Representations of Threshold Functions and Algorithmic Applications
复制标题
阈值函数的多项式表示和算法应用
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Ryan Williams
中科院分区：
文献类型：
--
作者：
Josh Alman;Timothy M. Chan;Ryan Williams
我们设计了新的多项式，用于表示三种不同状态下的阈值函数：低次概率多项式，其需要比以前的构造少得多的随机性，具有“良好”阈值行为且次数几乎与概率多项式一样低的多项式阈值函数（PTF），以及概率PTF的新概念，其中我们将上述技术联合收割机组合以实现具有类似“好”阈值行为的甚至更低的程度。·离线汉明最近（和最远）邻居：给定d维汉明空间中的n个红色和n个蓝色点，对于d = c log n，我们可以在随机时间n<sup>2-1</sup>/O（log<sup>2</sup> c）或确定性时间n<sup>2 - 1/O（log 2 c）中</sup>为每个红色点找到一个（精确的）最近（或最远）蓝色邻居。这些改进了Alman和威廉姆斯（FOCS'15）的随机n<sup>2-1/O（c log 2 c）</sup>约束，并且还导致了用于稀疏CNF的更快的MAX-SAT算法。·离线近似最近（和最远）邻居：给定d维空间中的n个红色和n个蓝色点，我们可以在随机时间内找到dn+n<sup>2-Ω（ε1/3/log（1/ε））</sup>附近的每个红色点的（1+ε）近似最近（或最远）蓝色邻居。<sub></sub>这改进了Valiant（FOCS'12）的算法，其随机化时间接近dn+n<sup>2-Ω（ε）</sup>，这反过来又改进了先前基于局部敏感散列的方法。·线性阈值电路的SAT算法和下界：我们给出了AC<sup>0</sup> [m] o LTF LTF电路的一个可满足性算法，该电路底层的LTF门数为次二次方，其他层的门数为次指数，该算法在确定的2n-n<sup>ε</sup>时间内运行。<sup></sup>这严格地推广了威廉姆斯（STOC'14）的ACC<sup>0</sup>oLTF电路的SAT算法，并且还暗示了阈值电路的新的电路下界，改进了Kane和威廉姆斯（STOC'16）最近的门下界。对于次指数大小的MAJoAC<sub>0</sub> oLTF oAC<sub>0</sub> oLTF电路，我们给出了一个随机<sup>的2n-n</sup><sup>ε</sup>时间SAT算法，其中顶部MAJ门和中间LTF门的扇入时间为O（<sup>n6/5-δ</sup>）.
We design new polynomials for representing threshold functions in three different regimes: probabilistic polynomials of low degree, which need far less randomness than previous constructions, polynomial threshold functions (PTFs) with "nice" threshold behavior and degree almost as low as the probabilistic polynomials, and a new notion of probabilistic PTFs where we combine the above techniques to achieve even lower degree with similar "nice" threshold behavior. Utilizing these polynomial constructions, we design faster algorithms for a variety of problems: · Offline Hamming Nearest (and Furthest) Neighbors: Given n red and n blue points in d-dimensional Hamming space for d = c log n, we can find an (exact) nearest (or furthest) blue neighbor for every red point in randomized time n<sup>2-1</sup>/O(√clog<sup>2/3</sup> c) or deterministic time n<sup>2-1/O(c log2 c)</sup>. These improve on a randomized n<sup>2-1/O(c log2 c)</sup> bound by Alman and Williams (FOCS'15), and also lead to faster MAX-SAT algorithms for sparse CNFs. · Offline Approximate Nearest (and Furthest) Neighbors: Given n red and n blue points in d-dimensional ℓ<sub>1</sub> or Euclidean space, we can find a (1+ε)-approximate nearest (or furthest) blue neighbor for each red point in randomized time near dn+n<sup>2-Ω(ε1/3/log(1/ε))</sup>. This improves on an algorithm by Valiant (FOCS'12) with randomized time near dn+n<sup>2-Ω(√ε)</sup>, which in turn improves previous methods based on locality-sensitive hashing. · SAT Algorithms and Lower Bounds for Circuits With Linear Threshold Functions: We give a satisfiability algorithm for AC<sup>0</sup>[m] o LTF LTF circuits with a subquadratic number of LTF gates on the bottom layer, and a subexponential number of gates on the other layers, that runs in deterministic 2<sup>n-n</sup><sup>ε</sup> time. This strictly generalizes a SAT algorithm for ACC<sup>0</sup> oLTF circuits of subexponential size by Williams (STOC'14) and also implies new circuit lower bounds for threshold circuits, improving a recent gate lower bound of Kane and Williams (STOC'16). We also give a randomized 2<sup>n-n</sup><sup>ε</sup>-time SAT algorithm for subexponential-size MAJ o AC<sub>0</sub> oLTF o AC<sub>0</sub> oLTF circuits, where the top MAJ gate and middle LTF gates have O(n<sup>6/5-δ</sup>) fan-in.