Analytical properties of resource-bounded real functionals

Computable analysis is an extension of classical discrete computability by enhancing the normal Turing machine model. It investigates mathematical analysis from the computability perspective. Though it is well developed on the computability level, it is still under developed on the complexity perspective, that is, when bounding the available computational resources. Recently Kawamura and Cook developed a framework to define the computational complexity of operators arising in analysis. Our goal is to understand the effects of complexity restrictions on the analytical properties of the operator. We focus on the case of norms over C[0, 1] and introduce the notion of dependence of a norm on a point and relate it to the query complexity of the norm. We show that the dependence of almost every point is of the order of the query complexity of the norm. A norm with small complexity depends on a few points but, as compensation, highly depends on them. We briefly show how to obtain similar results for non-deterministic time complexity. We characterize the functionals that are computable using one oracle call only and discuss the uniformity of that characterization.     

Box-Trees and R-Trees with Near-Optimal Query Time

Abstract. A box-tree is a bounding-volume hierarchy that uses axis-aligned boxes as bounding volumes. The query complexity of a box-tree with respect to a given type of query is the maximum number of nodes visited when answering such a query. We describe several new algorithms for constructing box-trees with small worst-case query complexity with respect to queries with axis-parallel boxes and with points. We also prove lower bounds on the worst-case query complexity for box-trees, which show that our results are optimal or close to optimal. Finally, we present algorithms to convert box-trees to R-trees, resulting in R-trees with (almost) optimal query complexity.     

On R-trees with low query complexity

The R-tree is a well-known bounding-volume hierarchy that is suitable for storing geometric data on secondary memory. Unfortunately, no good analysis of its query time exists. We describe a new algorithm to construct an R-tree for a set of planar objects that has provably good query complexity for point location queries and range queries with ranges of small width. For certain important special cases, our bounds are optimal. We also show how to update the structure dynamically, and we generalize our results to higher-dimensional spaces.     

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.     

On the analytic complexity of discriminants

The paper deals with the notion of analytic complexity introduced by V.K. Beloshapka. We give an algorithm which allows one to check whether a bivariate analytic function belongs to the second class of analytic complexity. We also provide estimates for the analytic complexity of classical discriminants and introduce the notion of analytic complexity of a knot.     

On a problem in quantum summation

We consider the computation of the mean of sequences in the quantum model of computation. We determine the query complexity in the case of sequences which satisfy a p-summability condition for 1⩽p<2. This settles a problem left open in Heinrich (J. Complexity 18 (2002) 1).     

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.     

A Theory of Complexity for Continuous Time Systems

We present a model of computation with ordinary differential equations (ODEs) which converge to attractors that are interpreted as the output of a computation. We introduce a measure of complexity for exponentially convergent ODEs, enabling an algorithmic analysis of continuous time flows and their comparison with discrete algorithms. We define polynomial and logarithmic continuous time complexity classes and show that an ODE which solves the maximum network flow problem has polynomial time complexity. We also analyze a simple flow that solves the Maximum problem in logarithmic time. We conjecture that a subclass of the continuous P is equivalent to the classical P.     

Local decoding and testing of polynomials over grids

We study the local decodability and (tolerant) local testability of low‐degree n‐variate polynomials over arbitrary fields, evaluated over the domain {0,1}ⁿ. We show that for every field there is a tolerant local test whose query complexity depends only on the degree. In contrast we show that decodability is possible over fields of positive characteristic, but not over the reals.     

Effective Search Problems

The task of computing a function F with the help of an oracle X can be viewed as a search problem where the cost measure is the number of queries to X. We ask for the minimal number that can be achieved by a suitable choice of X and call this quantity the query complexity of F. This concept is suggested by earlier work of Beigel, Gasarch, Gill, and Owings on “Bounded query classes”. We introduce a fault tolerant version and relate it with Ulam's game. For many natural classes of functions F we obtain tight upper and lower bounds on the query complexity of F. Previous results like the Nonspeedup Theorem and the Cardinality Theorem appear in a wider perspective. Mathematics Subject Classification: 03D20, 68Q15, 68R05.     

On the linear complexity profile of nonlinear congruential pseudorandom number generators with Rédei functions

Linear complexity and linear complexity profile are important characteristics of a sequence for applications in cryptography and quasi-Monte Carlo methods. The nonlinear congruential method is an attractive alternative to the classical linear congruential method for pseudorandom number generation. We prove lower bounds on the linear complexity profile of nonlinear congruential pseudorandom number generators with Rédei functions which are much stronger than bounds known for general nonlinear congruential pseudorandom number generators.     

