Quantum complexity of the approximation for the classes B(Wp ([0, 1])) and B(Hp ([0, 1]))

We study the approximation of functions from anisotropic Sobolev classes B(W^r_p([0,1]d)) and Hölder-Nikolskii classes B(H^r_p([0,1]d)) in the L_q([0,1]d) norm with q ≤ p in the quantum model of computation. We determine the quantum query complexity of this problem up to logarithmic factors. It shows that the quantum algorithms are significantly better than the classical deterministic or randomized algorithms.     

Succinct data structures for flexible text retrieval systems

We propose succinct data structures for text retrieval systems supporting document listing queries and ranking queries based on the tf*idf (term frequency times inverse document frequency) scores of documents. Traditional data structures for these problems support queries only for some predetermined keywords. Recently Muthukrishnan proposed a data structure for document listing queries for arbitrary patterns at the cost of data structure size. For computing the tf*idf scores there has been no efficient data structures for arbitrary patterns.Our new data structures support these queries using small space. The space is only 2/ times the size of compressed documents plus 10n bits for a document collection of length n, for any 0<1. This is much smaller than the previous O(nlogn) bit data structures. Query time is O(m+qlogn) for listing and computing tf*idf scores for all q documents containing a given pattern of length m. Our data structures are flexible in a sense that they support queries for arbitrary patterns.     

Complexity of Weighted Approximation over

We study approximation of multivariate functions defined over ^d. We assume that all rth order partial derivatives of the functions considered are continuous and uniformly bounded. Approximation algorithms (f) only use the values of f or its partial derivatives up to order r. We want to recover the function f with small error measured in a weighted L_q norm with a weight function ρ. We study the worst case (information) complexity which is equal to the minimal number of function and derivative evaluations needed to obtain error . We provide necessary and sufficient conditions in terms of the weight ρ and the parameters q and r for the weighted approximation problem to have finite complexity. We also provide conditions guaranteeing that the complexity is of the same order as the complexity of the classical approximation problem over a finite domain. Since the complexity of the weighted integration problem is equivalent to the complexity of the weighted approximation problem with q=1, the results of this paper also hold for weighted integration. This paper is a continuation of [7], where weighted approximation over was studied.     

Query complexity,or why is it difficult to separateNP A ∩coNP A fromP A by random oraclesA?

By thequery-time complexity of a relativized algorithm we mean the total length of oracle queries made; thequery-space complexity is the maximum length of the queries made. With respect to these cost measures one can define polynomially time- or space-bounded deterministic, nondeterministic, alternating, etc. Turing machines and the corresponding complexity classes. It turns out that all known relativized separation results operate essentially with this cost measure. Therefore, if certain classes do not separate in the query complexity model, this can be taken as an indication that their relativized separation in the classical cost model will require entirely new principles.A notable unresolved question in relativized complexity theory is the separation of NP^A co NP^A fromP ^A under random oraclesA. We conjecture that the analogues of these classes actually coincide in the query complexity model, thus indicating an answer to the question in the title. As a first step in the direction of establishing the conjecture, we prove the following result, where polynomial bounds refer to query complexity.If two polynomially query-time-bounded nondeterministic oracle Turing machines accept precisely complementary (oracle dependent) languages L^A and {0, 1}^*L^A under every oracle A then there exists a deterministic polynomially query-time-bounded oracle Turing machine that accept L^A. The proof involves a sort of greedy strategy to selecting deterministically, from the large set of prospective queries of the two nondeterministic machines, a small subset that suffices to perform an accepting computation in one of the nondeterministic machines. We describe additional algorithmic strategies that may resolve the same problem when the condition holds for a (1–) fraction of the oracles A, a step that would bring us to a non-uniform version of the conjecture. Thereby we reduce the question to a combinatorial problem on certain pairs of sets of partial functions on finite sets.     

Estimating the ground state energy of the Schrödinger equation for convex potentials

In 2011, the fundamental gap conjecture for Schrödinger operators was proven. This can be used to estimate the ground state energy of the time-independent Schrödinger equation with a convex potential and relative error ε$\epsilon$. Classical deterministic algorithms solving this problem have cost exponential in the number of its degrees of freedom d$d$. We show a quantum algorithm, that is based on a perturbation method, for estimating the ground state energy with relative error ε$\epsilon$. The cost of the algorithm is polynomial in d$d$ and ε⁻¹${\epsilon }^{-1}$, while the number of qubits is polynomial in d$d$ and logε⁻¹$log{\epsilon }^{-1}$. In addition, we present an algorithm for preparing a quantum state that overlaps within 1−δ,δ∈(0,1)$1-\delta ,\delta \in (0,1)$, with the ground state eigenvector of the discretized Hamiltonian. This algorithm also approximates the ground state with relative error ε$\epsilon$. The cost of the algorithm is polynomial in d$d$, ε⁻¹${\epsilon }^{-1}$ and δ⁻¹${\delta }^{-1}$, while the number of qubits is polynomial in d$d$, logε⁻¹$log{\epsilon }^{-1}$ and logδ⁻¹$log{\delta }^{-1}$.     

