Abstract Fix any $$\lambda \in \mathbb {C}$$ λ ∈ C . We say that a set $$S\subseteq \mathbb {C}$$ S ⊆ C is $$\lambda $$ λ -convex if, whenever a and b are in S , the point $$(1-\lambda )a+\lambda b$$ ( 1 - λ ) a + λ b is also in S . We investigate the properties of $$\lambda $$ λ -convex sets and their (topological) closures, and we prove a number of facts about them. Let $$Q_\lambda \subseteq \mathbb {C}$$ Q λ ⊆ C be the least $$\lambda $$ λ -convex superset of $$\{0,1\}$$ { 0 , 1 } . Generalizing results of R. G. E. Pinch, we give a sufficient condition on $$\lambda $$ λ for $$Q_\lambda $$ Q λ and some other related $$\lambda $$ λ -convex sets to be discrete by introducing the notion of a strong PV number . These conditions give rise to a number of periodic and aperiodic Meyer sets (often regarded as the mathematical counterpart of “quasicrystals”). This paper is in two parts: Part I (Theory, Sections 1–6) gives general results about $$\lambda $$ λ -convex sets and explores the connections between $$\lambda $$ λ -convex sets and quasicrystals; Part II (Applications, Sections 7–11) applies the results of Part I to a number of special cases. In Part II, we also display several aperiodic $$\lambda $$ λ -convex sets, including several with dihedral symmetry. Section 11 in Part II contains conjectures, open problems, and other suggestions for further research. Our work combines elementary concepts and techniques from algebra and plane geometry. Our results extend and generalize previous work of Pinch, Berman & Moody, and Masáková, Patera, & Pelantová. An extended paper that includes the results given here among many others is available online.

We study properties of non-uniform reductions and related completeness notions. We strengthen several results of Hitchcock and Pavan (ICALP (1), Lecture Notes in Computer Science, vol. 4051, pp. 465–476, Springer, 2006 ) and give a trade-off between the amount of advice needed for a reduction and its honesty on NEXP. We construct an oracle relative to which this trade-off is optimal. We show, in a more systematic study of non-uniform reductions, among other things that non-uniformity can be removed at the cost of more queries. In line with Post’s program for complexity theory (Buhrman and Torenvliet in Bulletin of the EATCS 85, pp. 41–51, 2005 ) we connect such ‘uniformization’ properties to the separation of complexity classes.

For any q>1, let MOD/sub q/ be a quantum gate that determines if the number of 1's in the input is divisible by q. We show that for any q, t>1, MODP is equivalent to MOD/sub t/ (up to constant depth). Based on the case q=2, C. Moore (1999) has shown that quantum analogs of AC/sup (0)/, ACC[q], and ACC, denoted QAC/sub wf//sup (0)/ QACC[2], QACC respectively, define the same class of operators, leaving q>2 as an open question. Our result resolves this question, proving that QAC/sub wf//sup (0)/=QACC[q] QACC for all q. We also develop techniques for proving upper bounds for QACC in terms of related language classes. We define classes of languages EQACC, NQACC and BQACC/sub Q/. We define a notion of log-planar QACC operators and show the appropriately restricted versions of QACC and BQACC are contained in P/poly. We also define a notion of log-gate restricted QACC operators and show the appropriately restricted versions of QACC and NQACC are contained in TC/sup (0)/. To do this last proof; we show that TC/sup (0)/ can perform iterated addition and multiplication in certain field extensions. We also introduce the notion of a polynomial-size tensor graph and we show that families of such graphs can encode the amplitudes resulting from applying an arbitrary QACC operator to an initial state.

Assuming that the polynomial hierarchy (PH) does not collapse, we show the existence of ascending sequences of ptime Turing degrees of length /spl omega//sub 1//sup CK/ all of which are in PSPACE and uniformly hard for PH, such that successors are NP-jumps of their predecessors. This is analogous to the hyperarithmetic hierarchy which is defined similarly but with the (recursive) Turing degrees. The lack of uniform least upper bounds for ascending sequences of ptime degrees causes (the limit levels of) our hyper-polynomial hierarchy to be inherently non-canonical. This problem is investigated in depth, and various possible structures for hyper-polynomial hierarchies are explicated, as are properties of the NP-jump operator on the languages which are in PSPACE but not in PH.

