One of the central open questions in the theory of average-case complexity is to establish the equivalence between the worst-case and average-case complexity of the Polynomial-time Hierarchy (PH). One general approach is to show that there exists a PH-computable hitting set generator whose security is based on some NP-hard problem. We present the limits of such an approach, by showing that there exists no exponential-time-computable hitting set generator whose security can be proved by using a nonadaptive randomized polynomial-time reduction from any problem outside AM ∩ coAM, which significantly improves the previous upper bound BPP^NP of Gutfreund and Vadhan (RANDOM/APPROX 2008 [Gutfreund and Vadhan, 2008]). In particular, any security proof of a hitting set generator based on some NP-hard problem must use either an adaptive or non-black-box reduction (unless the polynomial-time hierarchy collapses). To the best of our knowledge, this is the first result that shows limits of black-box reductions from an NP-hard problem to some form of a distributional problem in DistPH. Based on our results, we argue that the recent worst-case to average-case reduction of Hirahara (FOCS 2018 [Hirahara, 2018]) is inherently non-black-box, without relying on any unproven assumptions. On the other hand, combining the non-black-box reduction with our simulation technique of black-box reductions, we exhibit the existence of a "non-black-box selector" for GapMCSP, i.e., an efficient algorithm that solves GapMCSP given as advice two circuits one of which is guaranteed to compute GapMCSP.

We show that the counting class LWPP remains unchanged even if one allows a polynomial number of gap values rather than one. On the other hand, we show that it is impossible to improve this from polynomially many gap values to a superpolynomial number of gap values by relativizable proof techniques. The first of these results implies that the Legitimate Deck Problem (from the study of graph reconstruction) is in LWPP (and thus low for PP, i.e., $$\rm PP^{Legitimate Deck} = PP$$ ) if the weakened version of the Reconstruction Conjecture holds in which the number of nonisomorphic preimages is assumed merely to be polynomially bounded. This strengthens the 1992 result of Köbler, Schöning & Torán that the Legitimate Deck Problem is in LWPP if the Reconstruction Conjecture holds, and provides strengthened evidence that the Legitimate Deck Problem is not NP-hard. We additionally show on the one hand that our LWPP robustness result also holds for WPP, and also holds even when one allows both the rejection and acceptance gap-value targets to simultaneously be polynomial-sized lists; yet on the other hand, we show that for the $$\#{\rm P}$$ -based analogue of LWPP the behavior much differs in that, in some relativized worlds, even two target values already yield a richer class than one value does. Despite that nonrobustness result for a $$\#{\rm P}$$ -based class, we show that the $$\#{\rm P}$$ -based “exact counting” class $${\rm C}_{=}{\rm P}$$ remains unchanged even if one allows a polynomial number of target values for the number of accepting paths of the machine.

The Minimum Circuit Size Problem (MCSP) is known to be hard for statistical zero knowledge via a BPP-Turing reduction (Allender and Das, 2014), whereas establishing NP-hardness of MCSP via a polynomial-time many-one reduction is difficult (Murray and Williams, 2015) in the sense that it implies ZPP != EXP, which is a major open problem in computational complexity. In this paper, we provide strong evidence that current techniques cannot establish NP-hardness of MCSP, even under polynomial-time Turing reductions or randomized reductions: Specifically, we introduce the notion of oracle-independent reduction to MCSP, which captures all the currently known reductions. We say that a reduction to MCSP is oracle-independent if the reduction can be generalized to a reduction to MCSP^A for any oracle A, where MCSP^A denotes an oracle version of MCSP. We prove that no language outside P is reducible to MCSP via an oracle-independent polynomial-time Turing reduction. We also show that the class of languages reducible to MCSP via an oracle-independent randomized reduction that makes at most one query is contained in AM intersect coAM. Thus, NP-hardness of MCSP cannot be established via such oracle-independent reductions unless the polynomial hierarchy collapses. We also extend the previous results to the case of more general reductions: We prove that establishing NP-hardness of MCSP via a polynomial-time nonadaptive reduction implies ZPP != EXP, and that establishing NP-hardness of approximating circuit complexity via a polynomial-time Turing reduction also implies ZPP != EXP. Along the way, we prove that approximating Levin's Kolmogorov complexity is provably not EXP-hard under polynomial-time Turing reductions, which is of independent interest.

We show that the reach ability problem over {\em directed planar graphs} can be solved simultaneously in polynomial time and approximately $O(\sqrt{n})$ space. In contrast, the best space bound known for the reach ability problem on general directed graphs with polynomial running time is $O(n/2^{\sqrt{\log n}})$.