On Principal Eigenvalues for Indefinite Problems in Euclidean Space

For the eigenvalue problem—λΔu = q(x)u in IR^d, with the weight function q changing sign, conditions are discussed for existence of eigenvalues with positive decaying eigenfunctions.     

Optimal query error of quantum approximation on some Sobolev classes

We study the approximation of the imbedding of functions from anisotropic and general-ized Sobolev classes into Lq([0,1]d) space in the quantum model of computation. Based on the quantum algorithms for approximation of finite imbedding from LpN to LNq , we develop quantum algorithms for approximating the imbedding from anisotropic Sobolev classes B(Wpr ([0,1]d)) to Lq([0,1]d) space for all 1 q,p ∞ and prove their optimality. Our results show that for p < q the quantum model of computation can bring a speedup roughly up to a squaring of the rate in the classical deterministic and randomized settings.     

Complexity of fixed points, I

We study the complexity (minimal cost) of computing an s-approximation to a fixed point of a contractive function with the contractive factor q < 1. This is done for the relative error criterion in Part I and for the absolute error criterion in Part II, which is in progress. The complexity depends strongly on the dimension of the domain of functions. For the one-dimensional case we develop an optimal fixed point envelope (FPE) algorithm. The cost of the FPE algorithm with use of the relative error criterion is roughly , where c is the cost of one function evaluation. Thus, for fixed ε and q close to 1 the cost of the FPE algorithm is much smaller than the cost of the simple iteration algorithm, since the latter is roughly For the contractive functions of d variables, with d ≥ log(1/ε)/log(l/q) we show that it is impossible to essentially improve the efficiency of the simple iteration.     

Constructing permutation arrays from groups

Let M(n, d) be the maximum size of a permutation array on n symbols with pairwise Hamming distance at least d. We use various combinatorial, algebraic, and computational methods to improve lower bounds for M(n, d). We compute the Hamming distances of affine semilinear groups and projective semilinear groups, and unions of cosets of AGL(1, q) and PGL(2, q) with Frobenius maps to obtain new, improved lower bounds for M(n, d). We give new randomized algorithms. We give better lower bounds for M(n, d) also using new theorems concerning the contraction operation. For example, we prove a quadratic lower bound for \(M(n,n-2)\) for all \(n\equiv 2 \pmod 3\) such that \(n+1\) is a prime power.     

Relaxation Time of Quantized Toral Maps

We introduce the notion of relaxation time for noisy quantum maps on the 2d-dimensional torus – generalization of previously studied dissipation time. We show that the relaxation time is sensitive to the chaotic behavior of the corresponding classical system if one simultaneously considers the semiclassical limit together with the limit of small noise strength (ε → 0). Focusing on quantized smooth Anosov maps, we exhibit a semiclassical régime (where E > 1) in which classical and quantum relaxation times share the same asymptotics: in this régime, a quantized Anosov map relaxes to equilibrium fast, as the classical map does. As an intermediate result, we obtain rigorous estimates of the quantum-classical correspondence for noisy maps on the torus, up to times logarithmic in On the other hand, we show that in the “quantum régime” quantum and classical relaxation times behave very differently. In the special case of ergodic toral symplectomorphisms (generalized “Arnold’s cat” maps), we obtain the exact asymptotics of the quantum relaxation time and precise the régime of correspondence between quantum and classical relaxations. Communicated by Jens Marklof submitted 4/01/05, accepted 2/02/05     

Quantum complexity of parametric integration

We study parametric integration of functions from the class C^r([0,1]^d₁+d₂) to C([0,1]^d₁) in the quantum model of computation. We analyze the convergence rate of parametric integration in this model and show that it is always faster than the optimal deterministic rate and in some cases faster than the rate of optimal randomized classical algorithms.     

Quantum B-splines

Quantum splines are piecewise polynomials whose quantum derivatives (i.e. certain discrete derivatives or equivalently certain divided differences) agree up to some order at the joins. Just like classical splines, quantum splines admit a canonical basis with compact support: the quantum B-splines. These quantum B-splines are the q-analogues of classical B-splines. Here quantum B-spline bases and quantum B-spline curves are investigated, using a new variant of the blossom: the q (quantum)-blossom. The q-blossom of a degree d polynomial is the unique symmetric, multiaffine function in d variables that reduces to the polynomial along the q-diagonal. By applying the q-blossom, algorithms and identities for quantum B-spline bases and quantum B-spline curves are developed, including quantum variants of the de Boor algorithms for recursive evaluation and quantum differentiation, knot insertion procedures for converting from quantum B-spline to piecewise quantum Bézier form, and a quantum variant of Marsden’s identity.     

Small noise asymptotics for invariant densities for a class of diffusions: A control theoretic view

