Malign Distributions for Average Case Circuit Complexity

In contrast to machine models like Turing machines or random access machines, circuits are a static computational model. The internal information flow of a computation is fixed in advance, independent of the actual input. Therefore, size and depth are natural and simple measures for circuits and provide a worst-case analysis. We consider a new model in which an internal gate is evaluated as soon as its result has been determined by a partial assignment of its inputs. This way, a dynamic notion of delay is obtained which gives rise to an average case measure for the time complexity of circuits. In a previous paper we have obtained tight upper and lower bounds for the average case complexity of several basic Boolean functions. This paper examines the asymptotic average case complexity for the set of alln-ary Boolean functions. In contrast to worst case analysis a simple counting argument does not work. We prove that with respect to the uniform probability distribution almost all Boolean functions require at leastn−log n−log log nexpected time. On the other hand, there is a significantly large subset of functions that can be computed with a constant average delay. Finally, for an arbitrary Boolean function we compare its worst case and average case complexity. It is shown that for each function that requires circuit depthd, i.e. of worst-case complexityd, the expected time complexity will be at leastd−log n−log dwith respect to an explicitly defined probability distribution. In addition, a nontrivial upper bound on the complexity of such a distribution will be obtained.     

More on Average Case vs Approximation Complexity

We consider the problem to determine the maximal number of satisfiable equations in a linear system chosen at random. We make several plausible conjectures about the average case hardness of this problem for some natural distributions on the instances, and relate them to several interesting questions in the theory of approximation algorithms and in cryptography. Namely we show that our conjectures imply the following facts:

二值图像的区域游动编码及其复杂性分析

本文提出二值图像的一种新的表达及编码方法,此方法可在保持图像区域表达固有特点的基础上使数据得到有效的压缩.文中还对这种表达方法的复杂性作了分析.     

合并排序算法的平均情形复杂性分析及其应用

在合理的“概率分布”假设下,分析了两个有序表合并排序算法的平均情形复杂性,并将此结果应用于个元素的二分排序算法中,最后对二分排序算法的平均情形复杂性进行了估计。     

Optimal Average Case Estimation in Hilbert Norms

In contrast to the worst case approach, the average case setting provides less conservative insight into the quality of estimation algorithms. In this paper we consider two local average case error measures of algorithms based on noisy information, in Hilbert norms in the problem element and information spaces. We define the optimal algorithm and provide formulas for its two local errors, which explicitly exhibit the influence of factors such as information, information (measurement) errors, norms in the considered spaces, a subset where approximations are allowed, and “unmodeled dynamics.” Based on the error expression, we formulate in algebraic language the problem of selecting the optimal approximating subspace. The solution is given along with the specific formula for the error, which depends on the eigenvalues of a certain matrix defined by information and norms under consideration. Date received: November 25, 1999. Date revised: May 30, 2000.     

平均计算时间复杂度优化的动态粒子群优化算法

粒子群优化(PSO:Particle Swarm Optimization)算法已经被广泛地应用,其中包括大量实时性要求很高的领域,如宽带数字信号处理。传统PSO算法需要对大量粒子分别进行若干次迭代运算,这将导致该算法的平均计算时间复杂度较高,运算延时大,不能满足这种高实时性要求。因此,需要在不影响性能的前提下降低PSO算法的平均计算时间复杂度。提出了一种粒子数量可变的动态粒子群优化(DPSO:Dynamic PSO)算法,其核心是丢弃粒子判定条件,在迭代过程中,根据该条件动态地抛弃一些粒子,从而降低算法的平均计算时间复杂度。此外,在算法迭代过程中对粒子的个体极值进行变异,从而避免陷入局部最优解。实验和理论分析结果表明,在算法的平均计算时间复杂度方面,对于相同的优化结果,DPSO算法的平均计算时间复杂度比传统PSO算法降低了30%左右;在算法的性能方面,对于单峰值目标函数,DPSO算法与传统PSO算法的优化性能相当,而对于多峰值目标函数,DPSO算法的优化性能要优于传统PSO算法。     

Decomposability and Relative Invariance: the Structural Approach to Network Complexity and Resilience

Economic complexity highlights the relationship between interdependence (a positional characteristic of elements belonging to a given network or structure) and connectivity (a functional characteristic of elements belonging to a given field of interaction). Positional interdependence (as the one between pieces in a jigsaw puzzle) is central to studies investigating the architecture of a complex system (Simon) while connectivity is central to the analysis of responsiveness patterns in social networks and strategic action fields. This paper discusses the fundamentals of a structural approach to economic and spatial complexity by highlighting the hierarchical arrangement of network elements as a distinctive feature of system identity. The positional distribution of network elements is a fundamental characteristic of complex networks and a central condition constraining the dynamics of those networks through the principle of relative structural invariance. The paper investigates the role of this principle by connecting it with the aggregation criterion followed in assigning network elements to specific subsystems. The type of aggregation is essential in determining the resilience properties of the network with respect to specific dynamic impulses. The paper concludes highlighting the need to combine the investigation of positional interdependence with the analysis of connectivity since positional interdependence is fundamental in determining which patterns of connection are more likely to arise (and which ones are excluded), due to the role of alternative properties of relative invariance constraining the feasible transformations in the positions of network elements.

     

