Efficient Two-Stage Group Testing Algorithms for Genetic Screening

Efficient two-stage group testing algorithms that are particularly suited for rapid and less-expensive DNA library screening and other large scale biological group testing efforts are investigated in this paper. The main focus is on novel combinatorial constructions in order to minimize the number of individual tests at the second stage of a two-stage disjunctive testing procedure. Building on recent work by Levenshtein (Discrete Math., 266:293–309, 2003) and Tonchev (J. Comb. Optim., 15:1–6, 2008), several new infinite classes of such combinatorial designs are presented.     

Efficient Incremental Algorithms for the Sparse Resultant and the Mixed Volume

We propose a new and efficient algorithm for computing the sparse resultant of a system of n + 1 polynomial equations in n unknowns. This algorithm produces a matrix whose entries are coefficients of the given polynomials and is typically smaller than the matrices obtained by previous approaches. The matrix determinant is a non-trivial multiple of the sparse resultant from which the sparse resultant itself can be recovered. The algorithm is incremental in the sense that successively larger matrices are constructed until one is found with the above properties. For multigraded systems, the new algorithm produces optimal matrices, i.e. expresses the sparse resultant as a single determinant. An implementation of the algorithm is described and experimental results are presented. In addition, we propose an efficient algorithm for computing the mixed volume of n polynomials in n variables. This computation provides an upper bound on the number of common isolated roots. A publicly available implementation of the algorithm is presented and empirical results are reported which suggest that it is the fastest mixed volume code to date.     

Approximability of Sparse Integer Programs

The main focus of this paper is a pair of new approximation algorithms for certain integer programs. First, for covering integer programs {min cx:Ax≥b,0≤x≤d} where A has at most k nonzeroes per row, we give a k-approximation algorithm. (We assume A,b,c,d are nonnegative.) For any k≥2 and ε>0, if P≠NP this ratio cannot be improved to k−1−ε, and under the unique games conjecture this ratio cannot be improved to k−ε. One key idea is to replace individual constraints by others that have better rounding properties but the same nonnegative integral solutions; another critical ingredient is knapsack-cover inequalities. Second, for packing integer programs {max cx:Ax≤b,0≤x≤d} where A has at most k nonzeroes per column, we give a (2k ²+2)-approximation algorithm. Our approach builds on the iterated LP relaxation framework. In addition, we obtain improved approximations for the second problem when k=2, and for both problems when every A _ij is small compared to b _i . Finally, we demonstrate a 17/16-inapproximability for covering integer programs with at most two nonzeroes per column.     

面向高可信软件的整数溢出错误的自动化测试

面向高可信软件提出了一种二进制级高危整数溢出错误的全自动测试方法(dynamic automatic integer-overflow detection and testing,简称DAIDT).该方法无需任何源码甚至是符号表支持,即可对二进制应用程序进行全面测试,并自动发现高危整数溢出错误.在理论上形式化证明了该技术对高危整数溢出错误测试与发掘的无漏报性、零误报性与错误可重现特性.为了验证该方法的有效性,实现了IntHunter原型系统.IntHunter对3个最新版本的高可信应用程序(微软公司Windows 2003和2000 Server的WINS服务、百度公司的即时通讯软件BaiDu Hi)分别进行了24小时测试,共发现了4个高危整数溢出错误.其中3个错误可导致任意代码执行,其中两个由微软安全响应中心分配漏洞编号CVE-2009-1923,CVE-2009-1924,另一个由百度公司分配漏洞编号CVE-2008-6444.     

Distribution-Free Connectivity Testing for Sparse Graphs

We consider distribution-free property-testing of graph connectivity. In this setting of property testing, the distance between functions is measured with respect to a fixed but unknown distribution D on the domain, and the testing algorithm has an oracle access to random sampling from the domain according to this distribution D. This notion of distribution-free testing was previously defined, and testers were shown for very few properties. However, no distribution-free property testing algorithm was known for any graph property. We present the first distribution-free testing algorithms for one of the central properties in this area—graph connectivity (specifically, the problem is mainly interesting in the case of sparse graphs). We introduce three testing models for sparse graphs:

Parallel Algorithms for Counting and Randomly Generating Integer Partitions

This paper presents parallel algorithms for determining the number of partitions of a given integerN, where the partitions may be subject to restrictions, such as being composed of distinct parts, of a given number of parts, and/or of parts belonging to a specified set. We present a series of adaptive algorithms suitable for varying numbers of processors. The fastest of these algorithms computes the number of partitions ofnwith largest part equal tok, for 1 ≤k≤n≤N, in timeO(log²(N)) usingO(N²/logN) processors. Parallel logarithmic time algorithms that generate partitions uniformly at random, using these quantities, are also presented.     

Algorithms for Testing Satisfiability Formulas

The present paper presents algorithms for testing satisfiabily of clausalformulas in the propositional logic and the firs-order logic. The algorithmbased on the enumeration of solutions for testing the satisfiability ofpropositional formula, has already been given by K. Iwama, O. Dubois. Theoriginality in this paper is to combine this algorithm to other procedures,especially with the pure-literal literal and the one-literal rule, and also theone which consists in changing any formulas in formulas bounded. Thealgorithm based on the enumeration of the solution combined to theseprocedures is more efficient. The algorithm based on the concept ofresolutive derivation from Skolem normal form of formula in first-order logic, has already been given. The idea in present's paper is tocombined to this algorithm to process of elimination of tautological clausesand process of elimination of subsumed clauses.     

一类整数性目标规划的遗传算法

本文给出了以惩罚函数法将约束优化问题转化为无约束优化问题的通用算法,提出了将遗传算法和惩罚函数法相结合用于求解整数性目标规划问题的具体方法。计算机数值仿真结果表明了该方法的有效性。     

