More Like this

1. Property testing with online adversaries

   Ben-Eliezer, Omri; Kelman, Esty; Meir, Uri; Raskhodnikova, Sofya (January 2024, Proceedings of the 14th Innovations in Theoretical Computer Science Conference (ITCS))

   The online manipulation-resilient testing model, proposed by Kalemaj, Raskhodnikova and Varma (ITCS 2022 and Theory of Computing 2023), studies property testing in situations where access to the input degrades continuously and adversarially. Specifically, after each query made by the tester is answered, the adversary can intervene and either erase or corrupt t data points. In this work, we investigate a more nuanced version of the online model in order to overcome old and new impossibility results for the original model. We start by presenting an optimal tester for linearity and a lower bound for low-degree testing of Boolean functions in the original model. We overcome the lower bound by allowing batch queries, where the tester gets a group of queries answered between manipulations of the data. Our batch size is small enough so that function values for a single batch on their own give no information about whether the function is of low degree. Finally, to overcome the impossibility results of Kalemaj et al. for sortedness and the Lipschitz property of sequences, we extend the model to include t < 1, i.e., adversaries that make less than one erasure per query. For sortedness, we characterize the rate of erasures for which online testing can be performed, exhibiting a sharp transition from optimal query complexity to impossibility of testability (with any number of queries). Our online tester works for a general class of local properties of sequences. One feature of our results is that we get new (and in some cases, simpler) optimal algorithms for several properties in the standard property testing model. 

   more » « less
2. On Optimal Testing of Linearity

   Arora, Vipul; Kelman, Esty; Meir, Uri (January 2025, SIAM Symposium on Simplicity in Algorithms (SOSA))

   Linearity testing has been a focal problem in property testing of functions. We combine different known techniques and observations about Linearity testing in order to resolve two recent versions of this task. First, we focus on the online-manipulation-resilient model introduced by Kalemaj, Raskhodnikova and Varma (Theory of Computing 2023). In this model, up to t data entries are adversarially manipulated after each query is answered. Ben-Eliezer, Kelman, Meir, and Raskhodnikova (ITCS 2024) showed an asymptotically optimal Linearity tester that is resilient to t manipulations per query, but fails if t is too large. We simplify their analysis for the regime of small t, and for larger values of t we instead use sample-based testers, as defined by Goldreich and Ron (ACM Transactions on Computation Theory 2016). A key observation is that sample-based testing is resilient to online manipulations but still achieves optimal query complexity for Linearity when t is large. We complement our result by showing that when t is very large any reasonable property, and in particular Linearity, cannot be tested at all. Second, we consider Linearity over the reals with proximity parameter ε. Fleming and Yoshida (ITCS 2020) gave a tester using O(1/ε · log(1/ε)) queries. We simplify their algorithms and modify the analysis accordingly, showing an optimal tester that only uses O(1/ε) queries. This modification works for the low-degree testers presented in Arora, Bhattacharyya, Fleming, Kelman, and Yoshida (SODA 2023) as well, resulting in optimal testers for degree-d polynomials, for any constant d. 

   more » « less
3. On Optimal Testing of Linearity

   Arora, Vipul; Kelman, Esty; Meir, Uri (January 2025, SIAM Symposium on Simplicity in Algorithms)

   Linearity testing has been a focal problem in property testing of functions. We combine different known techniques and observations about Linearity testing in order to resolve two recent versions of this task. First, we focus on the online-manipulation-resilient model introduced by Kalemaj, Raskhodnikova and Varma (Theory of Computing 2023). In this model, up to t data entries are adversarially manipulated after each query is answered. Ben-Eliezer, Kelman, Meir, and Raskhodnikova (ITCS 2024) showed an asymptotically optimal Linearity tester that is resilient to t manipulations per query, but fails if t is too large. We simplify their analysis for the regime of small t, and for larger values of t we instead use sample-based testers, as defined by Goldreich and Ron (ACM Transactions on Computation Theory 2016). A key observation is that sample-based testing is resilient to online manipulations but still achieves optimal query complexity for Linearity when t is large. We complement our result by showing that when t is very large any reasonable property, and in particular Linearity, cannot be tested at all. Second, we consider Linearity over the reals with proximity parameter ε. Fleming and Yoshida (ITCS 2020) gave a tester using O (1/ε · log (1/ε)) queries. We simplify their algorithms and modify the analysis accordingly, showing an optimal tester that only uses O (1/ε) queries. This modification works for the low-degree testers presented in Arora, Bhattacharyya, Fleming, Kelman, and Yoshida (SODA 2023) as well, resulting in optimal testers for degree-d polynomials, for any constant d. 

   more » « less
4. Network Modeling and Analysis of COVID-19 Testing Strategies

   https://doi.org/10.1109/EMBC46164.2021.9629754  

   Zhang, Siqi; Ventura, Marta J.; Yang, Hui (November 2021, 2021 43rd Annual International Conference of the IEEE Engineering in Medicine & Biology Society (EMBC))

   The COVID-19 preparedness plans by the Centers for Disease Control and Prevention strongly underscores the need for efficient and effective testing strategies. This, in turn, calls upon the design and development of statistical sampling and testing of COVID-19 strategies. However, the evaluation of operational details requires a detailed representation of human behaviors in epidemic simulation models. Traditional epidemic simulations are mainly based upon system dynamic models, which use differential equations to study macro-level and aggregated behaviors of population subgroups. As such, individual behaviors (e.g., personal protection, commute conditions, social patterns) can’t be adequately modeled and tracked for the evaluation of health policies and action strategies. Therefore, this paper presents a network-based simulation model to optimize COVID-19 testing strategies for effective identifications of virus carriers in a spatial area. Specifically, we design a data-driven risk scoring system for statistical sampling and testing of COVID-19. This system collects real-time data from simulated networked behaviors of individuals in the spatial network to support decision-making during the virus spread process. Experimental results showed that this framework has superior performance in optimizing COVID-19 testing decisions and effectively identifying virus carriers from the population. 

   more » « less
5. Jespipe: A Plugin-Based, Open MPI Framework for Adversarial Machine Learning Analysis

   https://doi.org/10.1109/BigData52589.2021.9671385  

   Alemany, Sheila; Nucciarone, Jason; Pissinou, Niki (December 2021, 2021 IEEE International Conference on Big Data (Big Data))

   Research is increasingly showing the tremendous vulnerability in machine learning models to seemingly undetectable adversarial inputs. One of the current limitations in adversarial machine learning research is the incredibly time-consuming testing of novel defenses against various attacks and across multiple datasets, even with high computing power. To address this limitation, we have developed Jespipe as a new plugin-based, parallel-by-design Open MPI framework that aids in evaluating the robustness of machine learning models. The plugin-based nature of this framework enables researchers to specify any pre-training data manipulations, machine learning models, adversarial models, and analysis or visualization metrics with their input Python files. Because this framework is plugin-based, a researcher can easily incorporate model implementations using popular deep learning libraries such as PyTorch, Keras, TensorFlow, Theano, or MXNet, or adversarial robustness tools such as IBM’s Adversarial Robustness Toolbox or Foolbox. The parallelized nature of this framework also enables researchers to evaluate various learning or attack models with multiple datasets simultaneously by specifying all the models and datasets they would like to test with our XML control file template. Overall, Jespipe shows promising results by reducing latency in adversarial machine learning algorithm development and testing compared to traditional Jupyter notebook workflows. 

   more » « less