The Valiant-Vazirani Isolation Lemma provides an efficient procedure for isolating a satisfying assignment of a given satisfiable circuit: Given a Boolean circuit C on n input variables, the procedure outputs a new circuit C' on the same n input variables such that (i) every satisfying assignment of C' also satisfies C, and (ii) if C is satisfiable, then C' has exactly one satisfying assignment. In particular, if C is unsatisfiable, then (i) implies that C' is unsatisfiable. The Valiant-Vazirani procedure is randomized, and when C is satisfiable it produces a uniquely satisfiable circuit C' with probability Omega(1/n). Is it possible to have an efficient deterministic witness-isolating procedure? Or, at least, is it possible to improve the success probability of a randomized procedure to a large constant? We argue that the answer is likely `No'. More precisely, we prove that there exists a non-uniform randomized polynomial-time witness-isolating procedure with success probability bigger than 2/3 if and only if NP is in P/poly. Thus, an improved witness-isolating procedure would imply the collapse of the polynomial-time hierarchy. We establish similar results for other variants of witness isolation, such as reductions that remove all but an odd number of satisfying assignments of a satisfiable circuit. We also consider a black box setting of witness isolation that generalizes the setting of the Valiant-Vazirani Isolation Lemma, and give an upper bound of O(1/n) on the success probability for a natural class of randomized witness-isolating procedures.

Hash Distributed A* (HDA*) is a parallel A* algorithm that is proven to be effective in optimal sequential planning with unit edge costs. HDA* leverages the Zobrist function to almost uniformly distribute and schedule work among processors. This paper evaluates the performance of HDA * in optimal sequence alignment. We observe that with a large number of CPU cores HDA* suffers from an increase of search overhead caused by reexpansions of states in the closed list due to nonuniform edge costs in this domain. We therefore present a new work distribution strategy limiting processors to distribute work, thus increasing the possibility of detecting such duplicate search effort. We evaluate the performance of this approach on a cluster of multi-core machines and show that the approach scales well up to 384 CPU cores.

Parallelizing Monte Carlo tree search (MCTS) has been considered to be a way to improve the strength of Computer Go programs. In this paper, we analyze the performance of two root parallelization methods: the standard strategy based on average selection and our new strategy based on majority voting. As a starting code base, we used Fuego, which is one of the best programs available. Our experimental results with 64 central processing unit (CPU) cores show that majority voting outperforms average selection. Additionally, we show through an extensive analysis that root parallelization has limitations.

The Berman-Hartmanis conjecture states that all NP-complete sets are P-isomorphic each other. On this conjecture, we first improve the previous result of Agrawal and show that all NP-complete sets are lesli,1-1P/poly-reducible to each other based on the assumption that there exist regular one way functions that cannot be inverted by randomized polynomial time algorithms. Secondly, we show that, besides the above assumption, if all one-way functions have some easy part to invert, then all NP-complete sets are P/poly-isomorphic to each other.

Support Vector Machines are a family of algorithms for the analysis of data based on convex Quadratic Programming. We derive randomized algorithms for training SVMs, based on a variation of Random Sampling Techniques; these have been successfully used for similar problems. We formally prove an upper bound on the expected running time which is quasilinear with respect to the number of data points and polynomial with respect to the other parameters, i.e., the number of attributes and the inverse of a chosen soft margin parameter. [This is the combined journal version of the conference papers (Balcázar, J.L. et al. in Proceedings of 12th International Conference on Algorithmic Learning Theory (ALT’01), pp. 119–134, [ 2001 ]; Balcázar, J.L. et al. in Proceedings of First IEEE International Conference on Data Mining (ICDM’01), pp. 43–50, [ 2001 ]; and Balcázar, J.L. et al. in Proceedings of SIAM Workshop in Discrete Mathematics and Data Mining, pp. 19–29, [ 2002 ]).]

We consider the problem of proving circuit lower bounds against the polynomial-time hierarchy. We give both positive and negative results. For the positive side, for any fixed integer k>>0, we give an explicit $\Sigma^{\rm p}_2$ language, acceptable by a $\Sigma^{\rm p}_2$ machine with running time O(n k 2 +k ), that requires circuit size >n k . This provides a constructive version of an existence theorem of R. Kannan [Inform. and Control, 55 (1982), pp. 40--56]. Our main theorem is on the negative side. We give evidence that it is infeasible to give relativizable proofs that any single language in the polynomial-time hierarchy requires superpolynomial circuit size. Our proof techniques are based on the decision tree version of the Switching Lemma for constant depth circuits and the Nisan--Wigderson pseudorandom generator. We also take this opportunity to publish some previously unpublished older results of the first author on constant depth circuits, both straight lower bounds and inapproximability results based on decision tree--type Switching Lemmas.

We consider the resource bounded measure of polynomial-time learnable subclasses of polynomial-size circuits. We show that if EXP/spl ne/MA, then every PAC-learnable subclass of P/poly has EXP-measure zero. We introduce a nonuniformly computable variant of resource bounded measure and show that, for every fixed polynomial q, any polynomial-time learnable subclass of circuits of size q has measure zero with respect to P/poly. We relate our results to the question whether Boolean Circuits are polynomial-time learnable.

