## 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 n^{3}/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 n^{2-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 n^{2-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 · t^{1-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 k^{1.5}n^{2}/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) 2^{n}(l-l/o(log mn)) time time.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015 |

Publisher | Association for Computing Machinery |

Pages | 218-230 |

Number of pages | 13 |

Edition | January |

ISBN (Electronic) | 9781611973747 |

DOIs | |

State | Published - 2015 |

Externally published | Yes |

Event | 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015 - San Diego, United States Duration: Jan 4 2015 → Jan 6 2015 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Number | January |

Volume | 2015-January |

### Other

Other | 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015 |
---|---|

Country/Territory | United States |

City | San Diego |

Period | 1/4/15 → 1/6/15 |

## All Science Journal Classification (ASJC) codes

- Software
- General Mathematics