Search

We investigate algorithms for testing whether an image is connected. Given a proximity parameter ϵ ∈ (0 , 1) and query access to a black-and-white image represented by an n × n matrix of Boolean pixel values, a (1-sided error) connectedness tester accepts if the image is connected and rejects with probability at least 2/3 if the image is ϵ -far from connected. We show that connectedness can be tested nonadaptively with O (1 ϵ 2 ) queries and adaptively with O (1 ϵ 3 / 2 log 1 ϵ ) queries. The best connectedness tester to date, by Berman, Raskhodnikova, and Yaroslavtsev (STOC 2014) had query complexity O (1 ϵ 2 log 1 ϵ) and was adaptive. We also prove that every nonadaptive, 1-sided error tester for connectedness must make Ω (1 ϵ log 1 ϵ) queries. [ABSTRACT FROM AUTHOR]

A graph G$$ G $$ on n$$ n $$ vertices is ε$$ \varepsilon $$‐far from property 풫 if one should add/delete at least εn2$$ \varepsilon {n}^2 $$ edges to turn G$$ G $$ into a graph satisfying 풫. A distance estimator for 풫 is an algorithm that given G$$ G $$ and α,ε>0$$ \alpha, \varepsilon >0 $$ distinguishes between the case that G$$ G $$ is (α−ε)$$ \left(\alpha -\varepsilon \right) $$‐close to 풫 and the case that G$$ G $$ is α$$ \alpha $$‐far from 풫. If 풫 has a distance estimator whose query complexity depends only on ε$$ \varepsilon $$, then 풫 is said to be estimable. Every estimable property is clearly also testable, since testing corresponds to estimating with α=ε$$ \alpha =\varepsilon $$. A central result in the area of property testing is the Fischer–Newman theorem, stating that an inverse statement also holds, that is, that every testable graph property is in fact estimable. The proof of Fischer and Newman was highly ineffective, since it incurred a tower‐type loss when transforming a testing algorithm for 풫 into a distance estimator. This raised the natural problem, studied recently by Fiat–Ron and by Hoppen–Kohayakawa–Lang–Lefmann–Stagni, whether one can find a transformation with a polynomial loss. We obtain the following results. 1.We show that if 풫 is hereditary, then one can turn a tester for 풫 into a distance estimator with an exponential loss. This is an exponential improvement over the result of Hoppen et al., who obtained a transformation with a double exponential loss.2.We show that for every 풫, one can turn a testing algorithm for 풫 into a distance estimator with a double exponential loss. This improves over the transformation of Fischer–Newman that incurred a tower‐type loss. Our main conceptual contribution in this work is that we manage to turn the approach of Fischer–Newman, which was inherently ineffective, into an efficient one. On the technical level, our main contribution is in establishing certain properties of Frieze–Kannan Weak Regular partitions that are of independent interest. [ABSTRACT FROM AUTHOR]

In this work, we study the problem of approximating the distance to subsequence-freeness in the sample-based distribution-free model. For a given subsequence (word) w = w 1 ... w k , a sequence (text) T = t 1 ... t n is said to contain w if there exist indices 1 ≤ i 1 < ⋯ < i k ≤ n such that t i j = w j for every 1 ≤ j ≤ k . Otherwise, T is w-free. Ron and Rosin (ACM Trans Comput Theory 14(4):1–31, 2022) showed that the number of samples both necessary and sufficient for one-sided error testing of subsequence-freeness in the sample-based distribution-free model is Θ (k / ϵ) . Denoting by Δ (T , w , p) the distance of T to w-freeness under a distribution p : [ n ] → [ 0 , 1 ] , we are interested in obtaining an estimate Δ ^ , such that | Δ ^ - Δ (T , w , p) | ≤ δ with probability at least 2/3, for a given error parameter δ . Our main result is a sample-based distribution-free algorithm whose sample complexity is O ~ (k 2 / δ 2) . We first present an algorithm that works when the underlying distribution p is uniform, and then show how it can be modified to work for any (unknown) distribution p. We also show that a quadratic dependence on 1 / δ is necessary. [ABSTRACT FROM AUTHOR]