We develop and experiment with a new parallel algorithm to approximate the maximum weight cut in a weighted undirected graph. Our implementation starts with the recent (serial) algorithm of Goemans and Williamson for this problem. We consider several different versions of this algorithm, varying the interior-point part of the algorithm in order to optimize the parallel efficiency of our method. Our work aims for an efficient, practical formulation of the algorithm with close-to-optimal parallelization. We analyze our parallel algorithm in the LogP model and predict linear speedup for a wide range of the parameters. We have implemented the algorithm using the message passing interface (MPI) and run it on several parallel machines. In particular, we present performance measurements on the IBM SP2, the Connection Machine CM5, and a cluster of workstations. We observe that the measured speedups are predicted well by our analysis in the LogP model. Finally, we test our implementation on several large graphs (up to 13,000 vertices), particularly on large instances of the Ising model.

This paper focuses on complexity classes of partial functions that are computed in polynomial time with oracles in NPMV, the class of all multivalued partial functions that are computable nondeterministically in polynomial time. Concerning deterministic polynomial-time reducibilities, it is shown that a multivalued partial function is polynomial-time computable with k adaptive queries to NPMV if and only if it is polynomial-time computable via 2 k-1 nonadaptive queries to NPMV; a characteristic function is polynomial-time computable with k adaptive queries to NPMV if and only if it is polynomial-time computable with k adaptive queries to NP; unless the Boolean hierarchy collapses, for every k, k adaptive (nonadaptive) queries to NPMV are different than k+1 adaptive (nonadaptive) queries to NPMV. Nondeterministic reducibilities, lowness, and the difference hierarchy over NPMV are also studied. The difference hierarchy for partial functions does not collapse unless the Boolean hierarchy collapses, but, surprisingly, the levels of the difference and bounded query hierarchies do not interleave (as is the case for sets) unless the polynomial hierarchy collapses.

We investigate the problem of learning disjunctions of counting functions, which are general cases of parity and modulo functions, with equivalence and membership queries. We prove that, for any prime number p, the class of disjunctions of integer-weighted counting functions with modulus p over the domain Zqn (or Zn) for any given integer q ⩾ 2 is polynomial time learnable using at most n + 1 equivalence queries, where the hypotheses issued by the learner are disjunctions of at most n counting functions with weights from Zp. In general, a counting function may have a composite modulus. We prove that, for any given integer q ⩾ 2, over the domain Z2n, the class of read-once disjunctions of Boolean-weighted counting functions with modulus q is polynomial-time learnable with only one equivalence query and O(nq) membership queries.

We study the class coNPMV of complements of NPMV functions. Though defined symmetrically to NPMV this class exhibits very different properties. We clarify the complexity of coNPMV by showing that it is essentially the same as that of NPMV/sup NP/ complete functions for coNPMV are exhibited and central complexity-theoretic properties of this class are studied. We show that computing maximum satisfying assignments can be done in coNPMV, which leads us to a comparison of NPMV and coNPMV with Krentel's classes Max P and Min P. The difference hierarchy for NPMV is related to the query hierarchy for coNPMV. Finally, we examine a functional analogue of Chang and Kadin's relationship between a collapse of the Boolean hierarchy over NP and a collapse of the polynomial time hierarchy.

We develop a bounded version of the finite injury priority method in recursion theory. We use this to study the learnability of unions of rectangles over the domain {0, …, n − 1}d with only equivalence queries. Applying this method, we show three main results: (1)The class of unions of rectangles is polynomial time learnable for constant dimension d. (2)The class of unions of rectangles whose projections at some unknown dimension are pairwise-disjoint is polynomial time learnable. (3)The class of unions of two disjoint rectangles is polynomial time learnable with unions of two rectangles as hypotheses.

