Comparative complexity of the representation of languages by probabilistic automata

We analyze the effect of the degree of isolation of a cut point on the number of states P(U, ) of a probabilistic automaton representing the language U. We give an example of a language Uⁿ consisting of words of length n such that there exist numbers < for which P(Uⁿ, )/P(Uⁿ, )0 as n.Translated from Kibernetika, No. 3, pp. 21–25, May–June, 1989.     

Space Efficient Hash Tables with Worst Case Constant Access Time

We generalize Cuckoo Hashing to d-ary Cuckoo Hashing and show how this yields a simple hash table data structure that stores n elements in (1 + )n memory cells, for any constant > 0. Assuming uniform hashing, accessing or deleting table entries takes at most d=O (ln (1/)) probes and the expected amortized insertion time is constant. This is the first dictionary that has worst case constant access time and expected constant update time, works with (1 + )n space, and supports satellite information. Experiments indicate that d = 4 probes suffice for 0.03. We also describe variants of the data structure that allow the use of hash functions that can be evaluated in constant time.     

On the Epsilon-entropy of One Class of Ellipsoids in a Hamming Space

The asymptotic behavior of the -entropy of ellipsoids in an n-dimensional Hamming space whose coefficients take only two different values is investigated as n . Explicit expressions for the main terms of the asymptotic expansion of -entropy of such ellipsoids are obtained under various relations between and parameters that define these ellipsoids.     

ε-Entropy and Fractal Dimension of a State for a Gaussian Measure

Kolmogorov introduced the concept of -entropy to analyze information in classical continuous systems. The fractal dimension of a geometric set was introduced by Mandelbrot as a new criterion to analyze the geometric complexity of the set. The -entropy and the fractal dimension of a state in a general quantum system were introduced by one of the present authors (MO) in order to characterize chaotic properties of general states.In this paper, we show that -entropy of a state includes Kolmogorov's -entropy, and that the fractal dimension of a state describes fractal structure of Gaussian measures.     

On computing Boolean connectives of characteristic functions

This paper is a study of the existence of polynomial time Boolean connective functions for languages. A languageL has an AND function if there is a polynomial timef such thatf(x,y) L x L andy L. L has an OR function if there is a polynomial timeg such thatg(x,y) xL oryL. While all NP complete sets have these functions, Graph Isomorphism, which is probably not complete, is also shown to have both AND and OR functions. The results in this paper characterize the complete sets for the classes D^p and p^SAT[O(logn)] in terms of AND and OR and relate these functions to the structure of the Boolean hierarchy and the query hierarchies. Also, this paper shows that the complete sets for the levels of the Boolean hierarchy above the second level cannot have AND or OR unless the polynomial hierarchy collapses. Finally, most of the structural properties of the Boolean hierarchy and query hierarchies are shown to depend only on the existence of AND and OR functions for the NP complete sets.The first author was supported in part by NSF Research Grants DCR-8520597 and CCR-88-23053, and by an IBM Graduate Fellowship.     

On uniform convergence rates for Eulerian and Lagrangian finite element approximations of convection-dominated diffusion problems

Abstract Standard error estimates in the literature for finite element approximations of nonstationary convection-diffusion problems depend either reciprocally on the diffusion parameter or on higher order norms of the solution. Therefore, the estimates generally become worthless in the convection-dominated case with 0 < 1. In this work we develop a rigorous -uniform convergence theory for finite element discretizations of convection-dominated diffusion problems in Eulerian and Lagrangian coordinates. Here, the constants that arise in the error estimates depend on norms of the data and not of the solution and remain bounded in the hyperbolic limit 0. In particular in the Lagrangian case this requires modifications to standard finite element error analyses. In the Eulerian formulation -uniform convergence of order one half is proven whereas in the Lagrangian framework -uniform convergence of optimal order is established. The estimates are based on -uniform a priori estimates for the solution of the continuous problems which are derived first.     

Automated Proof Construction in Type Theory Using Resolution

We provide techniques to integrate resolution logic with equality in type theory. The results may be rendered as follows. A clausification procedure in type theory, equipped with a correctness proof, all encoded using higher-order primitive recursion. A novel representation of clauses in minimal logic such that the -representation of resolution steps is linear in the size of the premisses. A translation of resolution proofs into lambda terms, yielding a verification procedure for those proofs. Availability of the power of resolution theorem provers in interactive proof construction systems based on type theory.     

A Full Bayesian Approach to Curve and Surface Reconstruction