We generalize the celebrated isoperimetric inequality of Khot, Minzer, and Safra (SICOMP 2018) for Boolean functions to the case of real‐valued functions f:{0,1}d→ℝ$$ f:{\left\{0,1\right\}}^d\to \mathbb{R} $$. Our main tool in the proof of the generalized inequality is a new Boolean decomposition that represents every real‐valued function f$$ f $$ over an arbitrary partially ordered domain as a collection of Boolean functions over the same domain, roughly capturing the distance of f$$ f $$ to monotonicity and the structure of violations of f$$ f $$ to monotonicity. We apply our generalized isoperimetric inequality to improve algorithms for testing monotonicity and approximating the distance to monotonicity for real‐valued functions. Our tester for monotonicity has query complexity O˜(min(rd,d))$$ \tilde{O}\left(\min \left(r\sqrt{d},d\right)\right) $$, where r$$ r $$ is the size of the image of the input function. (The best previously known tester makes O(d)$$ O(d) $$ queries, as shown by Chakrabarty and Seshadhri (STOC 2013).) Our tester is nonadaptive and has 1‐sided error. We prove a matching lower bound for nonadaptive, 1‐sided error testers for monotonicity. We also show that the distance to monotonicity of real‐valued functions that are α$$ \alpha $$‐far from monotone can be approximated nonadaptively within a factor of O(dlogd)$$ O\left(\sqrt{d\log d}\right) $$ with query complexity polynomial in 1/α$$ 1/\alpha $$ and the dimension d$$ d $$. This query complexity is nearly optimal for nonadaptive algorithms even for the special case of Boolean functions (The best previously known distance approximation algorithm for real‐valued functions, by Fattal and Ron (TALG 2010) achieves O(dlogr)$$ O\left(d\log r\right) $$‐approximation.). [ABSTRACT FROM AUTHOR]

We revisit the problem of property testing for convex position for point sets in ℝ. Our results draw from previous ideas of Czumaj, Sohler, and Ziegler (2000). First, their testing algorithm is redesigned and its analysis is revised for correctness. Second, its functionality is expanded by (i) exhibiting both negative and positive certificates along with the convexity determination, and (ii) significantly extending the input range for moderate and higher dimensions. The behavior of the randomized tester on input set ⊂ ℝ is as follows: (i) if is in convex position, it accepts; (ii) if is far from convex position, with probability at least 2/3, it rejects and outputs a (+2)-point witness of non-convexity as a negative certificate; (iii) if is close to convex position, with probability at least 2/3, it accepts and outputs a subset in convex position that is a suitable approximation of the largest subset in convex position. The algorithm examines a sublinear number of points and runs in subquadratic time for every fixed dimension. [ABSTRACT FROM AUTHOR]

For a natural number m , a distribution is called m -grained, if each element appears with probability that is an integer multiple of 1 / m . We prove that, for any constant c < 1 , testing whether a distribution over [ Θ (m) ] is m -grained requires Ω (m c) samples, where testing a property of distributions means distinguishing between distributions that have the property and distributions that are far (in total variation distance) from any distribution that has the property. [ABSTRACT FROM AUTHOR]

We prove a general structural theorem for a wide family of local algorithms, which includes property testers, local decoders, and probabilistically checkable proofs of proximity. Namely, we show that the structure of every algorithm that makes q adaptive queries and satisfies a natural robustness condition admits a sample-based algorithm with n1-1/O(q² log{l}o}{g}² q) sample complexity, following the definition of Goldreich and Ron [ACM Trans. Comput. Theory, 8 (2016), 7]. We prove that this transformation is nearly optimal. Our theorem also admits a scheme for constructing privacypreserving local algorithms. Using the unified view that our structural theorem provides, we obtain results regarding various types of local algorithms, including the following. We strengthen the state-of-the-art lower bound for relaxed locally decodable codes, obtaining an exponential improvement on the dependency in query complexity; this resolves an open problem raised by Gur and Lachish [SIAM J. Comput., 50 (2021), pp. 788--813]. We show that any (constant-query) testable property admits a sample-based tester with sublinear sample complexity; this resolves a problem left open in a work of Fischer, Lachish, and Vasudev [Proceedings of the 56th Annual Symposium on Foundations of Computer Science, IEEE, 2015, pp. 1163--1182], bypassing an exponential blowup caused by previous techniques in the case of adaptive testers. We prove that the known separation between proofs of proximity and testers is essentially maximal; this resolves a problem left open by Gur and Rothblum [Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017, pp. 39:1--39:43; Comput. Complexity, 27 (2018), pp. 99-207] regarding sublinear-time delegation of computation. Our techniques strongly rely on relaxed sunflower lemmas and the Hajnal--Szemeedi theorem. [ABSTRACT FROM AUTHOR]

Let G be an undirected, bounded degree graph with n vertices. Fix a finite graph H, and suppose one must remove n edges from G to make it H-minor-free (for some small constant > 0). We give an n1/2+o(1)-time randomized procedure that, with high probability, finds an H-minor in such a graph. As an application, suppose one must remove n edges from a bounded degree graph G to make it planar. This result implies an algorithm, with the same running time, that produces a K3,3- or K5-minor in G. No prior sublinear time bound was known for this problem. By the graph minor theorem, we get an analogous result for any minor-closed property. Up to no(1) factors, this resolves a conjecture of Benjamini, Schramm, and Shapira [Adv. Math., 223 (2010), pp. 2200--2218] on the existence of one-sided property testers for minor-closed properties. Furthermore, our algorithm is nearly optimal by a n) lower bound of Czumaj et al. [Random Structures Algorithms, 45 (2014), pp. 139--184]. Prior to this work, the only graphs H for which nontrivial one-sided property testers were known for H-minor-freeness were the following: H being a forest or a cycle [Czumaj et al., Random Structures Algorithms, 45 (2014), pp. 139--184], K2,k, (k2)-grid, and the k-circus [Fichtenberger et al., preprint, arXiv:1707.06126v1, 2017]. [ABSTRACT FROM AUTHOR]

