More Like this

1. An Improved Line-Point Low-Degree Test

   Harsha, Prahladh; Kumar, Mrinal; Saptharishi, Ramprasad; Sudan, Madhu (October 2024, IEEE Press)

   We prove that the most natural low-degree test for polynomials over finite fields is “robust” in the high-error regime for linear-sized fields. Specifically we consider the “local” agreement of a function $$f:\mathbb{F}_{q}^{m}\rightarrow \mathbb{F}_{q}$$ from the space of degree-d polynomials, i.e., the expected agreement of the function from univariate degree-d polynomials over a randomly chosen line in $$\mathbb{F}_{q}^{m}$$, and prove that if this local agreement is $$\varepsilon\geq\Omega((d/q)^{\tau}))$$ for some fixed $$\tau > 0$$, then there is a global degree-d polynomial $$Q:\mathbb{F}_{q}^{m}\rightarrow \mathbb{F}_{q}$$ with agreement nearly $$\varepsilon$$ with $$f$$. This settles a long-standing open question in the area of low-degree testing, yielding an $O(d)$ -query robust test in the “high-error” regime (i.e., when $$\varepsilon < 1/2)$$. The previous results in this space either required $$\varepsilon > 1/2$$ (Polishchuk & Spielman, STOC 1994), or $$q=\Omega(d^{4})$$ (Arora & Sudan, Combinatorica 2003), orneeded to measure local distance on 2-dimensional “planes” rather than one-dimensional lines leading to $$\Omega(d^{2})$$ -query complexity (Raz & Safra, STOC 1997). Our analysis follows the spirit of most previous analyses in first analyzing the low-variable case $(m=O(1))$ and then “boot-strapping” to general multivariate settings. Our main technical novelty is a new analysis in the bivariate setting that exploits a previously known connection between multivariate factorization and finding (or testing) low-degree polynomials, in a non “black-box” manner. This connection was used roughly in a black-box manner in the work of Arora & Sudan — and we show that opening up this black box and making some delicate choices in the analysis leads to our essentially optimal analysis. A second contribution is a bootstrapping analysis which manages to lift analyses for $m=2$ directly to analyses for general $$m$$, where previous works needed to work with $m=3$ or $m=4$ — arguably this bootstrapping is significantly simpler than those in prior works. 

   more » « less
2. A deterministic near-linear time approximation scheme for geometric transportation

   https://doi.org/10.1109/FOCS57990.2023.00078  

   Fox, Emily; Lu, Jiashuai (November 2023, IEEE)

   Given a set of points $$P = (P^+ \sqcup P^-) \subset \mathbb{R}^d$$ for some constant $$d$$ and a supply function $$\mu:P\to \mathbb{R}$$ such that $$\mu(p) > 0~\forall p \in P^+$$, $$\mu(p) < 0~\forall p \in P^-$$, and $$\sum_{p\in P}{\mu(p)} = 0$$, the geometric transportation problem asks one to find a transportation map $$\tau: P^+\times P^-\to \mathbb{R}_{\ge 0}$$ such that $$\sum_{q\in P^-}{\tau(p, q)} = \mu(p)~\forall p \in P^+$$, $$\sum_{p\in P^+}{\tau(p, q)} = -\mu(q) \forall q \in P^-$$, and the weighted sum of Euclidean distances for the pairs $$\sum_{(p,q)\in P^+\times P^-}\tau(p, q)\cdot ||q-p||_2$$ is minimized. We present the first deterministic algorithm that computes, in near-linear time, a transportation map whose cost is within a $$(1 + \varepsilon)$$ factor of optimal. More precisely, our algorithm runs in $$O(n\varepsilon^{-(d+2)}\log^5{n}\log{\log{n}})$$ time for any constant $$\varepsilon > 0$$. While a randomized $$n\varepsilon^{-O(d)}\log^{O(d)}{n}$$ time algorithm for this problem was discovered in the last few years, all previously known deterministic $$(1 + \varepsilon)$$-approximation algorithms run in~$$\Omega(n^{3/2})$$ time. A similar situation existed for geometric bipartite matching, the special case of geometric transportation where all supplies are unit, until a deterministic $$n\varepsilon^{-O(d)}\log^{O(d)}{n}$$ time $$(1 + \varepsilon)$$-approximation algorithm was presented at STOC 2022. Surprisingly, our result is not only a generalization of the bipartite matching one to arbitrary instances of geometric transportation, but it also reduces the running time for all previously known $$(1 + \varepsilon)$$-approximation algorithms, randomized or deterministic, even for geometric bipartite matching. In particular, we give the first $$(1 + \varepsilon)$$-approximate deterministic algorithm for geometric bipartite matching and the first $$(1 + \varepsilon)$$-approximate deterministic or randomized algorithm for geometric transportation with no dependence on $$d$$ in the exponent of the running time's polylog. As an additional application of our main ideas, we also give the first randomized near-linear $$O(\varepsilon^{-2} m \log^{O(1)} n)$$ time $$(1 + \varepsilon)$$-approximation algorithm for the uncapacitated minimum cost flow (transshipment) problem in undirected graphs with arbitrary \emph{real} edge costs. 

   more » « less
