More applications of the polynomial method to algorithm design

Amir Abboud, Ryan Williams, Huacheng Yu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

101 Scopus citations

Abstract

In low-depth circuit complexity, the polynomial method is a way to prove lower bounds by translating weak circuits into low-degree polynomials, then analyzing properties of these polynomials. Recently, this method found an application to algorithm design: Williams (STOC 2014) used it to compute all-pairs shortest paths in n3/2ω√log n) time on dense n-node graphs. In this paper, we extend this methodology to solve a number of problems in combinatorial pattern matching and Boolean algebra, considerably faster than previously known methods. First, we give an algorithm for Boolean Orthogonal Detection, which is to detect among two sets A, B ⊆ {0, 1 }d of size n if there is an x ∈ A and y ∈ B such that (a;, y) = 0. For vectors of dimension d = c(n) log n, we solve Boolean Orthogonal Detection in n2-1/o(logc(n)) tjme by a Monte Carlo randomized algorithm. We apply this as a subroutine in several other new algorithms: In Batch Partial Match, we are given n query strings from from {0,1,∗}c(n)log n (∗ is a "don't care"), n strings from {0, 1}c(n)log n to determine for each query whether or not there is a string matching the query. We solve this problem in n2-1/o(log c(c)) time by a Monte Carlo randomized algorithm. Let t ≤ v be integers. Given a DNF F on clogt variables with t terms, and v arbitrary assignments on the variables, F can be evaluated on all v assignments in v · t1-1/o(log n) time with high probability. There is a randomized algorithm that solves the Longest Common Substring with don't cares problem on two strings of length n in k1.5n2/2ω(√log n) time. Given two strings S, T of length n, there is a randomized algorithm that computes the length of the longest substring of S that has Edit-Distance less than k to a substring of T in Symmetric Boolean Constraint Satisfaction Problems (CSPs) with n variables and m constraints are solvable in poly(m) 2n(l-l/o(log mn)) time time.

Original languageEnglish (US)
Title of host publicationProceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015
PublisherAssociation for Computing Machinery
Pages218-230
Number of pages13
EditionJanuary
ISBN (Electronic)9781611973747
DOIs
StatePublished - 2015
Externally publishedYes
Event26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015 - San Diego, United States
Duration: Jan 4 2015Jan 6 2015

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
NumberJanuary
Volume2015-January

Other

Other26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015
Country/TerritoryUnited States
CitySan Diego
Period1/4/151/6/15

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'More applications of the polynomial method to algorithm design'. Together they form a unique fingerprint.

Cite this