We prove that every uniform approximate homomorphism from a discrete amenable group into a symmetric group is uniformly close to a homomorphism into a slightly larger symmetric group. That is, amenable groups are uniformly flexibly stable in permutations. This answers affirmatively a question of Kun and Thom and a slight variation of a question of Lubotzky. We also give a negative answer to Lubotzky's original question by showing that the group Z is not uniformly strictly stable. Furthermore, we show that SLr(Z), r=3, is uniformly flexibly stable, but the free group Fr, r=2, is not. We define and investigate a probabilistic variant of uniform stability that has an application to property testing. [ABSTRACT FROM AUTHOR]

Property testing algorithms are highly efficient algorithms that come with probabilistic accuracy guarantees. For a property P, the goal is to distinguish inputs that have P from those that are far from having P with high probability correctly, by querying only a small number of local parts of the input. In property testing on graphs, the distance is measured by the number of edge modifications (additions or deletions) that are necessary to transform a graph into one with property P. Much research has focused on the query complexity of such algorithms, i. e., the number of queries the algorithm makes to the input, but in view of applications, the running time of the algorithm is equally relevant. In (Adler, Harwath, STACS 2018), a natural extension of the bounded degree graph model of property testing to relational databases of bounded degree was introduced, and it was shown that on databases of bounded degree and bounded tree-width, every property that is expressible in monadic second-order logic with counting (CMSO) is testable with constant query complexity and sublinear running time. It remains open whether this can be improved to constant running time. In this article we introduce a new model, which is based on the bounded degree model, but the distance measure allows both edge (tuple) modifications and vertex (element) modifications. We show that every property that is testable in the classical model is testable in our model with the same query complexity and running time, but the converse is not true. Our main theorem shows that on databases of bounded degree and bounded tree-width, every property that is expressible in CMSO is testable with constant query complexity and constant running time in the new model. Our proof methods include the semilinearity of the neighborhood histograms of databases having the property and a result by Alon (Proposition 19.10 in Lovász, Large networks and graph limits, 2012) that states that for every bounded degree graph G there exists a constant size graph H that has a similar neighborhood distribution to G. It can be derived from a result in (Benjamini et al., Advances in Mathematics 2010) that hyperfinite hereditary properties are testable with constant query complexity and constant running time in the classical model (and hence in the new model). Using our methods, we give an alternative proof that hyperfinite hereditary properties are testable with constant query complexity and constant running time in the new model. We argue that our model is natural and our meta-theorem showing constant-time CMSO testability supports this. [ABSTRACT FROM AUTHOR]

The selection of equipment and the design of rack for gold electroplating of single-layered ceramic chip capacitors were introduced. A neutral gold electroplating bath with a small amount of cyanide was used. The effect of mass concentration of Au+ on the allowable current density range during gold electroplating, and the effects of pulse parameters on the surface roughness of gold coating were studied. It is recommended that the process parameters in actual production be controlled as follows: mass concentration of Au+ ca.7 g/L, average current density 0.3-0.4 A/dm², pulse frequency 2 000 Hz, and duty cycle 20%. The key points for bath maintenance, the requirements and testing methods of the properties (including appearance, adhesion, thickness, and bonding strength) of gold coating were described. [ABSTRACT FROM AUTHOR]

Let G be a graph with n vertices and maximum degree d. Fix some minor-closed property P (such as planarity). We say that G is ε -far from P if one has to remove εdn edges to make it have P . The problem of property testing P was introduced in the seminal work of Benjamini, Schramm, and Shapira (Symposium on the Theory of Computing 2008) that gave a tester with query complexity triply exponential in ε - 1 . Levi and Ron [ACM Trans. Algorithms, 11 (2005), 24 2015] have given the best tester to date, with a quasi-polynomial (in ε - 1 ) query complexity. It remained an open problem to show whether there is a property tester whose query complexity is poly(dε - 1 ), even for planarity. In this paper, we resolve this open question. For any minor-closed property, we give a tester with query complexity d. poly(ε- 1 ). The previous line of work on (independent of n, two-sided) testers is primarily combinatorial. Our work, on the other hand, employs techniques from spectral graph theory. This paper is a continuation of recent work of the authors (Foundations of Computer Science 2018) analyzing random walk algorithms that find forbidden minors. [ABSTRACT FROM AUTHOR]

We prove that any non-adaptive algorithm that tests whether an unknown Boolean function f:{0,1}n→ {0,1} is a k-junta or ∊-far from every k-junta must make Ω˜(k3/2) / ∊) many queries for a wide range of parameters k and ∊. Our result dramatically improves previous lower bounds and is essentially optimal since there is a known non-adaptive junta tester which makes Ω˜(k3/2) / ∊ queries. Combined with the known existence of an adaptive tester which makes O(klog k + k /∊) queries, our result shows that adaptivity enables polynomial savings in query complexity for junta testing. [ABSTRACT FROM AUTHOR]

