检索结果-内蒙古大学图书馆

Constant Rate PCPs for Circuit-SAT with sublinear Query Complexity

JOURNAL OF THE ACM 2016年第4期63卷 32-32页

作者： Ben-Sasson, Eli Kaplan, Yohay Kopparty, Swastik Meir, Or Stichtenoth, Henning Technion Dept Comp Sci Haifa Israel Rutgers Brunswick NJ USA Univ Haifa Dept Comp Sci Haifa Israel Sabanci Univ MDBF Istanbul Turkey Rutgers State Univ Dept Math Brunswick NJ USA Rutgers State Univ Dept Comp Sci Brunswick NJ USA

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].

关键词： PCPs error-correcting codes algebraic-geometric codes probabilistic proof systems sublinear time algorithms

来源：评论

学校读者我要写书评

暂无评论

Approximating the minimum spanning tree weight in sublinear time

引用

SIAM JOURNAL ON COMPUTING 2005年第6期34卷 1370-1379页

作者： Chazelle, B Rubinfeld, R Trevisan, L Princeton Univ Dept Comp Sci Princeton NJ 08544 USA MIT Dept Elect Engn & Comp Sci Cambridge MA 02139 USA Univ Calif Berkeley Div Comp Sci Berkeley CA 94720 USA

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.

关键词： minimum spanning tree sublinear time algorithms randomized algorithms approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Algebraic Property Testing: The Role of Invariance

Algebraic Property Testing: The Role of Invariance

引用

14th Annual ACM International Symposium on Theory of Computing

作者： Kaufman, Tali Sudan, Madhu IAS Princeton NJ USA MIT CSAIL Cambridge MA 02139 USA

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

关键词： Error-correcting codes Locally testable codes sublinear time algorithms

来源：评论

学校读者我要写书评

暂无评论

Decodability of Group Homomorphisms beyond the Johnson Bound 08

Decodability of Group Homomorphisms beyond the Johnson Bound

引用

14th Annual ACM International Symposium on Theory of Computing

作者： Dinur, Irit Grigorescu, Elena Kopparty, Swastik Sudan, Madhu Weizmann Inst Sci IL-76100 Rehovot Israel MIT Comp Sci & Artifical Intelligence Lab Cambridge MA 02139 USA

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.

关键词： List Decoding sublinear time algorithms Hadamard Codes

来源：评论

学校读者我要写书评

暂无评论

Testing linear-invariant properties 61

Testing linear-invariant properties

引用

61st IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Tidor, Jonathan Zhao, Yufei MIT Dept Math Cambridge MA 02139 USA

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.

关键词： property testing sublinear time algorithms removal lemmas higher-order Fourier analysis

来源：评论

学校读者我要写书评

暂无评论

Local Computation algorithms 19

Local Computation Algorithms

引用

38th ACM Symposium on Principles of Distributed Computing (PODC)

作者： Rubinfeld, Ronitt MIT 77 Massachusetts Ave Cambridge MA 02139 USA Tel Aviv Univ Tel Aviv Israel

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 sublinear time and space local computation algorithms have been developed - we will give special focus to finding maximal independent sets and sparse spanning graphs.

关键词： sublinear time algorithms randomized algorithms approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform

引用

ACM TRANSACTIONS ON algorithms 2017年第3期13卷 34-34页

作者： Cheraghchi, Mahdi Indyk, Piotr Imperial Coll London Dept Comp London England MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA

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).

关键词： Sparse recovery sparse Fourier transform explicit constructions pseudorandomness sublinear time algorithms sketching

来源：评论

学校读者我要写书评

暂无评论

Testing Linear-Invariant Properties: 收藏
分享
引用; SIAM Journal on Computing 2022年第4期51卷 1230-1279页; 作者： Jonathan Tidor Yufei Zhao; We study the property testing of functions Fn<span class="mi" id="MathJax-Span-8" style="font-size: 70.7%; font-family: Mat; We study the property testing of functions $F_{p}^{n} \to [R]$; 来源：评论; 学校读者我要写书评

暂无评论

Algebraic Property Testing: The Role of Invariance 08

Algebraic Property Testing: The Role of Invariance

引用

ACM Symposium on Theory of Computing

作者： Tali Kaufman Madhu Sudan IAS Princeton MIT CSAIL

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

关键词： Error-correcting codes Locally testable codes sublinear time algorithms Invariant Algebra Lower bound invariance Affine transformation linear transformations Discrete-time algorithm Performance Tests Error correction codes Testability Function

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法