skip to main content

Explore Research Products in the NSF-PAR

Title: Low-degree testing over grids
We study the question of local testability of low (constant) degree functions from a product domain 𝒮_1 × … × 𝒮_n to a field 𝔽, where 𝒮_i ⊆ 𝔽 can be arbitrary constant sized sets. We show that this family is locally testable when the grid is "symmetric". That is, if 𝒮_i = 𝒮 for all i, there is a probabilistic algorithm using constantly many queries that distinguishes whether f has a polynomial representation of degree at most d or is Ω(1)-far from having this property. In contrast, we show that there exist asymmetric grids with |𝒮_1| = ⋯ = |𝒮_n| = 3 for which testing requires ω_n(1) queries, thereby establishing that even in the context of polynomials, local testing depends on the structure of the domain and not just the distance of the underlying code. The low-degree testing problem has been studied extensively over the years and a wide variety of tools have been applied to propose and analyze tests. Our work introduces yet another new connection in this rich field, by building low-degree tests out of tests for "junta-degrees". A function f:𝒮_1 × ⋯ × 𝒮_n → 𝒢, for an abelian group 𝒢 is said to be a junta-degree-d function if it is a sum of d-juntas. We derive our low-degree test by giving a new local test for junta-degree-d functions. For the analysis of our tests, we deduce a small-set expansion theorem for spherical/hamming noise over large grids, which may be of independent interest.  more » « less
Award ID(s):
2152413
NSF-PAR ID:
10484391
Author(s) / Creator(s):
; ;
Editor(s):
Megow, Nicole; Smith, Adam
Publisher / Repository:
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Date Published:
Journal Name:
Proceedings in Informatics (LIPIcs):Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Subject(s) / Keyword(s):
["Property testing","Low-degree testing","Small-set expansion","Local testing","Theory of computation → Probabilistic computation"]
Format(s):
Medium: X
Location:
Atlanta, GA, USA
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ( , Theory of computing)
    null (Ed.)
    The approximate degree of a Boolean function f is the least degree of a real polynomial that approximates f pointwise to error at most 1/3. The approximate degree of f is known to be a lower bound on the quantum query complexity of f (Beals et al., FOCS 1998 and J. ACM 2001). We find tight or nearly tight bounds on the approximate degree and quantum query complexities of several basic functions. Specifically, we show the following. k-Distinctness: For any constant k, the approximate degree and quantum query complexity of the k-distinctness function is Ω(n3/4−1/(2k)). This is nearly tight for large k, as Belovs (FOCS 2012) has shown that for any constant k, the approximate degree and quantum query complexity of k-distinctness is O(n3/4−1/(2k+2−4)). Image size testing: The approximate degree and quantum query complexity of testing the size of the image of a function [n]→[n] is Ω~(n1/2). This proves a conjecture of Ambainis et al. (SODA 2016), and it implies tight lower bounds on the approximate degree and quantum query complexity of the following natural problems. k-Junta testing: A tight Ω~(k1/2) lower bound for k-junta testing, answering the main open question of Ambainis et al. (SODA 2016). Statistical distance from uniform: A tight Ω~(n1/2) lower bound for approximating the statistical distance of a distribution from uniform, answering the main question left open by Bravyi et al. (STACS 2010 and IEEE Trans. Inf. Theory 2011). Shannon entropy: A tight Ω~(n1/2) lower bound for approximating Shannon entropy up to a certain additive constant, answering a question of Li and Wu (2017). Surjectivity: The approximate degree of the surjectivity function is Ω~(n3/4). The best prior lower bound was Ω(n2/3). Our result matches an upper bound of O~(n3/4) due to Sherstov (STOC 2018), which we reprove using different techniques. The quantum query complexity of this function is known to be Θ(n) (Beame and Machmouchi, Quantum Inf. Comput. 2012 and Sherstov, FOCS 2015). Our upper bound for surjectivity introduces new techniques for approximating Boolean functions by low-degree polynomials. Our lower bounds are proved by significantly refining techniques recently introduced by Bun and Thaler (FOCS 2017). 
    more » « less
  2. ; ; ( , Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020)
    We design a nonadaptive algorithm that, given a Boolean function f: {0, 1}^n → {0, 1} which is α-far from monotone, makes poly(n, 1/α) queries and returns an estimate that, with high probability, is an O-tilde(\sqrt{n})-approximation to the distance of f to monotonicity. Furthermore, we show that for any constant k > 0, approximating the distance to monotonicity up to n^(1/2−k)-factor requires 2^{n^k} nonadaptive queries, thereby ruling out a poly(n, 1/α)-query nonadaptive algorithm for such approximations. This answers a question of Seshadhri (Property Testing Review, 2014) for the case of nonadaptive algorithms. Approximating the distance to a property is closely related to tolerantly testing that property. Our lower bound stands in contrast to standard (non-tolerant) testing of monotonicity that can be done nonadaptively with O-tilde(n/ε^2) queries. We obtain our lower bound by proving an analogous bound for erasure-resilient testers. An α-erasure-resilient tester for a desired property gets oracle access to a function that has at most an α fraction of values erased. The tester has to accept (with probability at least 2/3) if the erasures can be filled in to ensure that the resulting function has the property and to reject (with probability at least 2/3) if every completion of erasures results in a function that is ε-far from having the property. Our method yields the same lower bounds for unateness and being a k-junta. These lower bounds improve exponentially on the existing lower bounds for these properties. 
    more » « less
  3. ; ; ; ; ( , ITCS)
    A Boolean {\em $k$-monotone} function defined over a finite poset domain ${\cal D}$ alternates between the values $0$ and $1$ at most $k$ times on any ascending chain in ${\cal D}$. Therefore, $k$-monotone functions are natural generalizations of the classical {\em monotone} functions, which are the {\em $1$-monotone} functions. Motivated by the recent interest in $k$-monotone functions in the context of circuit complexity and learning theory, and by the central role that monotonicity testing plays in the context of property testing, we initiate a systematic study of $k$-monotone functions, in the property testing model. In this model, the goal is to distinguish functions that are $k$-monotone (or are close to being $k$-monotone) from functions that are far from being $k$-monotone. Our results include the following: \begin{enumerate} \item We demonstrate a separation between testing $k$-monotonicity and testing monotonicity, on the hypercube domain $\{0,1\}^d$, for $k\geq 3$; \item We demonstrate a separation between testing and learning on $\{0,1\}^d$, for $k=\omega(\log d)$: testing $k$-monotonicity can be performed with $2^{O(\sqrt d \cdot \log d\cdot \log{1/\eps})}$ queries, while learning $k$-monotone functions requires $2^{\Omega(k\cdot \sqrt d\cdot{1/\eps})}$ queries (Blais et al. (RANDOM 2015)). \item We present a tolerant test for functions $f\colon[n]^d\to \{0,1\}$ with complexity independent of $n$, which makes progress on a problem left open by Berman et al. (STOC 2014). \end{enumerate} Our techniques exploit the testing-by-learning paradigm, use novel applications of Fourier analysis on the grid $[n]^d$, and draw connections to distribution testing techniques. 
    more » « less
  4. ; ; ; ; ( , Leibniz international proceedings in informatics)
    Bojanczyk, Mikolaj ; Merelli, Emanuela ; Woodruff, David P. (Ed.)
    We continue a line of work on extracting random bits from weak sources that are generated by simple processes. We focus on the model of locally samplable sources, where each bit in the source depends on a small number of (hidden) uniformly random input bits. Also known as local sources, this model was introduced by De and Watson (TOCT 2012) and Viola (SICOMP 2014), and is closely related to sources generated by AC⁰ circuits and bounded-width branching programs. In particular, extractors for local sources also work for sources generated by these classical computational models. Despite being introduced a decade ago, little progress has been made on improving the entropy requirement for extracting from local sources. The current best explicit extractors require entropy n^{1/2}, and follow via a reduction to affine extractors. To start, we prove a barrier showing that one cannot hope to improve this entropy requirement via a black-box reduction of this form. In particular, new techniques are needed. In our main result, we seek to answer whether low-degree polynomials (over 𝔽₂) hold potential for breaking this barrier. We answer this question in the positive, and fully characterize the power of low-degree polynomials as extractors for local sources. More precisely, we show that a random degree r polynomial is a low-error extractor for n-bit local sources with min-entropy Ω(r(nlog n)^{1/r}), and we show that this is tight. Our result leverages several new ingredients, which may be of independent interest. Our existential result relies on a new reduction from local sources to a more structured family, known as local non-oblivious bit-fixing sources. To show its tightness, we prove a "local version" of a structural result by Cohen and Tal (RANDOM 2015), which relies on a new "low-weight" Chevalley-Warning theorem. 
    more » « less
  5. ; ; ; ; ; ( , Zenodo)

    This dataset includes multiple fields: (i) files for monthly and annual fields for the max curl line and the zero curl line at 0.1 degree longitudinal resolutions; (ii) files for monthly and annual GS path obtained from Altimetry and originally processed by Andres (2016) at 0.1 degree longitudinal resolution. The maximum curl line (MCL) and the zero curl line (ZCL) calculations are briefly described here and are based on the original wind data (at 1.25 x 1.25 degree) provided by the Japanese reanalysis (JRA-55; Kobayashi et al., 2015) and available at https://zenodo.org/record/8200832 (Gifford et al. 2023). For details see Gifford, 2023. 

    The wind stress curl (WSC) fields used for the MCL and ZCL calculations extend from 80W to 45W and 30N to 45N at the 1.25 by 1.25-degree resolution.  The MCL is defined as the maximum WSC values greater than zero within the domain per 1.25 degree longitude. As such, it is a function of longitude and is not a constant WSC value unlike the zero contour. High wind stress curl values that occurred near the coast were not included within this calculation. After MCL at the 1.25 resolution was obtained the line was smoothed with a gaussian smoothing and interpolated on to a 0.1 longitudinal resolution. The smoothed MCL lines at 0.1 degree resolution are provided in separate files for monthly and annual averages (2 files). Similarly, 2 other files (monthly and annual) are provided for the ZCL.    

    Like the MCL, the ZCL is a line derived from 1.25 degree longitude throughout the domain under the condition that it's the line of zero WSC. The ZCL is constant at 0 and does not vary spatially like the MCL. If there are more than one location of zero curl for a given longitude the first location south of the MCL is selected. Similar to the MCL, the ZCL was smoothed with a gaussian smoothing and interpolated on to a 0.1 longitudinal resolution.   

    The above files span the years from 1980 through 2019. So, the monthly files have 480 months starting January 1980, and the annual files have 40 years of data. The files are organized with each row being a new time step and each column being a different longitude. Therefore, the monthly MCL and ZCL files are each 480 x 351 for the 0.1 resolution data. Similarly, the annual files are 40 x 351 for the 0.1 degree resolution data.  

    Note that the monthly MCLs and ZCLs are obtained from the monthly wind-stress curl fields. The annual MCLs and ZCLs are obtained from the annual wind-stress curl fields.

    Since the monthly curl fields preserves more atmospheric mesoscales than the annual curl fields, the 12-month average of the monthly MCLs and ZCLs will not match with the annual MCLs and ZCLs derived from the annual curl field.  The annual MCLs and ZCLs provided here are obtained from the annual curl fields and representative metrics of the wind forcing on an annual time-scale. 

    Furthermore, the monthly Gulf Stream axis path (25 cm isoheight from Altimeter, reprocessed by Andres (2016) technique) from 1993 through 2019 have been made available here. A total of 324 monthly paths of the Gulf Stream are tabulated. In addition, the annual GS paths for these 27 years (1993-2019) of altimetry era have been put together for ease of use. The monthly Gulf Stream paths have been resampled and reprocessed for uniqueness at every 0.1 degree longitude from 75W to 50W and smoothed with a 100 km (10 point) running average via matlab. The uniqueness has been achieved by using Consolidator algorithm (D’Errico, 2023). 

    Each monthly or annual GS path has 251 points between 75W to 50W at 0.1 degree resolution.  

    Please contact igifford@earth.miami.edu for any queries. {"references": ["Andres, M., 2016. On the recent destabilization of the Gulf Stream path downstream of Cape Hatteras. Geophysical Research Letters, 43(18), 9836-9842.", "D'Errico, J., 2023. Consolidator (https://www.mathworks.com/matlabcentral/fileexchange/ 8354-consolidator), MATLAB Central File Exchange. Retrieved June 17, 2023.", "Gifford, Ian. H., 2023. The Synchronicity of the Gulf Stream Free Jet and the Wind Induced Cyclonic Vorticity Pool. MS Thesis, University of Massachusetts Dartmouth. 75pp.", "Gifford, Ian, H., Avijit Gangopadhyay, Magdalena Andres, Glen Gawarkiewicz, Hilde Oliver, Adrienne Silver, 2023. Wind Stress, Wind Stress Curl, and Upwelling Velocities in the Northwest Atlantic (80-45W, 30-45N) during 1980-2019, https://zenodo.org/record/8200832.", "Kobayashi, S., Ota, Y., Harada, Y., Ebita, A., Moriya, M., Onoda, H., Onogi, K., Kamahori, H., Kobayashi, C., Endo, H. and Miyaoka, K., 2015. The JRA-55 reanalysis: General specifications and basic characteristics.\u202fJournal of the Meteorological Society of Japan. Ser. II,\u202f93(1), pp.5-48. Kobayashi, S., Ota, Y., Harada, Y., Ebita, A., Moriya, M., Onoda, H., Onogi, K., Kamahori, H., Kobayashi, C., Endo, H. and Miyaoka, K., 2015. The JRA-55 reanalysis: General specifications and basic characteristics.\u202fJournal of the Meteorological Society of Japan. Ser. II,\u202f93(1), pp.5-48."]} 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email