On sets turing reducible to p-selective sets

We consider sets Turing reducible to p-selective sets under various resource bounds and a restricted number of queries to the oracle. We show that there is a hierarchy among the sets polynomial-time Turing reducible to p-selective sets with respect to the degree of a polynomial bounding the number of adaptive queries used by a reduction. We give a characterization of EXP/poly in terms of exponential-time Turing reducibility to p-selective sets. Finally we show that EXP cannot be reduced to the p-selective sets under 2 ^lin time reductions with at mostn ^k queries for anyfixed k ε N.     

Lower bounds for the polynomial calculus and the Gröbner basis algorithm

Razborov (1996) recently proved that polynomial calculus proofs of the pigeonhole principle must have degree at least ⌈n/2⌉ + 1 over any field. We present a simplified proof of the same result.?Furthermore, we show a matching upper bound on polynomial calculus proofs of the pigeonhole principle for any field of suficiently large characteristic, and an ⌈n/2⌉ + 1 lower bound for any subset sum problem over the field of reals.?We show that these degree lower bounds also translate into lower bounds on the number of monomials in any polynomial calculus proof, and hence on the running time of most implementations of the Gr?bner basis algorithm. Received: October 14, 1997.     

Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds

We show that if Arthur-Merlin protocols can be derandomized, then there is a language computable in deterministic exponential-time with access to an NP oracle that requires circuits of exponential size. More formally, if every promise problem in prAM, the class of promise problems that have Arthur-Merlin protocols, can be computed by a deterministic polynomial-time algorithm with access to an NP oracle, then there is a language in E^NP that requires circuits of size Ω(2 ⁿ /n). The lower bound in the conclusion of our theorem suffices to construct pseudorandom generators with exponential stretch.     

Functions Computable with Nonadaptive Queries to NP

We study FP_|| ^NP , the class of functions that can be computed in polynomial time with nonadaptive queries to an NP oracle. This is motivated by the question of whether it is possible to compute witnesses for NP sets within FP_|| ^NP . The known algorithms for this task all require sequential access to the oracle. On the other hand, there is no evidence known yet that this should not be possible with parallel queries. We define a class of optimization problems based on NP sets, where the optimum is taken over a polynomially bounded range (NPbOpt). We show that if such an optimization problem is based on one of the known NP-complete sets, then it is hard for FP_|| ^NP . Moreover, we characterize FP_|| ^NP as the class of functions that reduces to such optimization functions. We call this property strong hardness. The main question is whether these function classes are complete for FP_|| ^NP . That is, whether it is possible to compute an optimal value for a given optimization problem in FP_|| ^NP . We show that these optimization problems are complete for FP_|| ^NP , if and only if one can compute membership proofs for NP sets in FP_|| ^NP . This indicates that the completeness question is a hard one. Received October 1995, and in final form March 1997.     

Fast Spatial Decomposition and Closest Pair Computation for Limited Precision Input

In this paper we show that if the input points to the geometric closest pair problem are given with limited precision (each coordinate is specified with O( log n) bits), then we can compute the closest pair in O(n log log n) time. We also apply our spatial decomposition technique to the k -nearest neighbor and n -body problems, achieving similar improvements. To make use of the limited precision of the input points, we use a reasonable machine model that allows ``bit shifting' in constant time—we believe that this model is realistic, and provides an interesting way of beating the Ω(n log n) lower bound that exists for this problem using the more typical algebraic RAM model. Received October 12, 1998; revised October 26, 1998.     

A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs

Algorithms used in data mining and bioinformatics have to deal with huge amount of data efficiently.In many applications,the data are supposed to have explicit or implicit structures.To develop efficient algorithms for such data,we have to propose possible structure models and test if the models are feasible.Hence,it is important to make a compact model for structured data,and enumerate all instances efficiently.There are few graph classes besides trees that can be used for a model.In this paper,we inves...     

Inapproximability Results for Guarding Polygons and Terrains

