Some Results on Effective Randomness

We investigate the characterizations of effective randomness in terms of Martin-Lof tests and martingales. First, we address a question of Ambos-Spies and Kucera, who asked for a characterization of computable randomness in terms of tests. We argue that computable randomness can be characterized in terms of Martin-Lof tests and effective probability distributions on Cantor space. Second, we show that the class of Martin-Lof random sequences coincides with the class of sequences that are random with respect to computable martingale processes; the latter randomness notion was introduced by Hitchcock and Lutz. Third, we analyze the sequence of measures of the components of a universal Martin-Lof test. Kucera and Slaman showed that any component of a universal Martin-Lof test defines a class of Martin-Lof random measure. Further, since the sets in a Martin-Lof test are uniformly computably enumerable, so is the corresponding sequence of measures. We prove an exact converse and hence a characterization. For any uniformly computably enumerable sequence r₁, r₂,... of reals such that each r_n is Martin-Lof random and less than 2^-n there is a universal Martin-Lof test U₁, U₂,... such that U_n{0,1}^∞ has measure r_n.     

Hardness Hypotheses, Derandomization, and Circuit Complexity

We consider hypotheses about nondeterministic computation that have been studied in different contexts and shown to have interesting consequences:

关于图的分数k-因子存在性的一些结果

设g(x)≤f(x)是定义在V(G)上的两个整数值函数,h(e)∈[0,1]是定义在图G的边集E(G)上的函数。令dGh(x)=移e∈Exh(e),其中Ex={xy:xy∈E(G)}。若对所有的x∈V(G)都有g(x)≤dGh(x)≤f(x)成立,称h是G的一个(g,f)-表示函数。Gh是图G的一个支撑子图使得E(Gh)={e:e∈E(G),h(e)≠0},则称Gh是G的一个分数(g,f)-因子。文章给出,若对V(G)中的任意两个顶点u和v,G-{u,v}有分数k-因子存在。则G有一个分数k-因子不含图G中任意给定的边e∈E(G);当G有分数1-因子F=Gh存在时,对任意e∈F,G-V(e)有分数k-因子存在,则G有分数k-因子。     

Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds

The area of derandomization attempts to provide efficient deterministic simulations of randomized algorithms in various algorithmic settings. Goldreich and Wigderson introduced a notion of “typically-correct” deterministic simulations, which are allowed to err on few inputs. In this paper, we further the study of typically-correct derandomization in two ways.     

关于混合加密方案匿名性质的几个一般性结果

公钥加密方案的匿名性(亦称公钥隐密性)与数据保密性同样都具有重要应用价值.文中首先建立关于公钥加密方案的两个通用的新概念,即相对匿名性和相对保密性.通过这些较弱的安全性概念,证明了关于公钥加密方案匿名性质的两类一般性结果.第一类结果建立了公钥加密方案的保密性与匿名性之间两个对偶式的普遍关系,即相对匿名性(相对保密性)连同保密性(匿名性)蕴涵匿名性(保密性);第二类结果给出两个典型的混合加密构造(即Fujisaki-Okamoto构造和Okamoto-Pointcheval构造(REACT))选择密文匿名的充分条件,这些条件仅包括特定意义上的相对匿名性质和其它一些自然的弱保密性要求.文中不仅用多个具体实例表明这些条件都是非常实用的判定准则,而且还进一步应用这些普遍结果,给出对某些具体公钥加密方案匿名性质的简化证明,并证明了著名的NESSIE方案PSEC-1/2/3的选择密文匿名性质.     

Some Results on Minimal Euclidean Reconstruction from Four Points

Methods for reconstruction and camera estimation from miminal data are often used to boot-strap robust (RANSAC and LMS) and optimal (bundle adjustment) structure and motion estimates. Minimal methods are known for projective reconstruction from two or more uncalibrated images, and for “5 point” relative orientation and Euclidean reconstruction from two calibrated parameters, but we know of no efficient minimal method for three or more calibrated cameras except the uniqueness proof by Holt and Netravali. We reformulate the problem of Euclidean reconstruction from minimal data of four points in three or more calibrated images, and develop a random rational simulation method to show some new results on this problem. In addition to an alternative proof of the uniqueness of the solutions in general cases, we further show that unknown coplanar configurations are not singular, but the true solution is a double root. The solution from a known coplanar configuration is also generally unique. Some especially symmetric point-camera configurations lead to multiple solutions, but only symmetry of points or the cameras gives a unique solution.     