We consider multi-dimensional nondegenerate diffusions with invariant densities, with the diffusion matrix scaled by a small >0. The o.d.e. limit corresponding to =0 is assumed to have the origin as its unique globally asymptotically stable equilibrium. Using control theoretic methods, we show that in the ↓0 limit, the invariant density has the form ≈exp(−W(x)/²), where the W is characterized as the optimal cost of a deterministic control problem. This generalizes an earlier work of Sheu. Extension to multiple equilibria is also given.     

Finding the exact bound of the maximum degrees of class two graphs embeddable in a surface of characteristic

In this paper, we consider the problem of determining the maximum of the set of maximum degrees of class two graphs that can be embedded in a surface. For each surface Σ, we define Δ(Σ)=max{Δ(G)| G is a class two graph of maximum degree Δ that can be embedded in Σ}. Hence Vizing's Planar Graph Conjecture can be restated as Δ(Σ)=5 if Σ is a plane. We show that Δ(Σ)=7 if (Σ)=−1 and Δ(Σ)=8 if (Σ){−2,−3}.     

Applications of random sampling in computational geometry,II

We use random sampling for several new geometric algorithms. The algorithms are Las Vegas, and their expected bounds are with respect to the random behavior of the algorithms. These algorithms follow from new general results giving sharp bounds for the use of random subsets in geometric algorithms. These bounds show that random subsets can be used optimally for divide-and-conquer, and also give bounds for a simple, general technique for building geometric structures incrementally. One new algorithm reports all the intersecting pairs of a set of line segments in the plane, and requiresO(A+n logn) expected time, whereA is the number of intersecting pairs reported. The algorithm requiresO(n) space in the worst case. Another algorithm computes the convex hull ofn points inE ^d inO(n logn) expected time ford=3, andO(n ^[d/2]) expected time ford>3. The algorithm also gives fast expected times for random input points. Another algorithm computes the diameter of a set ofn points inE ³ inO(n logn) expected time, and on the way computes the intersection ofn unit balls inE ³. We show thatO(n logA) expected time suffices to compute the convex hull ofn points inE ³, whereA is the number of input points on the surface of the hull. Algorithms for halfspace range reporting are also given. In addition, we give asymptotically tight bounds for (k)-sets, which are certain halfspace partitions of point sets, and give a simple proof of Lee's bounds for high-order Voronoi diagrams.     

A randomized scheme for speeding up algorithms for linear and convex programming problems with high constraints-to-variables ratio

We extend Clarkson's randomized algorithm for linear programming to a general scheme for solving convex optimization problems. The scheme can be used to speed up existing algorithms on problems which have many more constraints than variables. In particular, we give a randomized algorithm for solving convex quadratic and linear programs, which uses that scheme together with a variant of Karmarkar's interior point method. For problems withn constraints,d variables, and input lengthL, ifn = (d ²), the expected total number of major Karmarkar's iterations is O(d ²(logn)L), compared to the best known deterministic bound of O( L). We also present several other results which follow from the general scheme.     

Second-Order Optimality and Beyond: Characterization and Evaluation Complexity in Convexly Constrained Nonlinear Optimization

High-order optimality conditions for convexly constrained nonlinear optimization problems are analysed. A corresponding (expensive) measure of criticality for arbitrary order is proposed and extended to define high-order \(\epsilon \)-approximate critical points. This new measure is then used within a conceptual trust-region algorithm to show that if derivatives of the objective function up to order \(q \ge 1\) can be evaluated and are Lipschitz continuous, then this algorithm applied to the convexly constrained problem needs at most \(O(\epsilon ^{-(q+1)})\) evaluations of f and its derivatives to compute an \(\epsilon \)-approximate qth-order critical point. This provides the first evaluation complexity result for critical points of arbitrary order in nonlinear optimization. An example is discussed, showing that the obtained evaluation complexity bounds are essentially sharp.     

A fast and simple randomized parallel algorithm for the maximal independent set problem

A simple parallel randomized algorithm to find a maximal independent set in a graph G = (V, E) on n vertices is presented. Its expected running time on a concurrent-read concurrent-write PRAM with O(|E|d_max) processors is O(log n), where d_max denotes the maximum degree. On an exclusive-read exclusive-write PRAM with O(|E|) processors the algorithm runs in O(log²n). Previously, an O(log⁴n) deterministic algorithm was given by Karp and Wigderson for the EREW-PRAM model. This was recently (independently of our work) improved to O(log²n) by M. Luby. In both cases randomized algorithms depending on pairwise independent choices were turned into deterministic algorithms. We comment on how randomized combinatorial algorithms whose analysis only depends on d-wise rather than fully independent random choices (for some constant d) can be converted into deterministic algorithms. We apply a technique due to A. Joffe (1974) and obtain deterministic construction in fast parallel time of various combinatorial objects whose existence follows from probabilistic arguments.