We initiate a systematic study of tolerant testers of image properties or, equivalently, algorithms that approximate the distance from a given image to the desired property. Image processing is a particularly compelling area of applications for sublinear-time algorithms and, specifically, property testing. However, for testing algorithms to reach their full potential in image processing, they have to be tolerant, which allows them to be resilient to noise. We design efficient approximation algorithms for the following fundamental questions: What fraction of pixels have to be changed in an image so it becomes a half-plane? A representation of a convex object? A representation of a connected object? More precisely, our algorithms approximate the distance to three basic properties (being a half-plane, convexity, and connectedness) within a small additive error ε, after reading poly(1/ε) pixels, independent of the image size. We also design an efficient agnostic proper PAC learner of convex sets (continuous and discrete) in two dimensions under the uniform distribution. Our algorithms require very simple access to the input: uniform random samples for the half-plane property and convexity, and samples from uniformly random blocks for connectedness. However, the analysis of the algorithms, especially for convexity, requires many geometric and combinatorial insights. For example, in the analysis of the algorithm for convexity, we define a set of reference polygons Pε such that (1) every convex image has a nearby polygon in Pε and (2) one can use dynamic programming to quickly compute the smallest empirical distance to a polygon in Pε. [ABSTRACT FROM AUTHOR]

We consider the problem of finding a cycle in a sparse directed graph G that is promised to be far from acyclic, meaning that the smallest feedback arc set, i.e., a subset of edges whose deletion results in an acyclic graph, in G is large. We prove an information-theoretic lower bound, showing that for N-vertex graphs with constant outdegree, any algorithm for this problem must make Ω̄(N5/9) queries to an adjacency list representation of G. In the language of property testing, our result is an Ω̄(N5/9) lower bound on the query complexity of one-sided algorithms for testing whether sparse digraphs with constant outdegree are far from acyclic. This is the first improvement on the Ω (√ N) lower bound, implicit in the work of Bender and Ron, which follows from a simple birthday paradox argument. [ABSTRACT FROM AUTHOR]

We initiate a study of learning and testing dynamic environments, focusing on environments that evolve according to a fixed local rule. The (proper) learning task consists of obtaining the initial configuration of the environment, whereas for nonproper learning it suffices to predict its future values. The testing task consists of checking whether the environment has indeed evolved from some initial configuration according to the known evolution rule. We focus on the temporal aspect of these computational problems, which is reflected in two requirements: (1) it is not possible to "go back to the past" and make a query concerning the environment at time t after having made a query concerning time t'> t and (2) only a small portion of the environment is inspected in each time unit. We present several general results, extensive studies of two special cases, and a host of open problems. The general results illustrate the significance of the temporal aspect of the current model (i.e., the difference between the current model and the standard model) as well as the preservation of some relations that hold in the standard model. The two special cases that we study are linear rules of evolution and rules of evolution that represent simple movement of objects. Specifically, we show that evolution according to any linear rule can be tested within a total number of queries that is sublinear in the size of the environment and that evolution according to a simple one-dimensional movement rule can be tested within a total number of queries that is independent of the size of the environment. [ABSTRACT FROM AUTHOR]

This study aims to investigate the properties of novel waterborne epoxy modified asphalt emulsion with styrene–butadiene–chloroprene rubber (SBR/CR) and evaluate its performance improvement mechanism. To achieve this objective, Brookfield rotational viscometer tests and dynamic shear rheometer tests were first performed to characterize the rheological properties of new emulsion residues with time. Then, penetration, softening point, and ductility tests were adopted to evaluate the conventional performance of the new emulsion residue. Finally, the curing microstructures, functional group changes, and thermal stability of new emulsion were analyzed by using scanning electron microscopy, Fourier transform infrared spectrometry, thermal gravimetric analysis, and differential scanning calorimetry, respectively. The experimental results showed that the new emulsion residue showed an extremely high viscosity, and its viscosity value was more than 40 times that of general asphalt emulsion. The stiffness and thermal stability of new emulsion at high temperatures were significantly improved by crosslinking the epoxy system to form a three-dimensional polymer network. The incorporation of SBR/CR copolymer reduced the effect of waterborne epoxy cured products on the low-temperature elongation performance of new emulsion, resulting in improved thermal cracking resistance of the new emulsion system. The optimum dosage of waterborne epoxy for the new asphalt emulsion determined was 15% by weight of SBR/CR modified asphalt emulsion. Based on these results, it is evident that the waterborne epoxy asphalt emulsion together with the SBR/CR copolymer can form a durable emulsion system in both low- and high-temperature environments. [ABSTRACT FROM AUTHOR]