3. A $$d^{1/2+o(1)}$$ Monotonicity Tester for Boolean Functions on $$d$$-Dimensional Hypergrids

   Hadley Black, Deeparnab Chakrabarty (November 2023, Annual Symposium on Foundations of Computer Science)

   Monotonicity testing of Boolean functions on the hypergrid, $$f:[n]^d \to \{0,1\}$$, is a classic topic in property testing. Determining the non-adaptive complexity of this problem is an important open question. For arbitrary $$n$$, [Black-Chakrabarty-Seshadhri, SODA 2020] describe a tester with query complexity $$\widetilde{O}(\varepsilon^{-4/3}d^{5/6})$$. This complexity is independent of $$n$$, but has a suboptimal dependence on $$d$$. Recently, [Braverman-Khot-Kindler-Minzer, ITCS 2023] and [Black-Chakrabarty-Seshadhri, STOC 2023] describe $$\widetilde{O}(\varepsilon^{-2} n^3\sqrt{d})$$ and $$\widetilde{O}(\varepsilon^{-2} n\sqrt{d})$$-query testers, respectively. These testers have an almost optimal dependence on $$d$$, but a suboptimal polynomial dependence on $$n$$. \smallskip In this paper, we describe a non-adaptive, one-sided monotonicity tester with query complexity $$O(\varepsilon^{-2} d^{1/2 + o(1)})$$, \emph{independent} of $$n$$. Up to the $$d^{o(1)}$$-factors, our result resolves the non-adaptive complexity of monotonicity testing for Boolean functions on hypergrids. The independence of $$n$$ yields a non-adaptive, one-sided $$O(\varepsilon^{-2} d^{1/2 + o(1)})$$-query monotonicity tester for Boolean functions $$f:\mathbb{R}^d \to \{0,1\}$$ associated with an arbitrary product measure. 

   more » « less
4. Low Degree Local Correction Over the Boolean Cube

   Amireddy, Prashanth; Behera, Amik Raj; Paraashar, Manaswi; Srinivasan, Srikanth; Sudan, Madhu (January 2025, Society for Industrial and Applied Mathematics)

   In this work, we show that the class of multivariate degree-d polynomials mapping {0,1}n to any Abelian group G is locally correctable with Õd((log n )d) queries for up to a fraction of errors approaching half the minimum distance of the underlying code. In particular, this result holds even for polynomials over the reals or the rationals, special cases that were previously not known. Further, we show that they are locally list correctable up to a fraction of errors approaching the minimum distance of the code. These results build on and extend the prior work of Amireddy, Behera, Paraashar, Srinivasan, and Sudan [1] (STOC 2024) who considered the case of linear polynomials (d = 1) and gave analogous results. Low-degree polynomials over the Boolean cube {0,1}n arise naturally in Boolean circuit complexity and learning theory, and our work furthers the study of their coding-theoretic properties. Extending the results of [1] from linear polynomials to higher-degree polynomials involves several new challenges and handling them gives us further insights into properties of low-degree polynomials over the Boolean cube. For local correction, we construct a set of points in the Boolean cube that lie between two exponentially close parallel hyperplanes and is moreover an interpolating set for degree-d polynomials. To show that the class of degree-d polynomials is list decodable up to the minimum distance, we stitch together results on anti-concentration of low-degree polynomials, the Sunflower lemma, and the Footprint bound for counting common zeroes of polynomials. Analyzing the local list corrector of [1] for higher degree polynomials involves understanding random restrictions of non-zero degree-d polynomials on a Hamming slice. In particular, we show that a simple random restriction process for reducing the dimension of the Boolean cube is a suitably good sampler for Hamming slices. Thus our exploration unearths several new techniques that are useful in understanding the combinatorial structure of low-degree polynomials over {0, 1}n. 

   more » « less
5. Low Degree Local Correction Over the Boolean Cube

   Amireddy, Prashanth; Behera, Amik Raj; Paraashar, Manaswi; Srinivasan, Srikanth; Sudan, Madhu (January 2025, Society for Industrial and Applied Mathematics)

   In this work, we show that the class of multivariate degree-d polynomials mapping {0,1}n to any Abelian group G is locally correctable with Õd((log n )d) queries for up to a fraction of errors approaching half the minimum distance of the underlying code. In particular, this result holds even for polynomials over the reals or the rationals, special cases that were previously not known. Further, we show that they are locally list correctable up to a fraction of errors approaching the minimum distance of the code. These results build on and extend the prior work of Amireddy, Behera, Paraashar, Srinivasan, and Sudan [1] (STOC 2024) who considered the case of linear polynomials (d = 1) and gave analogous results. Low-degree polynomials over the Boolean cube {0,1}n arise naturally in Boolean circuit complexity and learning theory, and our work furthers the study of their coding-theoretic properties. Extending the results of [1] from linear polynomials to higher-degree polynomials involves several new challenges and handling them gives us further insights into properties of low-degree polynomials over the Boolean cube. For local correction, we construct a set of points in the Boolean cube that lie between two exponentially close parallel hyperplanes and is moreover an interpolating set for degree-d polynomials. To show that the class of degree-d polynomials is list decodable up to the minimum distance, we stitch together results on anti-concentration of low-degree polynomials, the Sunflower lemma, and the Footprint bound for counting common zeroes of polynomials. Analyzing the local list corrector of [1] for higher degree polynomials involves understanding random restrictions of non-zero degree-d polynomials on a Hamming slice. In particular, we show that a simple random restriction process for reducing the dimension of the Boolean cube is a suitably good sampler for Hamming slices. Thus our exploration unearths several new techniques that are useful in understanding the combinatorial structure of low-degree polynomials over {0, 1}n. 

   more » « less