应用于脑机接口系统的动态稀疏矩阵压缩算法

在脑机接口系统中,高通道数神经信号采集是一个核心功能模块。在高通道数神经信号采集中,因其原始数据量巨大,直接传输和处理产生的原始数据会消耗极大的功耗并增加硬件设计上的难度。为解决这个问题,一个有效的方法是在数据传输和处理前对原始数据进行压缩。神经元动作电位信号具有不应期性的特点,文中利用此特点,将多通道神经信号的数字标记输出在一定时间范围内定义为一个稀疏矩阵,并对此稀疏矩阵进行特征提取,根据其特征动态地采用优化算法进行数据压缩。文中的算法在使用FPGA作为中控硬件的32通道神经采集硬件系统上通过实时验证,实验证明文中提出的动态稀疏矩阵压缩算法可实现83.4%的数据压缩率。     

Block Local Elimination Algorithms for Sparse Discrete Optimization Problems

Block local elimination algorithms for solving sparse discrete optimization problems are considered. A numerical example is provided. The benchmarking is done in order to determine the real computational capabilities of block elimination algorithms combined with SYMPHONY solver. The analysis of the results shows that for a sufficiently large number of blocks and rather small size of separators between the blocks for a staircase integer linear programming problem, local elimination algorithms in combination with the solver for subproblems in blocks allow a much faster solution of such problems than the solver itself used to solve the whole problem. The capabilities of the postoptimal analysis (warm start) are also considered for solving packages of integer linear programming problems for the corresponding blocks.     

RSA密码系统有效实现算法

本文提出了实现RSA算法的一种快速、适合于硬件实现的方案，在该方案中，我们作用加法链将求幂运算转化为求平方和乘法运算并大大降低了运算的次数，使用Montgomery算法将模N乘法转化为模R（基数）的算法，模R乘积的转化，以及使用一种新的数母加法器作为运算部件的基础。     

Efficient Algorithms for Interface Timing Verification

This paper presents algorithms for computing separations between events that are constrained to obey prespecified relationships in their relative time of occurrence. The algorithms are useful for interface timing verification, where event separations are checked against timing requirements. The first algorithm computes separations when only linear and max constraints exist. The algorithm must converge to correct maximum separation values in a finite number of steps, or report an inconsistence of the constraints, irrespective of the existence of infinite constraint bounds or infinite event separations. It is conjectured to run in time, where V is the number of events, and E is the number of relationships between them. The other algorithms extend the first, and compute event separations in the NP-complete version of the problem where min constraints exist. Experiments demonstrate the algorithms are efficient in practice.     

基于整数变换的全零块判决方法

H．263中的运动搜索和变换域编码是运算量很大的部分，也是影响系统实时性能的瓶颈，为了减少图像编码的运算量，在采用整数变换代替浮点DCT变换的基础上，提出了一种全局判决方法，即在运动搜索中和变换前进行全零块判决。该方法是根据整数变换和量化结果为零的特点，在运动搜索中，对差值块先进行全零块判决，如果找到全零块，就停止搜索，以省却以后的搜索运算和全零块的整数变换以及相应的量化运算，由于其可在基本保持H．263原有编码算法图像质量的同时，减少运算量和缩短码流，从而大幅度提高了编码器的编码效率。     

Efficient Parallel Algorithms for Planar st-Graphs

Planar st -graphs find applications in a number of areas. In this paper we present efficient parallel algorithms for solving several fundamental problems on planar st -graphs. The problems we consider include all-pairs shortest paths in weighted planar st -graphs, single-source shortest paths in weighted planar layered digraphs (which can be reduced to single-source shortest paths in certain special planar st -graphs), and depth-first search in planar st -graphs. Our parallel shortest path techniques exploit the specific geometric and graphic structures of planar st -graphs, and involve schemes for partitioning planar st -graphs into subgraphs in a way that ensures that the resulting path length matrices have a monotonicity property [1], [2]. The parallel algorithms we obtain are a considerable improvement over the previously best known solutions (when they are applied to these st -graph problems), and are in fact relatively simple. The parallel computational models we use are the CREW PRAM and EREW PRAM.     

Efficient Parallel Algorithms for Permutation Graphs

In this paper, we present optimal O(log n) time, O(n/log n) processor EREW PRAM parallel algorithms for finding the connected components, cut vertices, and bridges of a permutation graph. We also present an O(log n) time, O(n) processor, CREW PRAM model parallel algorithm for finding a Breadth First Search (BFS) spanning tree of a permutation graph rooted at vertex 1 and use the same to derive an efficient parallel algorithm for the All Pairs Shortest Path problem on permutation graphs.     

RSA密码系统有效实现算法

大整数模幂乘运算一直是制约RSA广泛应用的瓶颈,在对传统算法剖析的基础上,提出了一种新的快速模乘算法,借鉴生成Wallace tree的思想,结合查找表和并行乘法运算进行RSA模幂运算。理论分析和试验证明新算法时间复杂度降低到O(logn)。     

Efficient Algorithms for k Maximum Sums

We study the problem of computing the k maximum sum subsequences. Given a sequence of real numbers and an integer parameter k, the problem involves finding the k largest values of for The problem for fixed k = 1, also known as the maximum sum subsequence problem, has received much attention in the literature and is linear-time solvable. Recently, Bae and Takaoka presented a -time algorithm for the k maximum sum subsequences problem. In this paper we design an efficient algorithm that solves the above problem in time in the worst case. Our algorithm is optimal for and improves over the previously best known result for any value of the user-defined parameter k < 1. Moreover, our results are also extended to the multi-dimensional versions of the k maximum sum subsequences problem; resulting in fast algorithms as well.