We study the property testing of functions Fnp → [R] for fixed prime p and positive integer R. We work in the natural model where we are allowed to query the function on a random subspace of constant dimension. We say that a property is testable if queries of this form can detect the property with one-sided error. Furthermore, a property is proximity oblivious-testable (POtestable) if the test is also independent of the proximity parameter\epsilon. It is known that a number of natural properties such as linearity and being a low degree polynomial are PO-testable. These properties are examples of linear-invariant properties, meaning that they are preserved under linear automorphisms of the domain. Following work of Kaufman and Sudan, the study of linear-invariant properties has been an important problem in arithmetic property testing. A central conjecture in this field, proposed by Bhattacharyya, Grigorescu, and Shapira, is that a linear-invariant property is testable if and only if it is semi-subspace-hereditary. We prove two results; the first resolves this conjecture and the second classifies PO-testable properties: (1) A linear-invariant property is testable if and only if it is semi-subspace-hereditary. (2) A linear-invariant property is PO-testable if and only if it is locally characterized. Our innovations are twofold. We give a more powerful version of the compactness argument first introduced by Alon and Shapira. This relies on a new strong arithmetic regularity lemma in which one mixes different levels of Gowers uniformity. This allows us to extend the work of Bhattacharyya, Fischer, Hatami, Hatami, and Lovett by removing the bounded complexity restriction in their work. Our second innovation is a novel recoloring technique called patching that builds on earlier work by the authors and Fox. This Ramsey-theoretic technique is critical for working in the linear-invariant setting and allows us to remove the translation-invariant restriction present in previous work. [ABSTRACT FROM AUTHOR]

We study two questions related to the abelian sandpile model, those questions are: can we predict the dynamics of sandpiles avalanches? Can we efficiently stop an evolving avalanche? We study the problem of deciding wether all the nodes of a sandpile grid will be toppled by an evolving avalanche. We identify an important subproblem of this prediction problem, namely: the problem of recognizing the recurrent configurations of the sandpile dynamics. This latter problem can be solved in linear time by simulating the appropriate sandpile avalanches. We ask: do there exist sequential algorithms that solve this recognition problem in sublinear time? We prove that there do not exist sublinear time sequential algorithms that solve this problem in a probabilistic approximately correct way. This means that those avalanches cannot be predicted by a sequential algorithm. We also study the problem of fighting against avalanches. This latter problem resembles the classical firefighter problem. We prove that fighting against two-dimensional avalanches is harder than fighting against fires on forests of low depth. [ABSTRACT FROM AUTHOR]

We design a nonadaptive algorithm that, given oracle access to a 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 Õ(n)‐approximation to the distance of f to monotonicity. The analysis of our algorithm relies on an improvement to the directed isoperimetric inequality of Khot, Minzer, and Safra (SIAM J. Comput., 2018). Furthermore, we rule out a poly(n,1/α)‐query nonadaptive algorithm that approximates the distance to monotonicity significantly better by showing that, for all constant κ>0, every nonadaptive n1/2−κ‐approximation algorithm for this problem requires 2nκ queries. This answers a question of Seshadhri (Property Testing Review, 2014) for the case of nonadaptive algorithms. We obtain our lower bound by proving an analogous bound for erasure‐resilient (and tolerant) testers. Our method also yields the same lower bounds for unateness and being a k‐junta. [ABSTRACT FROM AUTHOR]

Hamiltonian cycles in graphs were first studied in the 1850s. Since then, an impressive amount of research has been dedicated to identifying classes of graphs that allow Hamiltonian cycles, and to related questions. The corresponding decision problem, that asks whether a given graph is Hamiltonian (i. e. admits a Hamiltonian cycle), is one of Karp's famous NP-complete problems. In this paper we study graphs of bounded degree that are far from being Hamiltonian, where a graph G on n vertices is far from being Hamiltonian, if modifying a constant fraction of n edges is necessary to make G Hamiltonian. We give an explicit deterministic construction of a class of graphs of bounded degree that are locally Hamiltonian, but (globally) far from being Hamiltonian. Here, locally Hamiltonian means that every subgraph induced by the neighbourhood of a small vertex set appears in some Hamiltonian graph. More precisely, we obtain graphs which differ in (n) edges from any Hamiltonian graph, but non-Hamiltonicity cannot be detected in the neighbourhood of o(n) vertices. Our class of graphs yields a class of hard instances for one-sided error property testers with linear query complexity. It is known that any property tester (even with two-sided error) requires a linear number of queries to test Hamiltonicity (Yoshida, Ito, 2010). This is proved via a randomised construction of hard instances. In contrast, our construction is deterministic. So far only very few deterministic constructions of hard instances for property testing are known. We believe that our construction may lead to future insights in graph theory and towards a characterisation of the properties that are testable in the bounded-degree model. [ABSTRACT FROM AUTHOR]

Copyright of Electroplating & Finishing is the property of Electroplating & Finishing Editorial Office and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