Past research on art gallery problems has concentrated almost exclusively on bounds on the numbers of guards needed in the worst case in various settings. On the complexity side, fewer results are available. For instance, it has long been known that placing a smallest number of guards for a given input polygon is NP -hard. In this paper we initiate the study of the approximability of several types of art gallery problems. Motivated by a practical problem, we study the approximation properties of the three art gallery problems VERTEX GUARD, EDGE GUARD, and POINT GUARD. We prove that if the input polygon has no holes, there is a constant δ >0 such that no polynomial time algorithm can achieve an approximation ratio of 1+δ , for each of these guard problems. We obtain these results by proposing gap-preserving reductions from 5-OCCURRENCE-MAX-3-SAT. We also prove that if the input polygons are allowed to contain holes, then these problems cannot be approximated by a polynomial time algorithm with ratio ((1-ɛ)/12) \ln n for any ɛ > 0 , unless NP \subseteq TIME(n ^{O (log log n)} ) , where n is the number of vertices of the input polygon. We obtain these results by proposing gap-preserving reductions from the SET COVER problem. We show that this inapproximability for the POINT GUARD problem for polygons with holes carries over to the problem of covering a 2.5-dimensional terrain with a minimum number of guards that are placed at a certain fixed height above the terrain. The same holds if the guards may be placed on the terrain itself. Received September 22, 1999; revised December 5, 1999.     

Conjunctions of Unate DNF Formulas: Learning and Structure

A central topic in query learning is to determine which classes of Boolean formulas are efficiently learnable with membership and equivalence queries. We consider the class ^kconsisting of conjunctions ofkunate DNF formulas. This class generalizes the class ofk-clause CNF formulas and the class of unate DNF formulas, both of which are known to be learnable in polynomial time with membership and equivalence queries. We prove that ²can be properly learned with a polynomial number of polynomial-size membership and equivalence queries, but can be properly learned in polynomial time with such queries if and only if P=NP. Thus the barrier to properly learning ²with membership and equivalence queries is computational rather than informational. Few results of this type are known. In our proofs, we use recent results of Hellersteinet al.(1997,J. Assoc. Comput. Mach.43(5), 840–862), characterizing the classes that are polynomial-query learnable, together with work of Bshouty on the monotone dimension of Boolean functions. We extend some of our results to ^kand pose open questions on learning DNF formulas of small monotone dimension. We also prove structural results for ^k. We construct, for any fixedk2, a class of functionsfthat cannot be represented by any formula in ^k, but which cannot be “easily” shown to have this property. More precisely, for any functionfonnvariables in the class, the value offon any polynomial-size set of points in its domain is not a witness thatfcannot be represented by a formula in ^k. Our construction is based on BCH codes.     

Reductions on NP and P-selective sets

P-selective sets are used to distinguish polynomial time-bounded reducibilities on NP. In particular, we consider different kinds of “positive” reductions; these preserve membership in NP and are not a priori closed under complements. We show that the class of all sets which are both P-selective and have positive reductions to their complements is P. This is used to show that if DEXT ≠ NEXT, then there exists a set in NP?P that is not positive reducible to its complement. Various similar results are obtained. We also show that P is the class of all sets which are both p-selective and positive truth-table self-reducible. From this result, it follows that various naturally defined apparently intractible problems are not p-selective unless P = NP.     

Communication complexity towards lower bounds on circuit depth

Karchmer, Raz, and Wigderson (1995) discuss the circuit depth complexity of n-bit Boolean functions constructed by composing up to d = log n/log log n levels of k = log n-bit Boolean functions. Any such function is in AC¹ . They conjecture that circuit depth is additive under composition, which would imply that any (bounded fan-in) circuit for this problem requires depth. This would separate AC¹ from NC¹. They recommend using the communication game characterization of circuit depth. In order to develop techniques for using communication complexity to prove circuit depth lower bounds, they suggest an intermediate communication complexity problem which they call the Universal Composition Relation. We give an almost optimal lower bound of dk—O(d ²(k log k)^1/2) for this problem. In addition, we present a proof, directly in terms of communication complexity, that there is a function on k bits requiring circuit depth. Although this fact can be easily established using a counting argument, we hope that the ideas in our proof will be incorporated more easily into subsequent arguments which use communication complexity to prove circuit depth bounds. Received: July 30, 1999.     