Testing monotonicity over graph products

We consider the problem of monotonicity testing over graph products. Monotonicity testing is one of the central problems studied in the field of property testing. We present a testing approach that enables us to use known monotonicity testers for given graphs G₁, G₂, to test monotonicity over their product G₁ × G₂. Such an approach of reducing monotonicity testing over a graph product to monotonicity testing over the original graphs, has been previously used in the special case of monotonicity testing over [n]^d for a limited type of testers; in this article, we show that this approach can be applied to allow modular design of testers in many interesting cases: this approach works whenever the functions are boolean, and also in certain cases for functions with a general range. We demonstrate the usefulness of our results by showing how a careful use of this approach improves the query complexity of known testers. Specifically, based on our results, we provide a new analysis for the known tester for [n]^d which significantly improves its query complexity analysis in the low‐dimensional case. For example, when d = O(1), we reduce the best known query complexity from O(log ²n/ε) to O(log n/ε). © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Simple analysis of graph tests for linearity and PCP

We give a simple analysis of the PCP with low amortized query complexity of Samorodnitsky and Trevisan [16]. The analysis also applies to the linearity testing over finite fields, giving a better estimate of the acceptance probability in terms of the distance of the tested function to the closest linear function. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 22: 139–160, 2003     

Ideals with bases of unbounded Borel complexity

We present several naturally defined σ‐ideals which have Borel bases but, unlike for the classical examples, these ideals are not of bounded Borel complexity. We investigate set‐theoretic properties of such σ‐ideals.     

离线k-服务器问题算法的改进

阐述了在k-服务器猜想的证明中改进经典的离线k-服务器问题算法的必要性,从而对经典算法进行了改进,设计了一种新算法,其复杂度由原来的O(m(nk)2)下降为O(mk2).     

Self-customized BSP trees for collision detection

The ability to perform efficient collision detection is essential in virtual reality environments and their applications, such as walkthroughs. In this paper we re-explore a classical structure used for collision detection – the binary space partitioning tree. Unlike the common approach, which attributes equal likelihood to each possible query, we assume events that happened in the past are more likely to happen again in the future. This leads us to the definition of self-customized data structures. We report encouraging results obtained while experimenting with this concept in the context of self-customized BSP trees.     

The power of various real-valued quantum queries

The computation of combinatorial and numerical problems on quantum computers is often much faster than on a classical computer in numbers of queries. A query is a procedure by which the quantum computer gains information about the specific problem. Different query definitions were given and our aim is to review them and to show that these definitions are not equivalent. To achieve this result we will study the simulation and approximation of one query type by another. While approximation is “easy” in one direction, we will show that it is “hard” in the other direction by a lower bound for the numbers of queries needed in the simulation. The main tool in this lower bound proof is a relationship between quantum algorithms and trigonometric polynomials that we will establish.     

基于一类新方向的宽邻域路径跟踪内点算法

基于一类带有参数theta的新方向, 提出了求解单调线性互补问题的宽邻 域路径跟踪内点算法, 且当theta=1时即为经典牛顿方向. 当取theta为与问题规模 n无关的常数时, 算法具有O(nL)迭代复杂性, 其中L是输入数据的长度, 这与经典宽邻 域算法的复杂性相同; 当取theta=\sqrt{n/\beta\tau}时, 算法具有O(\sqrt{n}L)迭代复杂性, 这里的\beta, \tau是邻域参数, 这与窄邻域算法的复杂性相同. 这是首次研究包括经典宽邻域路径跟踪算法的一类内点算法, 给出了统一的算法框架和收敛性分析方法.     

Semialgebraic complexity of functions

In this paper we study the rate of the best approximation of a given function by semialgebraic functions of a prescribed “combinatorial complexity”. We call this rate a “Semialgebraic Complexity” of the approximated function. By the classical Approximation Theory, the rate of a polynomial approximation is determined by the regularity of the approximated function (the number of its continuous derivatives, the domain of analyticity, etc.). In contrast, semialgebraic complexity (being always bounded from above in terms of regularity) may be small for functions not regular in the usual sense. We give various natural examples of functions of low semialgebraic complexity, including maxima of smooth families, compositions, series of a special form, etc. We show that certain important characteristics of the functions, in particular, the geometry of their critical values (Morse–Sard Theorem) are determined by their semialgebraic complexity, and not by their regularity.