We initiate the study of the role of erasures in local decoding and use our understanding to prove a separation between erasure‐resilient and tolerant property testing. We first investigate local list‐decoding in the presence of erasures. We prove an analog of a famous result of Goldreich and Levin on local list‐decodability of the Hadamard code. Specifically, we show that the Hadamard code is locally list‐decodable in the presence of a constant fraction of erasures, arbitrarily close to 1, with list sizes and query complexity better than in the Goldreich–Levin theorem. We further study approximate locally erasure list‐decodable codes and use them to construct a property that is erasure‐resiliently testable with query complexity independent of the input length, n, but requires nΩ(1) queries for tolerant testing. We also investigate the general relationship between local decoding in the presence of errors and in the presence of erasures. [ABSTRACT FROM AUTHOR]

We present algorithms for testing if a (0,1)-matrix M has Boolean/binary rank at most d, or is 𝜖-far from having Boolean/binary rank at most d (i.e., at least an 𝜖-fraction of the entries in M must be modified so that it has rank at most d). For the Boolean rank we present a non-adaptive testing algorithm whose query complexity is Õ d 4 / 𝜖 6 . For the binary rank we present a non-adaptive testing algorithm whose query complexity is O(22d/𝜖2), and an adaptive testing algorithm whose query complexity is O(22d/𝜖). All algorithms are 1-sided error algorithms that always accept M if it has Boolean/binary rank at most d, and reject with probability at least 2/3 if M is 𝜖-far from having Boolean/binary rank at most d. [ABSTRACT FROM AUTHOR]

In hedonic games, players form coalitions based on individual preferences over the group of players they could belong to. Several concepts to describe the stability of coalition structures in a game have been proposed and analysed in the literature. However, prior research focuses on algorithms with time complexity that is at least linear in the input size. In the light of very large games that arise from, e.g., social networks and advertising, we initiate the study of sublinear time property testing algorithms for existence and verification problems under several notions of coalition stability in a model of hedonic games represented by graphs with bounded degree. In graph property testing, one shall decide whether a given input has a property (e.g., a game admits a stable coalition structure) or is far from it, i.e., one has to modify at least an ϵ -fraction of the input (e.g., the game’s preferences) to make it have the property. In particular, we consider verification of perfection, individual rationality, Nash stability, (contractual) individual stability, and core stability. While there is always a Nash-stable coalition structure (which also implies individually stable coalitions), we show that the existence of a perfect coalition structure is not tautological but can be tested. All our testers have one-sided error and time complexity that is independent of the input size. [ABSTRACT FROM AUTHOR]

Universal locally testable codes (universal - LTC s), recently introduced in our companion paper (CJTCS , 2018), are codes that admit local tests for membership in numerous subcodes, allowing for testing properties of the encoded message. Unfortunately, universal - LTC s suffer strong limitations, which motivate us to initiate, in this work, the study of the "NP analogue" of these codes, wherein the testing procedures are also given free access to a short proof, akin the MA proofs of proximity of Gur and Rothblum (Computational Complexity 2018). We call such codes "universal locally verifiable codes" (universal - LVC s). A universal - LVC C : { 0 , 1 } k → { 0 , 1 } η for a family of functions F = { f i : { 0 , 1 } k → { 0 , 1 } } i ∈ [ M ] is a code such that, for every i ∈ [ M ] , membership in the subcode { C (x) : f i (x) = 1 } can be verified locally using explicit access to a short (sublinear length) proof. A universal - LVC can be viewed as providing an encoding of inputs under which a large family of properties of the encoded inputs can be locally testable using a short proof. We show universal - LVC s of block length O ˜ (n 2) for the family of all functions expressible by t -ary constraint satisfaction problems (t -CSP) over n constraints and k variables, with proof length and query complexity O ˜ (n 2 / 3) , where t = O (1) and n ≥ k. In addition, we prove a lower bound of p ⋅ q = Ω ˜ (k) for every polynomial length universal - LVC , having proof complexity p and query complexity q , for such CSP functions. We give an application of universal - LVC s for interactive proofs of proximity (IPP), introduced by Rothblum, Vadhan, and Wigderson (STOC 2013), which are interactive proof systems wherein the verifier queries only a sublinear number of input bits to the end of asserting that, with high probability, the input is close to an accepting input. Specifically, we show a 3-round IPP for the set of assignments that satisfy fixed CSP instances, with sublinear communication and query complexity, which we derive from our universal - LVC for CSP functions. [ABSTRACT FROM AUTHOR]

Recently there has been much interest in Gowers uniformity norms from the perspective of theoretical computer science. This is mainly due to the fact that these norms provide a method for testing whether the maximum correlation of a function f : np → Fp with polynomials of degree at most d ≤ p is nonnegligible, while making only a constant number of queries to the function. This is an instance of correlation testing . In this framework, a fixed test is applied to a function, and the acceptance probability of the test is dependent on the correlation of the function from the property. This is an analogue of proximity oblivious testing, a notion coined by Goldreich and Ron, in the high error regime. In this work, we study general properties which are affine invariant and which are correlation testable using a constant number of queries. We show that any such property (as long as the field size is not too small) can in fact be tested by Gowers uniformity tests, and hence having correlation with the property is equivalent to having correlation with degree d polynomials for some fixed d. We stress that our result holds also for nonlinear properties which are affine invariant. This completely classifies affine invariant properties which are correlation testable. The proof is based on higher-order Fourier analysis. Another ingredient is a nontrivial extension of a graph theoretical theorem of Erd̈os, Lov́asz, and Spencer to the context of additive number theory. © 2014 Society for Industrial and Applied Mathematics.