When interpolating incomplete data, one can choose a parametric model, or opt for a more general approach and use a non-parametric model which allows a very large class of interpolants. A popular non-parametric model for interpolating various types of data is based on regularization, which looks for an interpolant that is both close to the data and also smooth in some sense. Formally, this interpolant is obtained by minimizing an error functional which is the weighted sum of a fidelity term and a smoothness term.The classical approach to regularization is: select optimal weights (also called hyperparameters) that should be assigned to these two terms, and minimize the resulting error functional.However, using only the optimal weights does not guarantee that the chosen function will be optimal in some sense, such as the maximum likelihood criterion, or the minimal square error criterion. For that, we have to consider all possible weights.The approach suggested here is to use the full probability distribution on the space of admissible functions, as opposed to the probability induced by using a single combination of weights. The reason is as follows: the weight actually determines the probability space in which we are working. For a given weight , the probability of a function f is proportional to exp(– f² _uu du) (for the case of a function with one variable). For each different , there is a different solution to the restoration problem; denote it by f. Now, if we had known , it would not be necessary to use all the weights; however, all we are given are some noisy measurements of f, and we do not know the correct . Therefore, the mathematically correct solution is to calculate, for every , the probability that f was sampled from a space whose probability is determined by , and average the different f's weighted by these probabilities. The same argument holds for the noise variance, which is also unknown.Three basic problems are addressed is this work: Computing the MAP estimate, that is, the function f maximizing Pr(f/D) when the data D is given. This problem is reduced to a one-dimensional optimization problem. Computing the MSE estimate. This function is defined at each point x as f(x)Pr(f/D) f. This problem is reduced to computing a one-dimensional integral.In the general setting, the MAP estimate is not equal to the MSE estimate. Computing the pointwise uncertainty associated with the MSE solution. This problem is reduced to computing three one-dimensional integrals.     

Approximation Schemes for Degree-Restricted MST and Red–Blue Separation Problems

We develop a quasi-polynomial time approximation scheme for the Euclidean version of the Degree-Restricted MST Problem by adapting techniques used previously by Arora for approximating TSP. Given n points in the plane, d = 3 or 4, and > 0, the scheme finds an approximation with cost within 1 + of the lowest cost spanning tree with the property that all nodes have degree at most d. We also develop a polynomial time approximation scheme for the Euclidean version of the Red–Blue Separation Problem, again extending Aroras techniques. Given > 0, the scheme finds an approximation with cost within 1+ of the cost of the optimum separating polygon of the input nodes, in nearly linear time.     

Scheduling Malleable Parallel Tasks: An Asymptotic Fully Polynomial Time Approximation Scheme

A malleable parallel task is one whose execution time is a function of the number of (identical) processors allotted to it. We study the problem of scheduling a set of n independent malleable tasks on an arbitrary number m of parallel processors and propose an asymptotic fully polynomial time approximation scheme. For any fixed > 0, the algorithm computes a non-preemptive schedule of length at most (1+) times the optimum (plus an additive term) and has running time polynomial in n,m and 1 /.     

Improving known solutions is hard

In this paper, we study the complexity of computing better solutions to optimization problems given other solutions. We use a model of computation suitable for this purpose, the counterexample computation model. We first prove that, if PH _P ³ , polynomial time transducers cannot compute optimal solutions for many problems, even givenn ^1– non-trivial solutions, for any >0. These results are then used to establish sharp lower bounds for several problems in the counterexample model. We extend the model by defining probabilistic counterexample computations and show that our results hold even in the presence of randomness.     

Decomposition in Terms of Variables for Some Optimization Problems

Decomposition of block convex-programming problems with coupling variables is considered in the paper. Functions of the blocks are defined on bounded sets. Rules for calculating -subgradients of objective functions of subproblems with connected variables are formulated. Initial problem normalization is described.     

A New Implementation of Automath

This paper presents aut, a modern Automath checker. It is a straightforward re-implementation of the Zandleven Automath checker from the seventies. It was implemented about five years ago, in the programming language C. It accepts both the AUT-68 and AUT-QE dialects of Automath. This program was written to restore a damaged version of Jutting's translation of Landau's Grundlagen. Some notable features: It is fast. On a 1 GHz machine it will check the full Jutting formalization (736 K of nonwhitespace Automath source) in 0.6 seconds. Its implementation of -terms does not use named variables or de Bruijn indices (the two common approaches) but instead uses a graph representation. In this representation variables are represented by pointers to a binder. The program can compile an Automath text into one big Automath single line-style -term. It outputs such a term using de Bruijn indices. (These -terms cannot be checked by modern systems like Coq or Agda, because the -typed -calculi of de Bruijn are different from the -typed -calculi of modern type theory.)The source of aut is freely available on the Web at the address .     

Implementation of Generalized Finite Element Methods for Homogenization Problems

The implementation of a generalized Finite Element Method (FEM) for problems with coefficients or geometry that oscillate locally at a small length scale 1 is described. Two-scale FE-spaces are combined conformingly with standard FE. Numerical experiments show that the complexity of the algorithm is independent of the micro length scale .     

