Source author record

Josh Alman

Josh Alman appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Computational Complexity Data Structures and Algorithms math.CO math.CA

Catalog footprint

What is connected

6works

4topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2024arXiv

Tensor Ranks and the Fine-Grained Complexity of Dynamic Programming

Generalizing work of Künnemann, Paturi, and Schneider [ICALP 2017], we study a wide class of high-dimensional dynamic programming (DP) problems in which one must find the shortest path between two points in a high-dimensional grid given a tensor of transition costs between nodes in the grid. This captures many classical problems which are solved using DP such as the knapsack problem, the airplane refueling problem, and the minimal-weight polygon triangulation problem. We observe that for many of these problems, the tensor naturally has low tensor rank or low slice rank. We then give new algorithms and a web of fine-grained reductions to tightly determine the complexity of these problems. For instance, we show that a polynomial speedup over the DP algorithm is possible when the tensor rank is a constant or the slice rank is 1, but that such a speedup is impossible if the tensor rank is slightly super-constant (assuming SETH) or the slice rank is at least 3 (assuming the APSP conjecture). We find that this characterizes the known complexities for many of these problems, and in some cases leads to new faster algorithms.

preprint2022arXiv

Optimal-Degree Polynomial Approximations for Exponentials and Gaussian Kernel Density Estimation

For any real numbers $B \ge 1$ and $δ\in (0, 1)$ and function $f: [0, B] \rightarrow \mathbb{R}$, let $d_{B; δ} (f) \in \mathbb{Z}_{> 0}$ denote the minimum degree of a polynomial $p(x)$ satisfying $\sup_{x \in [0, B]} \big| p(x) - f(x) \big| < δ$. In this paper, we provide precise asymptotics for $d_{B; δ} (e^{-x})$ and $d_{B; δ} (e^{x})$ in terms of both $B$ and $δ$, improving both the previously known upper bounds and lower bounds. In particular, we show $$d_{B; δ} (e^{-x}) = Θ\left( \max \left\{ \sqrt{B \log(δ^{-1})}, \frac{\log(δ^{-1}) }{ \log(B^{-1} \log(δ^{-1}))} \right\}\right), \text{ and}$$ $$d_{B; δ} (e^{x}) = Θ\left( \max \left\{ B, \frac{\log(δ^{-1}) }{ \log(B^{-1} \log(δ^{-1}))} \right\}\right).$$ Polynomial approximations for $e^{-x}$ and $e^x$ have applications to the design of algorithms for many problems, and our degree bounds show both the power and limitations of these algorithms. We focus in particular on the Batch Gaussian Kernel Density Estimation problem for $n$ sample points in $Θ(\log n)$ dimensions with error $δ= n^{-Θ(1)}$. We show that the running time one can achieve depends on the square of the diameter of the point set, $B$, with a transition at $B = Θ(\log n)$ mirroring the corresponding transition in $d_{B; δ} (e^{-x})$: - When $B=o(\log n)$, we give the first algorithm running in time $n^{1 + o(1)}$. - When $B = κ\log n$ for a small constant $κ>0$, we give an algorithm running in time $n^{1 + O(\log \log κ^{-1} /\log κ^{-1})}$. The $\log \log κ^{-1} /\log κ^{-1}$ term in the exponent comes from analyzing the behavior of the leading constant in our computation of $d_{B; δ} (e^{-x})$. - When $B = ω(\log n)$, we show that time $n^{2 - o(1)}$ is necessary assuming SETH.

preprint2022arXiv

Parameterized Sensitivity Oracles and Dynamic Algorithms using Exterior Algebras