We show that if a self-reducible set has polynomial-size circuits, then it is low for the probabilistic class ZPP (NP). As a consequence we get a deeper collapse of the polynomial-time hierarchy PH to ZPP(NP) under the assumption that NP has polynomial-size circuits. This improves on the well-known result in Karp and Lipton [ Proceedings of the 12th ACM Symposium on Theory of Computing, ACM Press, New York, 1980, pp. 302--309] stating a collapse of PH to its second level $\Sigmap_2$ under the same assumption. Furthermore, we derive new collapse consequences under the assumption that complexity classes like UP, FewP, and C=P have polynomial-size circuits. Finally, we investigate the circuit-size complexity of several language classes. In particular, we show that for every fixed polynomial s, there is a set in ZPP(NP) which does not have O(s(n))-size circuits.

We prove that the join of two sets may actually fall into a lower level of the extended low hierarchy than either of the sets. In particular, there exist sets that are not in the second level of the extended low hierarchy, EL2, yet their join is in EL2. That is, in terms of extended lowness, the join operator can lower complexity. Since in a strong intuitive sense the join does not lower complexity, our result suggests that the extended low hierarchy is unnatural as a complexity measure. We also study the closure properties of EL2 and prove that EL2 is not closed under certain Boolean operations. To this end, we establish the first known (and optimal) EL2 lower bounds for certain notions generalizing P-selectivity, which may be regarded as an interesting result in its own right.

For any operatorτon integer-valued functions, we say that #P isclosed under τ in the context ofPF∘#P if, for everyf∈#P,τ[f] belongs to PF∘num;P. For several operatorsτ, it is shown that the closure properties of #P underτin the above sense is closely related to the relationships between P#P[1]and higher classes such as PHPPand PPPP.

Sequential algorithms given by Angluin 1987 and Schapire 1992 learn deterministic nite automata DFA exactly from Membership and Equivalence queries.These algorithms are feasible, in the sense that they take time polynomial in n and m, where n is the number of states of the automaton and m is the length of the longest counterexample to an Equivalence query.This paper studies whether parallelism can lead to substantially more e cient algorithms for the problem.We show that no CRCW PRAM machine using a number of processors polynomial in n and m can identify DFA in on= log n time.Furthermore, this lower bound is tight up to constant factors: we develop a CRCW PRAM learning algorithm that uses polynomially many processors and exactly learns DFA in time On= log n.

We introduce a measure for the computational complexity of mdiwdual instances of a decision problem and study some of Its properties.The instance complexity of a string ~with respect to a set A and time bound t, ict(x : A). is defined as the size of the smallest special-case program for A that run> m time t,decides x correctly, and makes no mistakes on other strings ("don't know" answers are permitted).We prove that a set A is m P if and only if there exist a polynomial t and a constant c such that ic'(x : A) < c for all X; on the other hand, If A ]s NP-hard and P # NP, then for all polynomials t and constants c. lc'(~: A) > c log I ~I for ]nfimtely many x.Obserwng that Kf(x), the t-bounded Kolmogorov complexity of x, N roughly an upper bound on ]Ct(.t: A), we proceed to investigate the existence of mdiwdually hard problem Instances.].e , strings whose instance complexity E close to their Kolmogorov complexity.We prove that if t(n) z n is a time-constructible function and A 1s a recurswe set not in DTIME(t), there then exist a constant c and mfimtely many I such that ic'(x : ,4) z K' (x) -c. for some Prehmmary versions of parts of this work have appeared under the titles "What 1s a hard instance of a computational problem?" m Proceedings of tize Conference on Structare m Cornplexm Theory (Berkeley, Calif., June i 986), and "On the instance complexity of NP-hard problems" in Procecduzgs of the 5tk .4nrrualConference on StntctLwe m Cowrpkwty Theory (Barcelona, Spain, July 1990).

For a set L that is polynomial-time reducible (in short, $ \leqslant _{\text{T}}^{\text{P}} $-reducible) to some sparse set, the authors investigate the computational complexity of such sparse sets relative to L and prove the first lower bounds on the complexity of recognizing such sets. Sets A and B are constructed such that both of them are $ \leqslant _{\text{T}}^{\text{P}} $-reducible to some sparse set, but A (respectively, B) is $ \leqslant _{\text{T}}^{\text{P}} $-reducible to no sparse set in ${\text{P}}^A $ (respectively, ${\text{NP}}^B \cap {\text{co-NP}}^B $); that is, the complexity of sparse sets to which A (respectively, B) is $ \leqslant _{\text{T}}^{\text{P}} $-reducible is more than ${\text{P}}^A $ (respectively, ${\text{NP}}^B \cap {\text{co-NP}}^B $). From these results or application of the proof technique the authors obtain (1) lower bounds for the relative complexity of generating polynomial-size circuits for some sets in ${{\text{P}} / {{\operatorname{poly}}}}$ and (2) separations of the classes of sets equivalent or reducible to sparse sets under various polynomial-time reducibilities.

