The query complexity of estimating weighted averages

The query complexity of estimating the mean of some [0, 1] variables is understood. Inspired by some work by Carterette et?al. on evaluating retrieval systems, and by Moffat and Zobel??s new proposal for such evaluation, we examine the query complexity of weighted average calculation. In general, determining an answer within accuracy ${\varepsilon}$ , with high probability, requires ${\Omega(\varepsilon^{-2})}$ queries, as the mean is a special case. There is a matching upper bound for the weighted mean. If the weights are a normalized prefix of a divergent series, the same result holds. However, if the weights follow a geometric sequence, a sample of size ${\Omega(\log (1/\varepsilon))}$ suffices. Our principal contribution is the investigation of power-law sequences of weights. We show that if the ith largest weight is proportional to i ^?p , for p > 1, then the query complexity is in ${\Omega(\varepsilon^{2/(1-2p)})}$ .     

Two algorithms for estimating test complexity levels

We study the problem of estimating the complexity levels of test problems and levels of preparation of the students that arises in learning management systems. To solve the problem, we propose two algorithms for processing test results. The first algorithm is based on the assumption that random answers of the test takers are described by a logistic distribution. To compute test problem complexities and levels of preparation of the students, we use the maximum likelihood method and the quasi-Newton Broyden–Fletcher–Goldfarb–Shanno optimization method, where the likelihood function is constructed in a special way based on Rasch’s model. The second algorithm is heuristic and is based on recurrent recomputation of initial estimates obtained by adding up the positive answers of students separately by columns and rows of the matrix of answers, where columns correspond to answers of all students for a specific test, and rows correspond to answers of a specific student for all tests. We consider an example where we compare the results of applying the proposed algorithms.     

An approach to estimating the complexity of probabilistic procedures for the postoptimality analysis of discrete optimization problems

It is shown that ZPP- and RP-probabilistic polynomial postoptimality analysis procedures for finding an optimal solution of a set cover problem that differs from the original problem in one position of the constraints matrix do not exist if an optimal solution of the original problem is known and if ZPP ?? NP (RP ?? NP). A similar result holds for the knapsack problem.     

The network complexity and the Turing machine complexity of finite functions

Summary Let L(f) be the network complexity of a Boolean function L(f). For any n-ary Boolean function L(f) let . Hereby p ranges over all relative Turing programs and ranges over all oracles such that given the oracle , the restriction of p to inputs of length n is a program for L(f). p is the number of instructions of p. T _p (n) is the time bound and S _p of the program p relative to the oracle on inputs of length n. Our main results are (1) L(f) O(TC(L(f))), (2) TC(f) O(L(f) ^{2 2+}) for every O.The results of this paper have been reported in a main lecture at the 1975 annual meeting of GAMM, April 2–5, Göttingen     

The query complexity of order-finding

We consider the problem where π is an unknown permutation on {0,1,…,2ⁿ−1}, y₀{0,1,…,2ⁿ−1}, and the goal is to determine the minimum r>0 such that π^r(y₀)=1. Information about π is available only via queries that yield π^x(y) from any x{0,1,…,2^m−1} and y{0,1,…,2ⁿ−1} (where m is polynomial in n). The main resource under consideration is the number of these queries. We show that the number of queries necessary to solve the problem in the classical probabilistic bounded-error model is exponential in n. This contrasts sharply with the quantum bounded-error model, where a constant number of queries suffices.     

The complexity of propositional implication

The question whether a set of formulae Γ implies a formula φ is fundamental. The present paper studies the complexity of the above implication problem for propositional formulae that are built from a systematically restricted set of Boolean connectives. We give a complete complexity-theoretic classification for all sets of Boolean functions in the meaning of Post's lattice and show that the implication problem is efficiently solvable only if the connectives are definable using the constants {0,1} and only one of {∧,∨,⊕}. The problem remains coNP-complete in all other cases. We also consider the restriction of Γ to singletons which makes the problem strictly easier in some cases.     

The complexity of logical theories

In this paper we introduce a method of encoding the computation of an alternating TM into a logical theory. The efficiency of the embedding we give together with the decision procedures, using Ehrenfencht games, which have been developed over the past few years, yield precise lower bounds for many decidable theories. In this paper we apply our technique explicitly to the theory of reals with addition; however, it should be clear that the techniques apply directly to other theories as well.We also outline the proof of a general theorem, motivated by a comment of A.R. Meyer and discovered independently by A.R. Meyer and L. Stockmeyer, which allows us to obtain a recent result of Bruss and Meyer directly from our precise characterization of R.A.     

The complexity of stochastic games

We consider the complexity of stochastic games—simple games of chance played by two players. We show that the problem of deciding which player has the greatest chance of winning the game is in the class NP co-NP.     

The complexity of tensor calculus

Tensor calculus over semirings is shown relevant to complexity theory in unexpected ways. First, evaluating well-formed tensor formulas with explicit tensor entries is shown complete for $\bigoplusP$, for NP, and for #P as the semiring varies. Indeed the permanent of a matrix is shown expressible as the value of a tensor formula in much the same way that Berkowitzs theorem expresses its determinant. Second, restricted tensor formulas are shown to capture the classes LOGCFL and NL, their parity counterparts $\bigoplusLOGCFL$ and $\bigoplusL$, and several other counting classes. Finally, the known inclusions $\NP/\poly \subseteq \bigoplusP/\poly$, $\LOGCFL/\poly \subseteq \bigoplusLOGCFL/\poly$, and $\NL/\poly \subseteq \bigoplusL/\poly$, which have scattered proofs in the literature (Valiant & Vazirani 1986; Gál & Wigderson 1996), are shown to follow from the new characterizations in a single blow. As an intermediate tool, we define and make use of the natural notion of an algebraic Turing machine over a semiring $ \mathcal{S}$.     

The combinational complexity of equivalence

Consider the Boolean functions and$\text{(n)=}\text{?}\text{i=1}\text{n}\text{x}{}_{\mathrm{i}}\text{nor}\text{(n)=}\text{?}\text{i=1}\text{n}\text{¬ x}{}_{\mathrm{i}}$ and the equivalence Eq(n)=and (n)∨nor(n). Let L (F) be the smallest number of arbitrary binary Boolean operations that are used in any Boolean computation for F. We prove L(Eq(n))=2n ?3, L (and(n), nor(n))=2n?2. There exist many structurally different optimal computations for Eq (n).