We design the first efficient sensitivity oracles and dynamic algorithms for a variety of parameterized problems. Our main approach is to modify the algebraic coding technique from static parameterized algorithm design, which had not previously been used in a dynamic context. We particularly build off of the `extensor coding' method of Brand, Dell and Husfeldt [STOC'18], employing properties of the exterior algebra over different fields. For the $k$-Path detection problem for directed graphs, it is known that no efficient dynamic algorithm exists (under popular assumptions from fine-grained complexity). We circumvent this by designing an efficient sensitivity oracle, which preprocesses a directed graph on $n$ vertices in $2^k poly(k) n^{ω+o(1)}$ time, such that, given $\ell$ updates (mixing edge insertions and deletions, and vertex deletions) to that input graph, it can decide in time $\ell^2 2^kpoly(k)$ and with high probability, whether the updated graph contains a path of length $k$. We also give a deterministic sensitivity oracle requiring $4^k poly(k) n^{ω+o(1)}$ preprocessing time and $\ell^2 2^{ωk + o(k)}$ query time, and obtain a randomized sensitivity oracle for the task of approximately counting the number of $k$-paths. For $k$-Path detection in undirected graphs, we obtain a randomized sensitivity oracle with $O(1.66^k n^3)$ preprocessing time and $O(\ell^3 1.66^k)$ query time, and a better bound for undirected bipartite graphs. In addition, we present the first fully dynamic algorithms for a variety of problems: $k$-Partial Cover, $m$-Set $k$-Packing, $t$-Dominating Set, $d$-Dimensional $k$-Matching, and Exact $k$-Partial Cover. For example, for $k$-Partial Cover we show a randomized dynamic algorithm with $2^k poly(k)polylog(n)$ update time, and a deterministic dynamic algorithm with $4^kpoly(k)polylog(n)$ update time.

preprint2021arXiv

Kronecker Products, Low-Depth Circuits, and Matrix Rigidity

For a matrix $M$ and a positive integer $r$, the rank $r$ rigidity of $M$ is the smallest number of entries of $M$ which one must change to make its rank at most $r$. There are many known applications of rigidity lower bounds to a variety of areas in complexity theory, but fewer known applications of rigidity upper bounds. In this paper, we use rigidity upper bounds to prove new upper bounds in a few different models of computation. Our results include: $\bullet$ For any $d> 1$, and over any field $\mathbb{F}$, the $N \times N$ Walsh-Hadamard transform has a depth-$d$ linear circuit of size $O(d \cdot N^{1 + 0.96/d})$. This circumvents a known lower bound of $Ω(d \cdot N^{1 + 1/d})$ for circuits with bounded coefficients over $\mathbb{C}$ by Pudlák (2000), by using coefficients of magnitude polynomial in $N$. Our construction also generalizes to linear transformations given by a Kronecker power of any fixed $2 \times 2$ matrix. $\bullet$ The $N \times N$ Walsh-Hadamard transform has a linear circuit of size $\leq (1.81 + o(1)) N \log_2 N$, improving on the bound of $\approx 1.88 N \log_2 N$ which one obtains from the standard fast Walsh-Hadamard transform. $\bullet$ A new rigidity upper bound, showing that the following classes of matrices are not rigid enough to prove circuit lower bounds using Valiant's approach: $-$ for any field $\mathbb{F}$ and any function $f : \{0,1\}^n \to \mathbb{F}$, the matrix $V_f \in \mathbb{F}^{2^n \times 2^n}$ given by, for any $x,y \in \{0,1\}^n$, $V_f[x,y] = f(x \wedge y)$, and $-$ for any field $\mathbb{F}$ and any fixed-size matrices $M_1, \ldots, M_n \in \mathbb{F}^{q \times q}$, the Kronecker product $M_1 \otimes M_2 \otimes \cdots \otimes M_n$. This generalizes recent results on non-rigidity, using a simpler approach which avoids needing the polynomial method.

preprint2016arXiv

Polynomial Representations of Threshold Functions and Algorithmic Applications

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: $\bullet$ 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^{2-1/O(\sqrt{c}\log^{2/3}c)}$ or deterministic time $n^{2-1/O(c\log^2c)}$. These also lead to faster MAX-SAT algorithms for sparse CNFs. $\bullet$ Offline Approximate Nearest (and Furthest) Neighbors: Given $n$ red and $n$ blue points in $d$-dimensional $\ell_1$ or Euclidean space, we can find a $(1+ε)$-approximate nearest (or furthest) blue neighbor for each red point in randomized time near $dn+n^{2-Ω(ε^{1/3}/\log(1/ε))}$. $\bullet$ SAT Algorithms and Lower Bounds for Circuits With Linear Threshold Functions: We give a satisfiability algorithm for $AC^0[m]\circ LTF\circ LTF$ circuits with a subquadratic number of linear threshold gates on the bottom layer, and a subexponential number of gates on the other layers, that runs in deterministic $2^{n-n^ε}$ time. This also implies new circuit lower bounds for threshold circuits. We also give a randomized $2^{n-n^ε}$-time SAT algorithm for subexponential-size $MAJ\circ AC^0\circ LTF\circ AC^0\circ LTF$ circuits, where the top $MAJ$ gate and middle $LTF$ gates have $O(n^{6/5-δ})$ fan-in.

preprint2015arXiv

Probabilistic Polynomials and Hamming Nearest Neighbors

We show how to compute any symmetric Boolean function on $n$ variables over any field (as well as the integers) with a probabilistic polynomial of degree $O(\sqrt{n \log(1/ε)})$ and error at most $ε$. The degree dependence on $n$ and $ε$ is optimal, matching a lower bound of Razborov (1987) and Smolensky (1987) for the MAJORITY function. The proof is constructive: a low-degree polynomial can be efficiently sampled from the distribution. This polynomial construction is combined with other algebraic ideas to give the first subquadratic time algorithm for computing a (worst-case) batch of Hamming distances in superlogarithmic dimensions, exactly. To illustrate, let $c(n) : \mathbb{N} \rightarrow \mathbb{N}$. Suppose we are given a database $D$ of $n$ vectors in $\{0,1\}^{c(n) \log n}$ and a collection of $n$ query vectors $Q$ in the same dimension. For all $u \in Q$, we wish to compute a $v \in D$ with minimum Hamming distance from $u$. We solve this problem in $n^{2-1/O(c(n) \log^2 c(n))}$ randomized time. Hence, the problem is in "truly subquadratic" time for $O(\log n)$ dimensions, and in subquadratic time for $d = o((\log^2 n)/(\log \log n)^2)$. We apply the algorithm to computing pairs with maximum inner product, closest pair in $\ell_1$ for vectors with bounded integer entries, and pairs with maximum Jaccard coefficients.