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 prove exponentially small upper bounds on the correlation between parity and quadratic polynomials mod 3. One corollary of this is that in order to compute parity, circuits consisting of a threshold gate at the top, mod 3 gates in the middle, and AND gates of fan-in two at the inputs must be of size 2/sup /spl Omega/(n)/. This is the first result of this type for general mod subcircuits with ANDs of fan-in greater than 1. This yields an exponential improvement over a recent result of Alon and Beigel (2001). The proof uses a novel inductive estimate of the relevant exponential sums introduced by Cai et al. (1996). The exponential sum bounds are tight.

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.

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.