Some Ergodic Results on Stochastic Iterative Discrete Events Systems

This paper deals with the asymptotic behavior of the stochastic dynamics of discrete event systems. In this paper we focus on a wide class of models arising in several fields and particularly in computer science. This class of models may be characterized by stochastic recurrence equations in ^K of the form T(n+1) = _n+1(T(n)) where _n is a random operator monotone and 1—linear. We establish that the behaviour of the extremas of the process T(n) are linear. The results are an application of the sub-additive ergodic theorem of Kingman. We also give some stability properties of such sequences and a simple method of estimating the limit points.     

加细覆盖下模糊广义粗集的一些基本结果

论文从拓扑学角度研究覆盖近似空间(U,C),提出了加细覆盖的概念,讨论了加细覆盖近似空间的约简问题;同时给出了对定义在加细覆盖近似空间上的模糊集进行上、下近似计算的一种计算方法,并讨论该算法的一些性质。     

Some Results on the Working Set Anomalies in Numerical Programs

This paper shows that the working set parameter-real memory and real memory-fault rate anomalies mentioned by Franklin, Graham, and Gupta in [13] do occur in traces generated by real programs. The results of the detailed investigation of this anomalous behavior in four Fortran programs are presented. In some cases a drop of a factor of two in the average real-time memory allotment is observed when the window size is increased. In some instances a bigger real-time memory allotment means an order of magnitude increase in page faults.     

关于超图自同构群的若干结论

利用超图在新的公理体系下同构的定义,给出超图自同构群的定义,这与特殊的情形——图的自同构群的定义是相容的,并将图的自同构群的一些结论在超图中进行推广。     

Derandomization,witnesses for Boolean matrix multiplication and construction of perfect hash functions

Small sample spaces with almost independent random variables are applied to design efficient sequential deterministic algorithms for two problems. The first algorithm, motivated by the attempt to design efficient algorithms for the All Pairs Shortest Path problem using fast matrix multiplication, solves the problem of computingwitnesses for the Boolean product of two matrices. That is, ifA andB are twon byn matrices, andC=AB is their Boolean product, the algorithm finds for every entryC _ij =1 a witness: an indexk so thatA _ik =B _kj =1. Its running time exceeds that of computing the product of twon byn matrices with small integer entries by a polylogarithmic factor. The second algorithm is a nearly linear time deterministic procedure for constructing a perfect hash function for a givenn-subset of {1,...,m}.Part of this paper was presented at the IEEE 33rd Symposium on Foundations of Computer Science.Research supported in part by a USA-Israeli BSF grant and by the Fund for Basic Research administered by the Israel Academy of Sciences.Supported by an Alon Fellowship and by a grant from the Israel Science Foundation administered by the Israeli Academy of Sciences. Some of this work was done while the author was with the IBM Almaden Research Center.     

部分K值逻辑中正则可离函数集的一些结果

根据部分多值逻辑完备性理论,证明了当m=2,σ=e时,若正则可离函数关系G2=G2(｛1,2｝)∪G"2之关系图的基础图连通且如含回路必须是M-回路,则T(G2)不是PK*的最小覆盖成员。     

Some Equivalence Results for Load-Independent Exponential Queueing Networks

In this paper we derive a number of results concerning the behavior of closed load-independent exponential queueing networks. It is shown that if the service rate of any station is increased (decreased), then the throughput of the network itself also increases (decreases). This is not true for product form networks in general. In addition, if the service rate at server i is increased then both the mean queue length and mean waiting time at server i decrease while both these quantities increase at all stations j ? i. The opposite effect is observed if the senrvice rate at station i is decreased. The main result of the paper is a proof of the conjective that corresponding to any general closed queueing network consisting of M stations and in which N customers circulate according to the elements of an irreducible stochastic routing matrix Q, there exists a closed load-independent exponential queueing network with the same M, N, and Q such that the mean number of customers at each station in the exponential network is equal to that in the general network. If the network throughput is specified, it is shown that this exponential network iS unique.     

Redundancy in Data Structures: Some Theoretical Results

A companion paper, "Redundancy in Data Structures: Improving Software Fault Tolerance," provides an infonnal introduction to robust data structures. Here, we present the underlying theory for them, and use it to discuss the synthesis and cost effectiveness of robust data structures.