低复杂度的H.264帧间编码的模式判决算法

H.264是最新的国际视频编码标准,它能够提供更高的编码效率,但其编码实现也非常复杂,三叉树结构的多编码模式和多帧参考技术是复杂度增加的两个重要因素.针对这两个因素提出一种用于帧间编码的快速模式判决算法FIMDA,它利用编码过程中获得的模式、码率开销等编码信息来减少那些对编码性能影响不大的参考帧和模式的搜索过程,从而降低编码复杂度.实验结果表明,对常用的5帧参考,与全搜索相比,FIMDA可将编码复杂度降低平均85%以上,而PSNR下降仅在0.07dB左右.     

Average Case Analysis of Searching in Associative Processing

We introduce an average case analysis of the search primitive operations (equality and thresholding) in associative memories. We provide a general framework for analysis, using as parameters the word space distribution and the CAM size parameters:m(number of memory words) andn(memory word length). Using this framework, we calculate the probability that the whole CAM memory responds to a search primitive operation after comparing up tokmost significant bits (1?k?n) in each word; furthermore, we provide a closed formula for the average value ofkand the probability that there exists at least one memory word that equals the centrally broadcast word. Additionally, we derive results for the cases of uniform and exponential distribution of word spaces. We prove that in both cases the average value ofkdepends strongly on lg m, whenn>lg m: for the case of uniform distribution, the average value is practically independent ofn, while in the exponential depends weakly on the difference between the sample space size 2ⁿand the CAM sizem. Furthermore, in both cases, the averagekis approximatelynwhenn?lg m. Verification of our theoretical results through massive simulations on a parallel machine is presented. One of the main results of this work, that the average value ofkcan be much smaller than n or even practically independent ofnin some cases, has an important practical effect: associative memories can be designed with fast execution times of threshold primitives and low implementation complexity, leading to high performance associative memories that can scale up to sizes larger than previous designs at a low cost.     

基于低复杂度编译码的数据流错误纠错方法

针对单粒子翻转可能带来的数据流错误,设计一种改进的数据流错误纠错方法。利用线性分组码的相关理论,分析常用数据流容错方法的容错能力,从线性分组码的编译码原理出发给出一种低复杂度编译码算法,基于该编码的容错方法能够以较少的开销纠正单粒子翻转造成的单比特数据错误。实验结果表明,该方法能够有效纠正单粒子翻转造成的数据错误,与常用的纠检错方法相比,具有较优的纠错性能和较少的容错开销。     

结合双随机相位加密和四元数格拉斯曼平均网络的彩色人脸隐私保护识别

为保护彩色人脸图像的隐私并提高识别准确率,提出一种结合双随机相位加密和四元数格拉斯曼平均网络的彩色人脸隐私保护识别算法.首先将彩色人脸图像的颜色分量编码为纯四元数矩阵,使用双随机相位加密和四元数Gyrator变换进行加密.为了隐藏原始彩色人脸图像的内容,通过随机二值幅度掩模选取部分密文进行解密,得到不可见的人脸图像,然后使用四元数格拉斯曼平均网络提取人脸的特征向量和线性支持向量机进行识别.当人脸特征模板泄露时,可以重新生成随机二值幅度矩阵并构建新的特征模板替换原始的特征模板,满足可撤销性,从而保证原始人脸图像的安全性.在Aberdeen,Georgia Tech,Visible Light和YouTube Makeup 4个数据集上与当前3种人脸隐私保护识别算法进行比较,实验结果表明该算法能够有效地提高识别率,而且对数据集的变化具有较好的鲁棒性.     

基于时间复杂度的无线网络编码数据包平均传输次数优化分析

为提高无线网络编码数据包传输效能,提出了基于时间复杂度的无线网络编码数据包平均传输次数优化方法。首先分析无线网络编码数据包传输信道的多径特性,并根据数据包的多径特性采集有效且安全的数据包,同时在IEEE802.3EFM通信协议下构建数据包的传输信道模型。为提升数据包的传输及存储性能,需建立缓存反馈机制,在该机制作用下设计混合编码。最后采用自适应量化融合编码的方法,进行无线网络编码数据包传输的调制解调处理,结合时间复杂度的衡量算法实现无线网络编码数据包传输的传输次数优化,提升了无线网络混合编码下数据包的传传输效能。仿真结果表明,采用该方法进行无线网络编码数据包传输的输出均衡性较好,传输误码率较低,时间开销较短。     

Average Case Analysis of Bounded Space Bin Packing Algorithms