A regularity test for dual bordered OS systems

Summary A dual bordered OS system is a triple (, P, S) where is a finite alphabet, S a finite subset of ^*, the set of axioms, and P a finite set of rules of the form aa × a, where a and x ^*. Using well-quasi-order theory, we show that the regularity problem for such systems is decidable. Whether such a system generates a regular language essentially only depends on the set of rules but not on the axioms.     

Software Quality Evaluation Based on Expert Judgement

A method using expert judgement for the evaluation of software quality is presented. The underlying principle of the approach is the encoding of experts' tacit knowledge into probabilistic measures associated with the achievement level of software quality attributes. An aggregated quality measure is obtained based on preference statements related to the quality attributes. The technical objectives of the paper are to develop of a generic and operationally feasible measurement technique to transform the tacit knowledge of a software expert to a probability distribution depicting his/her uncertainty of the level of achievement related to a quality attribute; to develop rules for the construction of a consensus probability measure based on expert-specific probability measures; to derive a framework for specifying software quality strategy and for evaluating the acceptance of a software produced in a software development process;The above technical developments are used to support group decision-making regarding the launch or implementation decision of a software version; the allocation of resources during the software development process.     

Classical and Quantum Complexity of the Sturm–Liouville Eigenvalue Problem

We study the approximation of the smallest eigenvalue of a Sturm–Liouville problem in the classical and quantum settings. We consider a univariate Sturm–Liouville eigenvalue problem with a nonnegative function q from the class C² ([0,1]) and study the minimal number n() of function evaluations or queries that are necessary to compute an -approximation of the smallest eigenvalue. We prove that n()=(^–1/2) in the (deterministic) worst case setting, and n()=(^–2/5) in the randomized setting. The quantum setting offers a polynomial speedup with bit queries and an exponential speedup with power queries. Bit queries are similar to the oracle calls used in Grovers algorithm appropriately extended to real valued functions. Power queries are used for a number of problems including phase estimation. They are obtained by considering the propagator of the discretized system at a number of different time moments. They allow us to use powers of the unitary matrix exp((1/2) iM), where M is an n× n matrix obtained from the standard discretization of the Sturm–Liouville differential operator. The quantum implementation of power queries by a number of elementary quantum gates that is polylog in n is an open issue. In particular, we show how to compute an -approximation with probability (3/4) using n()=(^–1/3) bit queries. For power queries, we use the phase estimation algorithm as a basic tool and present the algorithm that solves the problem using n()=(log ^–1) power queries, log ^2–1 quantum operations, and (3/2) log ^–1 quantum bits. We also prove that the minimal number of qubits needed for this problem (regardless of the kind of queries used) is at least roughly (1/2) log ^–1. The lower bound on the number of quantum queries is proven in Bessen (in preparation). We derive a formula that relates the Sturm–Liouville eigenvalue problem to a weighted integration problem. Many computational problems may be recast as this weighted integration problem, which allows us to solve them with a polylog number of power queries. Examples include Grovers search, the approximation of the Boolean mean, NP-complete problems, and many multivariate integration problems. In this paper we only provide the relationship formula. The implications are covered in a forthcoming paper (in preparation).PACS: 03.67.Lx, 02.60.-x.     

On deterministic approximation of DNF

We develop several quasi-polynomial-time deterministic algorithms for approximating the fraction of truth assignments that satisfy a disjunctive normal form formula. The most efficient algorithm computes for a given DNF formulaF onn variables withm clauses and > 0 an estimateY such that ¦Pr[F] –Y¦ in time which is , for any constant. Although the algorithms themselves are deterministic, their analysis is probabilistic and uses the notion of limited independence between random variables.Research supported in part by National Science Foundation Operating Grant CCR-9016468, National Science Foundation Operating Grant CCR-9304722, United States-Israel Binational Science Foundation Grant No. 89-00312, United States-Israel Binational Science Foundation Grant No. 92-00226, and ESPRIT Basic Research Grant EC-US 030.Research partially done while visiting the International Computer Science Institute and while at Carnegie Mellon University.     

Decision procedures for elementary sublanguages of set theory: XIII. Model graphs,reflection and decidability

Positive solutions to the decision problem for a class of quantified formulae of the first order set theoretic language based on , , =, involving particular occurrences of restricted universal quantifiers and for the unquantified formulae of , , =, {...}, , where {...} is the tuple operator and is a general choice operator, are obtained. To that end a method is developed which also provides strong reflection principles over the hereditarily finite sets. As far as finite satisfiability is concerned such results apply also to the unquantified extention of , , =, {...}, , obtained by adding the operators of binary union, intersection and difference and the relation of inclusion, provided no nested term involving is allowed.