Bounded query machines: On NP and PSPACE

It is shown that NP is equal to PSPACE if and only if for every oracle set A, NP(A) is equal to the class NPQUERY(A) of languages accepted by nondeterministic polynomial space-bounded oracle machines that are allowed to query the oracle for A only a polynomial number of times. Further, it is shown that there is an oracle set B such that NPQUERY(B) is not equal to the class PQUERY(B) of languages accepted by deterministic polynomial space-bounded oracle machines that are allowed to query the oracle for B only a polynomial number of times.     

On log-tape isomorphisms of complete sets

In this paper we study log n-tape computable reductions between sets and investigate conditions under which log n-tape reductions between sets can be extended to log n-tape computable isomorphisms of these sets. As an application of these results we obtain easy to check necessary and sufficient conditions that sets complete under log n-tape reductions in NL, CSL, P, NP, PTAPE, etc. are log n-tape isomorphic to the previously known complete sets in the respective classes. As a matter of fact, all the “known” complete sets for NL, CSL, P, NP, PTAPE, etc. are now easily seen to be, respectively, log n-tape isomorphic. These results strengthen and extend substantially the previously known results about polynomial time computable reductions and isomorphisms of NP and PTAPE complete sets. Furthermore, we show that any set complete in CSL, PTAPE, etc. must be dense and therefore, for example, cannot be over a single letter alphabet.     

On the uselessness of quantum queries

Given a prior probability distribution over a set of possible oracle functions, we define a number of queries to be useless for determining some property of the function if the probability that the function has the property is unchanged after the oracle responds to the queries. A familiar example is the parity of a uniformly random Boolean-valued function over {1,2,…,N}, for which N−1 classical queries are useless. We prove that if 2k classical queries are useless for some oracle problem, then k quantum queries are also useless. For such problems, which include classical threshold secret sharing schemes, our result also gives a new way to obtain a lower bound on the quantum query complexity, even in cases where neither the function nor the property to be determined is Boolean.     

PAC Learning Intersections of Halfspaces with Membership Queries

A randomized learning algorithm {POLLY} is presented that efficiently learns intersections of s halfspaces in n dimensions, in time polynomial in both s and n . The learning protocol is the PAC (probably approximately correct) model of Valiant, augmented with membership queries. In particular, {POLLY} receives a set S of m = poly(n,s,1/ε,1/δ) randomly generated points from an arbitrary distribution over the unit hypercube, and is told exactly which points are contained in, and which points are not contained in, the convex polyhedron P defined by the halfspaces. {POLLY} may also obtain the same information about points of its own choosing. It is shown that after poly(n , s , 1/ε , 1/δ , log(1/d) ) time, the probability that {POLLY} fails to output a collection of s halfspaces with classification error at most ε , is at most δ . Here, d is the minimum distance between the boundary of the target and those examples in S that are not lying on the boundary. The parameter log(1/d) can be bounded by the number of bits needed to encode the coefficients of the bounding hyperplanes and the coordinates of the sampled examples S . Moreover, {POLLY} can be extended to learn unions of k disjoint polyhedra with each polyhedron having at most s facets, in time poly(n , k , s , 1/ε , 1/δ , log(1/d) , 1/γ ) where γ is the minimum distance between any two distinct polyhedra. Received February 5, 1997; revised July 1, 1997.     

Compact Navigation and Distance Oracles for Graphs with Small Treewidth

Given an unlabeled, unweighted, and undirected graph with n vertices and small (but not necessarily constant) treewidth k, we consider the problem of preprocessing the graph to build space-efficient encodings (oracles) to perform various queries efficiently. We assume the word RAM model where the size of a word is Ω(logn) bits. The first oracle, we present, is the navigation oracle which facilitates primitive navigation operations of adjacency, neighborhood, and degree queries. By way of an enumeration argument, which is of interest in its own right, we show the space requirement of the oracle is optimal to within lower order terms for all graphs with n vertices and treewidth k. The oracle supports the mentioned queries all in constant worst-case time. The second oracle, we present, is an exact distance oracle which facilitates distance queries between any pair of vertices (i.e., an all-pairs shortest-path oracle). The space requirement of the oracle is also optimal to within lower order terms. Moreover, the distance queries perform in O(k ³log³ k) time. Particularly, for the class of graphs of popular interest, graphs of bounded treewidth (where k is constant), the distances are reported in constant worst-case time.     