We consider the one-dimensional bin packing problem and analyze the average case performance of bounded space algorithms. The analysis covers a wide variety of bin packing algorithms including Next-K Fit, K-Bounded Best Fit and Harmonic algorithms, as well as of others. We assume discrete item sizes, an assumption which is true in most real-world applications of bin packing. We present a Markov chains method which is general enough to calculate results for any i.i.d. discrete item size distribution. The paper presents many results heretofore unknown or conjectured from simulation. Some of the results are surprising as they differ considerably from results for continuous distributions.     

A New Approach for Analyzing Average Time Complexity of Population-Based Evolutionary Algorithms on Unimodal Problems

In the past decades, many theoretical results related to the time complexity of evolutionary algorithms (EAs) on different problems are obtained. However, there is not any general and easy-to-apply approach designed particularly for population-based EAs on unimodal problems. In this paper, we first generalize the concept of the takeover time to EAs with mutation, then we utilize the generalized takeover time to obtain the mean first hitting time of EAs and, thus, propose a general approach for analyzing EAs on unimodal problems. As examples, we consider the so-called $(N + N)$ EAs and we show that, on two well-known unimodal problems, leadingones and onemax , the EAs with the bitwise mutation and two commonly used selection schemes both need $O(nln n + n^{2}/N)$ and $O(n lnln n + nln n/N)$ generations to find the global optimum, respectively. Except for the new results above, our approach can also be applied directly for obtaining results for some population-based EAs on some other unimodal problems. Moreover, we also discuss when the general approach is valid to provide us tight bounds of the mean first hitting times and when our approach should be combined with problem-specific knowledge to get the tight bounds. It is the first time a general idea for analyzing population-based EAs on unimodal problems is discussed theoretically.      

非稳定环境下基于竞争消息复杂度的分布式互斥节点容错算法

目前人们已经提出了很多分布式互斥算法.为简化问题,这些算法多数要求假设系统的节点与通信均可靠,因此不存在容错处理问题.部分在先假定节点与通信可靠的基础上讨论的算法,为达到其结论的逻辑严密性,补充了节点与通信不可靠时的容错处理,但这些容错处理方式都是作为其分布式互斥算法的补充提出来的,有较大程度的理想化成分,基本上没用进行充分的性能分析.本文根据分布式互斥算法节点容错处理方式的不同,将其分为两类并对其时消息复杂度的影响进行详细讨论.在此基础上,提出一种混合的分布式互斥节点容错处理方法,以降低非稳定环境下分布式互斥算法的平均消息复杂度.     

非稳定环境下基于竞争消息复杂度的分布式互斥节点容错算法

目前人们已经提出了很多分布式互斥算法。为简化问题,这些算法多数要求假设系统的节点与通信均可靠,因此不存在容错处理问题。部分在先假定节点与通信可靠的基础上讨论的算法,为达到其结论的逻辑严密性,补充了节点与通信不可靠时的容错处理,但这些容错处理方式都是作为其分布式互斥算法的补充提出来的,有较大程度的理想化成分,基本上没用进行充分的性能分析。本文根据分布式互斥算法节点容错处理方式的不同,将其分为两类并对其对消息复杂度的影响进行详细讨论。在此基础上,提出一种混合的分布式互斥节点容错处理方法,以降低非稳定环境下分布式互斥算法的平均消息复杂度。     

Controlled Markov Set-chains with Set-valued Rewards—The Average Case

In this paper, the average case of finite state controlled Markov set-chains with R ^p -set-valued rewards are considered. The optimization is done by a pseudo-order relation on the set of all convex and compact subsets of R ^p induced by a closed convex cone. We introduce a v -step contractive property (minorization condition) for the average case and by use of this method the average expected reward set from a periodic policy is characterized. And, applying the scalarization technique, a Pareto optimal policy is obtained. Also, a numerical example is given to comprehend our results.     

Local Invariance

A local invariant is a set of states of a transition system with the property that every action possible from each of its states takes the system back into the local invariant, unless it is an ‘exit’ action, each of which is accessible from every state in the set via a sequence of non-‘exit’ actions. This idea supports a form of abstraction construction, abstracting away from behaviour internal to the local invariants themselves, that involving their non-‘exit’ actions. In this way, for example, it is possible to construct from a system one which exhibits precisely the externally visible behaviour. This abstraction is reminiscent of hiding in process algebra, and we compare the notion of abstraction with that of observational equivalence in process calculus. Received August 2000 / Accepted in revised form March 2002 Correspondence and offprint requests to: David H. Pitt, Department of Computing, University of Surrey, Guildford GU2 5HX, UK. E-mail: d.pitt@eim.surrey.ac.ukau     

A Framework for Average Case Analysis of Conjunctive Learning Algorithms

We present an approach to modeling the average case behavior of learning algorithms. Our motivation is to predict the expected accuracy of learning algorithms as a function of the number of training examples. We apply this framework to a purely empirical learning algorithm, (the one-sided algorithm for pure conjunctive concepts), and to an algorithm that combines empirical and explanation-based learning. The model is used to gain insight into the behavior of these algorithms on a series of problems. Finally, we evaluate how well the average case model performs when the training examples violate the assumptions of the model.