Scalable sets are defined and their properties studied. It is shown that the set of scalable sets is the isomorphism closure of the set of rankable sets and that every scalable set is P-isomorphic to some rankable set. Scalable sets coincide with P-printable sets when sparse, and with P-paddable sets when thick. Using scalability as a tool, the P-isomorphism question for polynomial-time computable sets of similar densities is examined. 1 Introduction This paper defines and investigates the new concept of scalability for polynomial-time sets. A set is scalable if there is an efficient method for computing the number of elements in the set (or its complement) which are less than a given element, relative to some polynomial-time computable and invertible order on \\Sigma . All scalable sets are polynomial-time computable. Scalability generalizes the previously studied concept of ranking which was based on the same property with respect to a fixed ordering, the lexicographic ordering, ...

Although many learning problems can be reduced to learning Boolean functions, in many cases a more efficient learning algorithm can be

We investigate the problem of learning disjunctions of counting functions, generalizations of parity and modulo functions, with equivalence and membership queries. We prove that, for any prime number p, the class of disjunctions of integer-weighted counting functions with modulus p over the domain Znq (or Zn) for any given integer q≥2, is polynomial time learnable using at most n+1 equivalence queries. The hypotheses issued by the learner are disjunctions of at most n counting functions with weights from Zp. In general a counting function may have a composite modulus. We prove that, for any given integer q≥2, over the domain Zn2, the class of read-once disjunctions of Boolean-weighted counting functions with modulus q is polynomial time learnable with only one equivalence query and O(nq) membership queries. And the class of disjunctions of loglogn Boolean-weighted counting functions with modulus q is polynomial time learnable.

We present a polynomial time online learning algorithm that learns any discretized geometric concept generated from any number of halfspaces with any number of known (to the learner) slopes in a constant dimensional space. In particular, our algorithm learns (from equivalence queries only) unions of discretized axis-parallel rectangles in a constant dimensional space in polynomial time. The algorithm also runs in polynomial time in l if the teacher lies on l counterexamples. We then show a PAC-learning algorithm for the above discretized geometric concept when the example oracle lies on the labels of the examples with a fixed probability p/spl les/ 1/2 -1/r that runs in polynomial time also with r. We use these methods, as well as a bounded version of the finite injury priority method, to construct algorithms for learning several classes of rectangles. In particular we design efficient algorithms for learning several classes of unions of discretized axis-parallel rectangles in either arbitrary dimensional spaces or constant dimensional spaces.>

Two necessary and sufficient conditions for all E-complete sets to contain dense P subsets are shown. We then prove that every ≤pm-hard for E set and its complement contain dense E∩UP subsets. As a corollary, every NE-complete set and its complement contain dense E∩UP subsets.

Ogiwara and Watanabe showed that if SAT is bounded truth-table reducible to a sparse set, then P = NP. In this paper we simplify their proof, strengthen the result and use it to obtain several new results. Among the new results are the following: Applications of the main theorem to log-truth-table and log-Turing reductions of NP sets to sparse sets. One typical example is that if SAT is log-truth-table reducible to a sparse set then NP is contained in DTIME (2O(log2n)). Generalizations of the main theorem which yields results similar to the main result at arbitrary levels of the polynomial hierarchy and which extend as well to strong nondeterministic reductions. The construction of an oracle relative to which P ≠ NP but there are NP-complete sets which are f(n)-tt-reducible to a tally set, for any f(n) ε ω(log n). This implies that, up to relativization, some of our results are optimal.

There exists an oracle, relative to which, P ≠ NP, and each of the following properties hold: (i)All Σ2P-complete sets are p-isomorphic; (ii)P-inseparable pairs of sets in NP do not exist; (iii)Intractable public-key cryptosystems do not exist; (iv)NP-complete sets are closed under union of disjoint sets. Remarkably, these properties all follow from one oracle construction. Namely, we prove that there is an oracle A such that every two disjoint sets in NPA are P-separable, and Σ2P = U DTIME(2P)| p is a polynomial. Additional related relativization results are presented also.

