A hypergraph dictatorship test is first introduced by Samorodnitsky and Trevisan and serves as a key component in their unique games based @math construction. Such a test has oracle access to a collection of functions and determines whether all the functions are the same dictatorship, or all their low degree influences are o (1). Their test makes q *** 3 queries, has amortized query complexity @math , but has an inherent loss of perfect completeness. In this paper we give an (adaptive) hypergraph dictatorship test that achieves both perfect completeness and amortized query complexity @math .
The orthogonal question of designing testers or @math s with as few queries as possible was also considered. In a highly influential paper @cite_8 , H stad constructed a @math system making only three queries. Many variants also followed. In particular @math systems with perfect completeness making three queries were also achieved in @cite_2 @cite_15 . Similar to our approach, O'Donnell and Wu @cite_10 designed an optimal three bit dictatorship test with perfect completeness, and later the same authors constructed a conditional @math system @cite_11 .
@cite_8 @cite_2 @cite_15 @cite_10 @cite_11
1556276033 2133344054 1551374365 1970259241
In the conclusion of his monumental paper on optimal inapproximability results, Hastad [13] suggested that Fourier analysis of Dictator (Long Code) Tests may not be universally applicable in the study of CSPs. His main open question was to determine if the technique could resolve the approximability of satisfiable 3-bit constraint satisfaction problems. In particular, he asked if the "Not Two" (NTW) predicate is non-approximable beyond the random assignment threshold of 5 8 on satisfiable instances. Around the same time, Zwick [30] showed that all satisfiable 3-CSPs are 5 8-approximable and conjectured that the 5 8 is optimal. In this work we show that Fourier analysis techniques can produce a Dictator Test based on NTW with completeness 1 and soundness 5 8. Our test's analysis uses the Bonami-Gross-Beckner hypercontractive inequality. We also show a soundness lower bound of 5 8 for all 3-query Dictator Tests with perfect completeness. This lower bound for Property Testing is proved in part via a semidefinite programming algorithm of Zwick [30]. Our work precisely determines the 3-query "Dictatorship Testing gap". Although this represents progress on Zwick's conjecture, current PCP "outer verifier" technology is insufficient to convert our Dictator Test into an NP-hardness-of-approximation result. It is known that there exists a PCP characterization of NP where the verifier makes 3 queries and has a one-sided error that is bounded away from 1; and also that 2 queries do not suffice for such a characterization. Thus PCPs with 3 queries possess non-trivial verification power and motivate the task of determining the lowest error that can be achieved with a 3-query PCP. Recently, Hastad (1997) has shown a tight characterization of NP by constructing a 3-query PCP verifier with "error" arbitrarily close to 1 2. Unfortunately this verifier makes two-sided error and Hastad makes essential use of this feature. One-sided error, on the other hand, is a natural notion to associate with a proof system, since it has the desirable property that every rejected proof has a short counterexample. The question of determining the smallest error for which there exists a 3-query PCP verifier making one-sided error and accepting an NP-complete language, however, remained open. We resolve this question by showing that NP has a 3-query PCP with a one-sided error that is arbitrarily close to 1 2. This characterization is tight, i.e., the error cannot be lower. This result is in seeming contradiction with the results of Trevisan (1997) and Zwick (1998) who show that in order to recognize an NP-complete language, the error probability of a PCP verifier making 3 non-adaptive queries and having one-sided error must be at least 5 8. We get around this bottleneck by designing an adaptive 3-query PCP for NP. Our result yields the first tight analysis of an adaptive PCP; and reveals a previously unsuspected separation between the powers of adaptive and non-adaptive PCPs. Our design and analysis of adaptive PCPs can be extended to higher number of queries as well and we give an example of such a proof system with 5 queries. Our adaptive verifiers yield proof systems whose error probabilities match those of previous constructions, while also achieving one-sidedness in the error. This raises new questions about the power of adaptive PCPs, which deserve further study. We consider the problem of answering queries from databases that may be incomplete. A database is incomplete if some tuples may be missing from some relations, and only a part of each relation is known to be complete. This problem arises in several contexts. For example, systems that provide access to multiple heterogeneous information sources often encounter incomplete sources. The question we address is to determine whether the answer to a specific given query is complete even when the database is incomplete. We present a novel sound and complete algorithm for the answer-completeness problem by relating it to the problem of independence of queries from updates. We also show an important case of the independence problem (and therefore ofthe answer-completeness problem) that can be decided in polynomial time, whereas the best known algorithm for this case is exponential. This case involves updates that are described using a conjunction of comparison predicates. We also describe an algorithm that determines whether the answer to the query is complete in the current state of the database. Finally, we show that our ‘treatment extends naturally to partiallyincorrect databases. Permission to copy without fee all or part of this material is granted provided that the copies aTe not made OT distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Very Large Data Base Endowment. To copy otherwise, OT to republish, requirea a fee and or special permission from the Endowment. Proceedings of the 22nd VLDB Conference Mumbai(Bombay), India, 1996 We show that a parallel repetition of any two-prover one-round proof system (MIP(2,1)) decreases the probability of error at an exponential rate. No constructive bound was previously known. The constant in the exponent (in our analysis) depends only on the original probability of error and on the total number of possible answers of the two provers. The dependency on the total number of possible answers is logarithmic, which was recently proved to be almost the best possible [U. Feige and O. Verbitsky, Proc.11th Annual IEEE Conference on Computational Complexity, IEEE Computer Society Press, Los Alamitos, CA, 1996, pp. 70--76].