For various polynomial-time reducibilities r, this paper asks whether being r-reducible to a sparse set is a broader notion than being r-equivalent to a sparse set. Although distinguishing equivalence and reducibility to sparse sets, for many-one or 1-truth-table reductions, would imply that $P \ne NP$, this paper shows that for k-truth-table reductions, $k \geq 2$, equivalence and reducibility to sparse sets provably differ. Though Gavaldà and Watanabe have shown that, for any polynomial-time computable unbounded function $f( \cdot )$, some sets $f(n)$-truth-table reducible to sparse sets are not even Turing equivalent to sparse sets, this paper shows that extending their result to the 2-truth-table case would provide a proof that $P\ne NP$. Additionally, this paper studies the relative power of different notions of reducibility, and proves that disjunctive and conjunctive truth-table reductions to sparse sets are surprisingly powerful, refuting a conjecture of Ko.

It is proved that if ${\text{P}} \ne {\text{NP}}$, then there exists a set in ${\text{NP}}$ that is not polynomial-time bounded truth-table reducible (in short, $ \leqq _{{\text{btt}}}^{\text{P}} $-reducible) to any sparse set. In other words, it is proved that no sparse $ \leqq _{{\text{btt}}}^{\text{P}} $-hard set exists for ${\text{NP}}$ unless ${\text{P}} = {\text{NP}}$. By using the technique proving this result, the intractability of several number-theoretic decision problems, i.e., decision problems defined naturally from number-theoretic problems is investigated. It is shown that for these number-theoretic decision problems, if it is not in ${\text{P}}$, then it is not $ \leqq _{{\text{btt}}}^{\text{P}} $-reducible to any sparse set.

We prove that if P ¢ NP, then there exists a set in NP that is polynomial time bounded truth-table reducible (in short, <Ptt-reducible) to no sparse set.In other words, we prove that no sparse <bPtt-hard set exists for NP unless P = NP.By using the technique proving this result, we investigate intractability of several number theoretic decision problems, i.e., decision problems defined naturally from number theoretic problems.We show that for those number theoretic decision problems, if it is not in P, then it is <~tt-reducible to no sparse set.

It is known that $AM = BP \cdot NP$. Babai [Proc. 17th Annual ACM Symposium Theory of Computing, 1985, pp. 421–429] and Goldwasser and Sipser [Proc.18th Annual ACM Symposium on Theory of Computing, 1986, pp. 59–68] asked whether $BP \cdot NP{\text{ for almost every set }}B,A \in NP(B)\}$ is equal to $\{ A|$ . This question is still open. In this paper it is shown that (1) for every $k \geqq 0$ and every set $A,A \in BP \cdot \Sigma _k^P $ if and only if for almost every tally set , and (2) for every $k \geqq 0$ and almost every tally set $T,BP \cdot \Sigma _k^P (T) = \Sigma _k^P (T)$. From them are obtained some properties of the “BP-polynomial-time hierarchy” studied by Schoning [Proc. 2nd Annual Conference on Structure in Complexity Theory, 1987, pp. 2–8]. That is, the $BP$-polynomial-time hierarchy has the properties that are precisely parallel to those of the polynomial-time hierarchy. The proofs of these results provide examples of the use of properties of complexity classes specified by relativizations to obtain properties of unrelativized complexity classes.

The notion of “lowness” was introduced in computational complexity theory by Schöning [J, Comput. Systems Sci., 27 (1983), pp. 14–28] who studied sets in the class NP. This notion may be interpreted as setting an upper bound on the amount of information that can be encoded by a set. Here ideas from previous studies are incorporated in order to capture the notion of a set being exponentially low. The main result asserts the existence of a sparse set E such that ${\operatorname{DEXT}}(E) = {\operatorname{DEXT}}$, i.e., E is “exponentially low,” but E is not in the class P. In contrast, any set with small generalized Kolmogorov complexity that is exponentially low must be in the class P. In addition, we show that for each $k \geqq 2$, any sparse set S that is low with respect to the class $\Sigma _k^E $ of the exponential-time hierarchy (i.e., $\Sigma _k^E {(S) = \Sigma _k^E } $ ) must be in the class $\Sigma _k^P $ of the polynomial-time hierarchy. Similarly, for each $k \geqq 4$, any set with polynomial-size circuits that is low with respect to the class $\Sigma _k^E $ must be in the class $\Sigma _k^P $ .