For every fixed constant alpha > 0, we design an algorithm for computing the k-sparse Walsh-Hadamard transform (i.e., Discrete Fourier Transform over the Boolean cube) of an N-dimensional vector x is an element of ...
详细信息
For every fixed constant alpha > 0, we design an algorithm for computing the k-sparse Walsh-Hadamard transform (i.e., Discrete Fourier Transform over the Boolean cube) of an N-dimensional vector x is an element of R-N in time k(1+alpha) (log N)(O(1)). Specifically;the algorithm is given query access to x and computes a k -sparse (x) over tilde is an element of R-N satisfying parallel to(x) over tilde - (x) over cap parallel to(1) <= parallel to(x) over cap - H-k((x) over cap)parallel to(1) for an absolute constant c > 0, where (x) over cap is the transform of x and H-K(x) over cap is its best k -sparse approximation. Our algorithm is fully deterministic and only uses nonadaptive queries to x (i.e., all queries are determined and performed in parallel when the algorithm starts). An important technical tool that we use is a construction of nearly optimal and linear lossless condensers, which is a careful instantiation of the GUV condenser (Guruswami et al. [2009]). Moreover;we design a deterministic and nonadaptive l(1)/l(1) compressed sensing scheme based on general lossless condensers that is equipped with a fast reconstruction algorithm running in time k(1+alpha)(log N)(O(1)) (for the GUV-based condenser) and is of independent interest. Our scheme significantly simplifies and improves an earlier expander -based construction due to Berinde, Gilbert, Indyk, Karloft;and Strauss [Berinde et al. 2008]. Our methods use linear lossless condensers in a black box fashion;therefore, any future improvement on explicit constructions of such condensers would immediately translate to improved parameters in our framework (potentially leading to k(log N)(O(1)) reconstruction time with a reduced exponent in the poly logarithmic factor, and eliminating the extra parameter alpha). By allowing the algorithm to use randomness while still using nonadaptive queries, the runtime of the algorithm can be improved to O(k log(3) N).
The PCP theorem [Arora et al. 1998;Arora and Safra 1998] says that every NP-proof can be encoded to another proof, namely, a probabilistically checkable proof (PCP), which can be tested by a verifier that queries only...
详细信息
The PCP theorem [Arora et al. 1998;Arora and Safra 1998] says that every NP-proof can be encoded to another proof, namely, a probabilistically checkable proof (PCP), which can be tested by a verifier that queries only a small part of the PCP. A natural question is how large is the blow-up incurred by this encoding, that is, how long is the PCP compared to the original NP-proof? The state-of-the-art work of Ben-Sasson and Sudan [2008] and Dinur [2007] shows that one can encode proofs of length n by PCPs of length *** log n that can be verified using a constant number of queries. In this work, we show that if the query complexity is relaxed to n(epsilon), then one can construct PCPs of length O(n) for circuit-SAT, and PCPs of length O(t log t) for any language in Ntime(t). More specifically, for any epsilon > 0, we present (nonuniform) probabilistically checkable proofs (PCPs) of length 2(O(1/epsilon)).n that can be checked using n(epsilon) queries for circuit-SAT instances of size n. Our PCPs have perfect completeness and constant soundness. This is the first constant-rate PCP construction that achieves constant soundness with nontrivial query complexity (o(n)). Our proof replaces the low-degree polynomials in algebraic PCP constructions with tensors of transitive algebraic geometry (AG) codes. We show that the automorphisms of an AG code can be used to simulate the role of affine transformations that are crucial in earlier high-rate algebraic PCP constructions. Using this observation, we conclude that any asymptotically good family of transitive AG codes over a constant-sized alphabet leads to a family of constant-rate PCPs with polynomially small query complexity. Such codes are constructed in the appendix to this article for the first time for every message length, building on an earlier construction for infinitely many message lengths by Stichtenoth [2006].
We consider the problem of testing whether a given function f : F-q(n) -> F-q is close to an n-variate degree d polynomial over the finite field F-q of q elements. The natural, low-query test for this property woul...
详细信息
We consider the problem of testing whether a given function f : F-q(n) -> F-q is close to an n-variate degree d polynomial over the finite field F-q of q elements. The natural, low-query test for this property would be to first pick the smallest dimension t = t(q,d) approximate to d/q such that every function of degree greater than d reveals this aspect on some t-dimensional affine subspace of F-q(n). Then, one would test that f when restricted to a random t-dimensional affine subspace is a polynomial of degree at most d on this subspace. Such a test makes only q(t) queries, independent of n. Previous works, by Alon et al. [IEEE Trans. Inform. Theory, 51 (2005), pp. 4032-4039], Kaufman and Ron [SIAM J. Comput., 36 (2006), pp. 779-802], and Jutla et al. [Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, 2004, pp. 423-432], showed that this natural test rejected functions that were Omega(1)-far from degree d-polynomials with probability at least Omega(q(-t)). (The initial work [IEEE Trans. Inform. Theory, 51 (2005), pp. 4032-4039] considered only the case of q = 2, while the work [Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, 2004, pp. 423-432] considered only the case of prime q. The results in [SIAM J. Comput., 36 (2006), pp. 779-802] hold for all fields.) Thus to get a constant probability of detecting functions that are at a constant distance from the space of degree d polynomials, the tests made q(2t) queries. Kaufman and Ron also noted that when q is prime, then q(t) queries are necessary. Thus these tests were off by at least a quadratic factor from known lower bounds. Bhattacharyya et al. [Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, 2010, pp. 488-497] gave an optimal analysis of this test for the case of the binary field and showed that the natural test actually rejects functions that were Omega(1)-far from degree d-polynomials with probability Omega(1). I
sublinear time algorithms represent a new paradigm in computing, where an algorithm must give some sort of an answer after inspecting only a very small portion of the input. We discuss the sorts of answers that one mi...
详细信息
In this paper, we Study two questions related to the problem of testing whether a function is close to a homomorphism. For two finite groups G,H (not necessarily Abelian), an arbitrary map f : G -> H, and a paramet...
详细信息
In this paper, we Study two questions related to the problem of testing whether a function is close to a homomorphism. For two finite groups G,H (not necessarily Abelian), an arbitrary map f : G -> H, and a parameter 0 < is an element of < 1, say that f is is an element of-close to a homomorphism if there is some homomorphism g such that g and f differ on at most is an element of vertical bar G vertical bar elements of G, and say that f is is an element of-far otherwise. For a given f and is an element of, a homomorphism tester should distinguish whether f is a homomorphism, or if f is is an element of-far from a homornorphism. When G is Abelian, it was known that the test which picks O(1/is an element of) random pairs x,y and tests that f (x) + f (y) = f (x + y) gives a homomorphism tester. Our first result shows that such a test works for all groups G. Next, we consider functions that are close to their self-convolutions. Let A = (ag vertical bar g is an element of G) be a distribution on G. The self-convolution of A, A' = (a(g)'vertical bar g is an element of G), is defined by a(x)' = Sigma a(y)a(z). y,z is an element of G;yz=x It is known that A = A' exactly when A is the uniform distribution over a subgroup of G. We show that there is a sense in which this characterization is robust-that is, if A is close in statistical distance to A', then A must be close to uniform over some subgroup of G. Finally, we show a relationship between the question of testing whether a function is close to a homomorphism via the above test and the question of characterizing functions that are close to their self-convolutions. (c) 2007 Wiley Periodicals, Inc.
We argue that the symmetries of a property being tested play a central role in property testing. We support this assertion in the context of algebraic functions, by examining properties of functions mapping a vector s...
详细信息
ISBN:
(纸本)9781605580470
We argue that the symmetries of a property being tested play a central role in property testing. We support this assertion in the context of algebraic functions, by examining properties of functions mapping a vector space K-n over a field K to a subfield F. We consider (F-)linear properties that are invariant under linear transformations of the domain and prove that an O(1)-local "characterization" is a necessary and sufficient condition for O(1)-local testability, when vertical bar K vertical bar = O(1). (A local characterization of a property is a definition of a property in terms of local constraints satisfied by functions exhibiting a property.) For the subclass of properties that are invariant under affine transformations of the domain, we prove that the existence of a single O(1)-local constraint implies O(1)-local testability. These results generalize and extend the class of algebraic properties, most notably linearity and low-degree-ness, that were previously known to be testable. In particular, the extensions include properties satisfied by functions of degree linear in n that turn out to be O(1)-locally testable. Our results are proved by introducing a new notion that we term "formal characterizations". Roughly this corresponds to characterizations that are given by a single local constraint and its permutations under linear transformations of the domain. Our main testing result shows that local formal characterizations essentially imply local testability. We then investigate properties that are linear-invariant and attempt to understand their local formal characterizability. Our results here give coarse upper and lower bounds on the locality of constraints and characterizations for linear-invariant properties in terms of some structural parameters of the property we introduce. The lower bounds rule out any characterization, while the tipper bounds give formal characterizations. Combining the two gives a test for all linear-invariant properties with local
Given a pair of finite groups G and H, the set of homomorphisms from G to H form an error-correcting code where codewords differ in at least 1/2 the coordinates. We show that for every pair of abelian groups G and H, ...
详细信息
ISBN:
(纸本)9781605580470
Given a pair of finite groups G and H, the set of homomorphisms from G to H form an error-correcting code where codewords differ in at least 1/2 the coordinates. We show that for every pair of abelian groups G and H, the resulting code is (locally) list-decodable from a fraction of errors arbitrarily close to its distance. At the heart of this result is the following combinatorial result: There is a fixed polynomial p(.) such that for every pair of abelian groups G and H, if the maximum fraction of agreement between two distinct homomorphisms from G to H is Lambda, then for every epsilon > 0 and every function f : G -> H, the number of homomorphisms that have agreement Delta + epsilon with f is at most p(1/epsilon). We thus give a broad class of codes whose list-decoding radius exceeds the "Johnson bound". Examples of such codes are rare in the literature, and for the ones that do exist, "combinatorial" techniques to analyze their list-decodability are limited. Our work is an attempt to add to the body of such techniques. We use the fact that abelian groups decompose into simpler ones and thus codes derived from homomorphisms over abelian groups may be viewed as certain "coin positions" of simpler codes. We give techniques to lift list-decoding bounds for the component codes to bounds for the composed code. We believe these techniques may be of general interest.
We argue that the symmetries of a property being tested play a central role in property testing. We support this assertion in the context of algebraic functions, by examining properties of functions mapping a vector s...
详细信息
ISBN:
(纸本)9781605604657
We argue that the symmetries of a property being tested play a central role in property testing. We support this assertion in the context of algebraic functions, by examining properties of functions mapping a vector space K~n over a field K to a subfield F. We consider (F-)linear properties that are invariant under linear transformations of the domain and prove that an O(1)-local "characterization" is a necessary and sufficient condition for O(1) -local testability, when |K| = O(1). (A local characterization of a property is a definition of a property in terms of local constraints satisfied by functions exhibiting a property.) For the subclass of properties that are invariant under affine transformations of the domain, we prove that the existence of a single O(1)-local constraint implies O(1)-local testability. These results generalize and extend the class of algebraic properties, most notably linearity and low-degree-ness, that were previously known to be testable. In particular, the extensions include properties satisfied by functions of degree linear in n that turn out to be O(1)-locally testable. Our results are proved by introducing a new notion that we term "formal characterizations". Roughly this corresponds to characterizations that are given by a single local constraint and its permutations under linear transformations of the domain. Our main testing result shows that local formal characterizations essentially imply local testability. We then investigate properties that are linear-invariant and attempt to understand their local formal characterizability. Our results here give coarse upper and lower bounds on the locality of constraints and characterizations for linear-invariant properties in terms of some structural parameters of the property we introduce. The lower bounds rule out any characterization, while the upper bounds give formal characterizations. Combining the two gives a test for all linear-invariant properties with local characterizations. We be
We present a probabilistic algorithm that, given a connected graph G ( represented by adjacency lists) of average degree d, with edge weights in the set {1,..., w}, and given a parameter 0 < epsilon < 1/ 2, esti...
详细信息
We present a probabilistic algorithm that, given a connected graph G ( represented by adjacency lists) of average degree d, with edge weights in the set {1,..., w}, and given a parameter 0 < epsilon < 1/ 2, estimates in time O(dw epsilon(-2) log dw/epsilon) the weight of the minimum spanning tree (MST) of G with a relative error of at most e. Note that the running time does not depend on the number of vertices in G. We also prove a nearly matching lower bound of Omega(dw epsilon(-2)) on the probe and time complexity of any approximation algorithm for MST weight. The essential component of our algorithm is a procedure for estimating in time O(d epsilon(-2) log d/epsilon) the number of connected components of an unweighted graph to within an additive error of epsilon n. ( This becomes O(epsilon(-2) log 1/epsilon) for d = O(1).) The time bound is shown to be tight up to within the log d/epsilon factor. Our connected-components algorithm picks O(1/epsilon(2)) vertices in the graph and then grows "local spanning trees" whose sizes are specified by a stochastic process. From the local information collected in this way, the algorithm is able to infer, with high confidence, an estimate of the number of connected components. We then show how estimates on the number of components in various subgraphs of G can be used to estimate the weight of its MST.
暂无评论