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 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.
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.
Fix a prime p and a positive integer R. We study the property testing of functions F-p(n) -> [R]. We say that a property is testable if there exists an oblivious tester for this property with one-sided error and co...
详细信息
ISBN:
(纸本)9781728196213
Fix a prime p and a positive integer R. We study the property testing of functions F-p(n) -> [R]. We say that a property is testable if there exists an oblivious tester for this property with one-sided error and constant query complexity. Furthermore, a property is proximity oblivious-testable (PO-testable) 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 two-fold. 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. 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.
Consider a setting in which inputs to and outputs from a computational problem are so large, that there is not time to read them in their entirety. However, if one is only interested in small parts of the output at an...
详细信息
ISBN:
(纸本)9781450362177
Consider a setting in which inputs to and outputs from a computational problem are so large, that there is not time to read them in their entirety. However, if one is only interested in small parts of the output at any given time, is it really necessary to solve the entire computational problem? Is it even necessary to view the whole input? We survey recent work in the model of "local computation algorithms" which for a given input, supports queries by a user to values of specified bits of a legal output. The goal is to design local computation algorithms in such a way that very little of the input needs to be seen in order to determine the value of any single bit of the output. Though this model describes sequential computations, techniques from local distributed algorithms have been extremely important in designing efficient local computation algorithms. In this talk, we describe results on a variety of problems for which sublineartime and space local computation algorithms have been developed - we will give special focus to finding maximal independent sets and sparse spanning graphs.
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).
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
暂无评论