Recently there has been much interest in Gowers uniformity norms from the perspective of theoretical computer science. This is mainly due to the fact that these norms provide a method for testing whether the maximum correlation of a function f : np → Fp with polynomials of degree at most d ≤ p is nonnegligible, while making only a constant number of queries to the function. This is an instance of correlation testing . In this framework, a fixed test is applied to a function, and the acceptance probability of the test is dependent on the correlation of the function from the property. This is an analogue of proximity oblivious testing, a notion coined by Goldreich and Ron, in the high error regime. In this work, we study general properties which are affine invariant and which are correlation testable using a constant number of queries. We show that any such property (as long as the field size is not too small) can in fact be tested by Gowers uniformity tests, and hence having correlation with the property is equivalent to having correlation with degree d polynomials for some fixed d. We stress that our result holds also for nonlinear properties which are affine invariant. This completely classifies affine invariant properties which are correlation testable. The proof is based on higher-order Fourier analysis. Another ingredient is a nontrivial extension of a graph theoretical theorem of Erd̈os, Lov́asz, and Spencer to the context of additive number theory. © 2014 Society for Industrial and Applied Mathematics.

Let P be an affine invariant property of multivariate functions over a constant size finite field. We show that if P is locally testable with a constant number of queries, then one can estimate the distance of a function f from P with a constant number of queries. This was previously unknown even for simple properties such as cubic polynomials over the binary field. Our test is simple: Take a restriction of f to a constant dimensional affine subspace, and measure its distance from P. We show that by choosing the dimension large enough, this approximates with high probability the global distance of f from P. The analysis combines the approach of Fischer and Newman [SIAM J. Comp 2007] who established a similar result for graph properties, with recently developed tools in higher order Fourier analysis, in particular those developed in Bhattacharyya et al. [STOC 2013]. Copyright © 2013 by The Institute of Electrical and Electronics Engineers, Inc.

Let P be an affine invariant property of multivariate functions over a constant size finite field. We show that if P is locally testable with a constant number of queries, then one can estimate the distance of a function f from P with a constant number of queries. This was previously unknown even for simple properties such as cubic polynomials over the binary field. Our test is simple: Take a restriction of f to a constant dimensional affine subspace, and measure its distance from P. We show that by choosing the dimension large enough, this approximates with high probability the global distance of f from P. The analysis combines the approach of Fischer and Newman [SIAM J. Comp 2007] who established a similar result for graph properties, with recently developed tools in higher order Fourier analysis, in particular those developed in Bhattacharyya et al. [STOC 2013]. Copyright © 2013 by The Institute of Electrical and Electronics Engineers, Inc.

Set F = Fp for any fixed prime p ≥ 2. An affine-invariant property is a property of functions over Fn that is closed under taking affine transformations of the domain. We prove that all affine-invariant properties having local characterizations are testable. In fact, we show a proximity-oblivious test for any such property P, meaning that given an input function f, we make a constant number of queries to f, always accept if f satisfies P, and otherwise reject with probability larger than a positive number that depends only on the distance between f and P. More generally, we show that any affine-invariant property that is closed under taking restrictions to subspaces and has bounded complexity is testable. We also prove that any property that can be described as the property of decomposing into a known structure of lowdegree polynomials is locally characterized and is, hence, testable. For example, whether a function is a product of two degree-d polynomials, whether a function splits into a product of d linear polynomials, and whether a function has low rank are all examples of degree-structural properties and are therefore locally characterized. Our results depend on a new Gowers inverse theorem by Tao and Ziegler for low characteristic fields that decomposes any polynomial with large Gowers norm into a function of a small number of low-degree non-classical polynomi- als. We establish a new equidistribution result for high rank non-classical polynomials that drives the proofs of both the testability results and the local characterization of degreestructural properties. Copyright 2013 ACM.

Set F = Fp for any fixed prime p ≥ 2. An affine-invariant property is a property of functions over Fn that is closed under taking affine transformations of the domain. We prove that all affine-invariant properties having local characterizations are testable. In fact, we show a proximity-oblivious test for any such property P, meaning that given an input function f, we make a constant number of queries to f, always accept if f satisfies P, and otherwise reject with probability larger than a positive number that depends only on the distance between f and P. More generally, we show that any affine-invariant property that is closed under taking restrictions to subspaces and has bounded complexity is testable. We also prove that any property that can be described as the property of decomposing into a known structure of lowdegree polynomials is locally characterized and is, hence, testable. For example, whether a function is a product of two degree-d polynomials, whether a function splits into a product of d linear polynomials, and whether a function has low rank are all examples of degree-structural properties and are therefore locally characterized. Our results depend on a new Gowers inverse theorem by Tao and Ziegler for low characteristic fields that decomposes any polynomial with large Gowers norm into a function of a small number of low-degree non-classical polynomi- als. We establish a new equidistribution result for high rank non-classical polynomials that drives the proofs of both the testability results and the local characterization of degreestructural properties. Copyright 2013 ACM.