Nonadaptive quantum query complexity

We study the power of nonadaptive quantum query algorithms, which are algorithms whose queries to the input do not depend on the result of previous queries. First, we show that any bounded-error nonadaptive quantum query algorithm that computes a total boolean function depending on n variables must make Ω(n) queries to the input in total. Second, we show that, if there exists a quantum algorithm that uses k nonadaptive oracle queries to learn which one of a set of m boolean functions it has been given, there exists a nonadaptive classical algorithm using queries to solve the same problem. Thus, in the nonadaptive setting, quantum algorithms for these tasks can achieve at most a very limited speed-up over classical query algorithms.     

Space Complexity Vs. Query Complexity

Combinatorial property testing deals with the following relaxation of decision problems: Given a fixed property and an input x, one wants to decide whether x satisfies the property or is “far” from satisfying it. The main focus of property testing is in identifying large families of properties that can be tested with a certain number of queries to the input. In this paper we study the relation between the space complexity of a language and its query complexity. Our main result is that for any space complexity s(n) ≤ log n there is a language with space complexity O(s(n)) and query complexity 2^Ω(s(n)). Our result has implications with respect to testing languages accepted by certain restricted machines. Alon et al. [FOCS 1999] have shown that any regular language is testable with a constant number of queries. It is well known that any language in space o(log log n) is regular, thus implying that such languages can be so tested. It was previously known that there are languages in space O(log n) that are not testable with a constant number of queries and Newman [FOCS 2000] raised the question of closing the exponential gap between these two results. A special case of our main result resolves this problem as it implies that there is a language in space O(log log n) that is not testable with a constant number of queries. It was also previously known that the class of testable properties cannot be extended to all context-free languages. We further show that one cannot even extend the family of testable languages to the class of languages accepted by single counter machines.      

TSP Heuristics: Domination Analysis and Complexity

   Abstract. We show that the 2-Opt and 3-Opt heuristics for the traveling salesman problem (TSP) on the complete graph K _n produce a solution no worse than the average cost of a tour in K _n in a polynomial number of iterations. As a consequence, we get that the domination numbers of the 2- Opt , 3- Opt , Carlier—Villon, Shortest Path Ejection Chain, and Lin—Kernighan heuristics are all at least (n-2)! / 2 . The domination number of the Christofides heuristic is shown to be no more than

Minimum Weakly Fundamental Cycle Bases Are Hard To Find

In the last years, new variants of the minimum cycle basis (MCB) problem and new classes of cycle bases have been introduced, as motivated by several applications from disparate areas of scientific and technological inquiry. At present, the complexity status of the MCB problem is settled only for undirected, directed, and strictly fundamental cycle bases (SFCB’s). Weakly fundamental cycle bases (WFCB’s) form a natural superclass of SFCB’s. A cycle basis of a graph G is a WFCB iff ν=0 or there exists an edge e of G and a circuit C _i in such that is a WFCB of G∖e. WFCB’s still possess several of the nice properties offered by SFCB’s. At the same time, several classes of graphs enjoying WFCB’s of cost asymptotically inferior to the cost of the cheapest SFCB’s have been found and exhibited in the literature. Considered also the computational difficulty of finding cheap SFCB’s, these works advocated an in-depth study of WFCB’s. In this paper, we settle the complexity status of the MCB problem for WFCB’s (the MWFCB problem). The problem turns out to be -hard. However, in this paper, we also offer a simple and practical 2⌈log ₂ n⌉-approximation algorithm for the MWFCB problem. In O(n ν) time, this algorithm actually returns a WFCB whose cost is at most 2⌈log ₂ n⌉∑ _e∈E(G) w _e , thus allowing a fast 2⌈log ₂ n⌉-approximation also for the MCB problem. With this algorithm, we provide tight bounds on the cost of any MCB and MWFCB.