A set A is m-reducible to a set B if and only if there is a polynomial-time computable function f such that for all x, $x \in A \Leftrightarrow f(x) \in B$. A set C is m-complete for a class S if $C \in S$ and all sets in S are m-reducible to C. One-reducibility and one-completeness can be defined by requiring f to be one–one. Two sets A and B are p-isomorphic if the function f can be taken one-to-one, onto, and polynomially invertible. In this paper it is shown that all the m-complete sets are one–one complete for ${\operatorname{DTIME}}(2^{\mathcal{O}(n)} )$, ${\operatorname{NTIME}}(2^{\mathcal{O}(n)} )$, and the class of recursively enumerable sets. Further, all the sets complete for ${\operatorname{NTIME}}(2^{\mathcal{O}(n)} )$ under 1–L (or two-way DFA) reductions are p-isomorphic. All the m-complete sets for ${\operatorname{DTIME}}(2^{\mathcal{O}(n)} )$ are p-isomorphic if and only if all the m-complete sets for DTIME($2^{{\text{poly}}} $) are p-isomorphic.

The existence of minimal degrees is investigated for several polynomial reducibilities. It is shown that no set has minimal degree with respect to polynomial many-one or Turing reducibility. This extends a result of Ladner in which only recursive sets are considered. A polynomial reducibility ≤ h T is defined. This reducibility is a strengthening of polynomial Turing reducibility, and its properties relate to the P = ? NP question. For this new reducibility, a set of minimal degree is constructed under the assumption that P = NP. However, the set constructed is nonrecursive, and it is shown that no recursive set is of minimal ≤ h T degree.

We present a relatively simple proof of a result from Homer (1986) showing that if nonrecursive sets cannot be minimal for honest polynomial-time Turing reducibility (⩽ h T -minimal), then P ≠ NP . As a corollary to our proof, we strengthen Homer's result by showing, without assuming that P ≠ NP , that there are ⩽ h T -minimal sets for all tally sets. We also consider the converse of Homer's result, providing some evidence that the nonexistence of ⩽ h T -minimal sets may folow from P ≠ NP in an interesting way. Finally, we consider structural and/or computability properties of sets that cannot be ⩽ h T -minimal.

Two structurally defined types of NP-sets are studied. k -Simple sets are defined and shown to exist in NP. Other properties of these sets are investigated. k -Creative sets, as previously defined by Joseph and Young (1985), are next considered. A new condition is given which implies that a set is k -creative. Several previously considered NP-complete sets are proved to be k -creative.

The existence of minimal degrees is investigated for several polynomial reducibilities. It is shown that no set has minimal degree with respect to polynomial many-one or Turing reducibility. This extends a result of Ladner [L] whew reciirsive sets are considered. An "honest" polynomial reducibility, ⩽is defined which is a strengthening of polynomial Turing reducibility. We prove that no recursive set, (or igeeand P-immune set) has minimalssets (or even all 3 sets) would imply P 2 .y/l. Finally, a partial converse of this result is obtained, proving that if a certain class of one-way functions exists then no set has minimal (h/t)-degree.

In his thesis [2] Sy Friedman showed that for any inadmissible ordinal β there is an easily definable β-r.e. degree, 01/2, with β-degree strictly between 0 and 0′. In this paper we define, for some weakly admissible β, a β-r.e. degree 03/4 intermediate between 01/2 and 0′. This definition is given using the machinery developed by Maass [6], [7] to study the β-r.e. degrees. A weak jump for β-recursion theory, the ½-jump, was first defined by Friedman [4] and has been studied by Sacks and Homer [5]. The degree 03/4 is of interest because of the way it interacts with the half-jump. In particular 03/4 forms the boundary between the half-jump of “hyperregular” and “nonhyperregular” β-r.e. degrees less than 01/2. One consequence of these results is that there are weakly inadmissible β for which either the jump theorem or the density theorem fails. Much of this paper is based on earlier work in this area by Sy Friedman and Wolfgang Maass. I would like to thank Gerald Sacks for many helpful conversations and comments concerning this work.