We show that every algorithm for testing n-variate Boolean functions for monotonicity must have query complexity Ω(n1/4). All previous lower bounds for this problem were designed for nonadaptive algorithms and, as a result, the best previous lower bound for general (possibly adaptive) monotonicity testers was only Ω(log n). Combined with the query complexity of the nonadaptive monotonicity tester of Khot, Minzer, and Safra (FOCS 2015), our lower bound shows that adaptivity can result in at most a quadratic reduction in the query complexity for testing monotonicity. By contrast, we show that there is an exponential gap between the query complexity of adaptive and nonadaptive algorithms for testing regular linear threshold functions (LTFs) for monotonicity. Chen, De, Servedio, and Tan (STOC 2015) recently showed that nonadaptive algorithms require almost Ω(n1/2) queries for this task. We introduce a new adaptive monotonicity testing algorithm which has query complexity O(log n) when the input is a regular LTF. [ABSTRACT FROM AUTHOR]

We consider expansion and property testing in the language of incidence geometry, covering both simplicial and cubical complexes in any dimension. We develop a general method for the transition from an explicit description of the cohomology group, which need not be trivial, to a testability proof with linear ratio between errors. The method is demonstrated by testing functions on 2-cells in cubical complexes to be induced from the edges. [ABSTRACT FROM AUTHOR]

As PUFs become ubiquitous for commercial products (e.g., FPGAs from Xilinx, Altera, and Microsemi), attacks against these primitives are evolving toward more omnipresent and even advanced techniques. Machine learning (ML) attacks, among other non-invasive attacks, are proven to be feasible and cost-effective in the real-world. However, for PUF designers, it still remains an open question whether their countermeasures, or even new designs, are resistant to these types of attacks. Although standard metrics for estimating PUF quality exist, the most common approaches for measuring resistance to ML attacks are empirical. This paper introduces PUFmeter, a new publicly available toolbox consisting of in-house developed algorithms, to provide a firm basis for the robustness assessment of PUFs against ML attacks. To this end, new metrics and notions are reintroduced by PUFmeter to PUF designers and manufacturers. Furthermore, to prepare the PUF input-output pairs adequately before conducting any analysis, PUFmeter involves modules that output the minimum number of measurement repetitions and the upper bound on the noise level affecting the PUF responses.

In this article, we consider the problem of identifying patterns of interest in colored strings. A colored string is a string where each position is assigned one of a finite set of colors. Our task is to find substrings of the colored string that always occur followed by the same color at the same distance. The problem is motivated by applications in embedded systems verification, in particular, assertion mining. The goal there is to automatically find properties of the embedded system from the analysis of its simulation traces. We show that, in our setting, the number of patterns of interest is upper-bounded by O(n2), where n is the length of the string. We introduce a baseline algorithm, running in O(n2) time, which identifies all patterns of interest satisfying certain minimality conditions for all colors in the string. For the case where one is interested in patterns related to one color only, we also provide a second algorithm that runs in O(n2 log n) time in the worst case but is faster than the baseline algorithm in practice. Both solutions use suffix trees, and the second algorithm also uses an appropriately defined priority queue, which allows us to reduce the number of computations. We performed an experimental evaluation of the proposed approaches over both synthetic and real-world datasets, and found that the second algorithm outperforms the first algorithm on all simulated data, while on the real-world data, the performance varies between a slight slowdown (on half of the datasets) and a speedup by a factor of up to 11. [ABSTRACT FROM AUTHOR]

We study the local decodability and (tolerant) local testability of low‐degree n‐variate polynomials over arbitrary fields, evaluated over the domain {0,1}n. We show that for every field there is a tolerant local test whose query complexity depends only on the degree. In contrast we show that decodability is possible over fields of positive characteristic, but not over the reals. [ABSTRACT FROM AUTHOR]

We consider the subspace proximity problem: Given a vector x ∈ R n and a basis matrix V ∈ R n × m , the objective is to determine whether x is close to the subspace spanned by V. Although the problem is solvable by linear programming, it is time consuming especially when n is large. In this paper, we propose a quick tester that solves the problem correctly with high probability. Our tester runs in time independent of n and can be used as a sieve before computing the exact distance between x and the subspace. The number of coordinates of x queried by our tester is O (m ϵ log m ϵ) , where ϵ is an error parameter, and we show almost matching lower bounds. By experiments, we demonstrate the scalability and applicability of our tester using synthetic and real data sets. [ABSTRACT FROM AUTHOR]