Maximizing Agreements with One-Sided Error with Applications to Heuristic Learning

We study heuristic learnability of classes of Boolean formulas, a model proposed by Pitt and Valiant. In this type of example-based learning of a concept class C by a hypothesis class H, the learner seeks a hypothesis h H that agrees with all of the negative (resp. positive) examples, and a maximum number of positive (resp. negative) examples. This learning is equivalent to the problem of maximizing agreement with a training sample, with the constraint that the misclassifications be limited to examples with positive (resp. negative) labels. Several recent papers have studied the more general problem of maximizing agreements without this one-sided error constraint. We show that for many classes (though not all), the maximum agreement problem with one-sided error is more difficult than the general maximum agreement problem. We then provide lower bounds on the approximability of these one-sided error problems, for many concept classes, including Halfspaces, Decision Lists, XOR, k-term DNF, and neural nets.Editor Philip M. LongThis research was supported by the fund for promotion of research at the Technion. Research no. 120-025.     

On the Complexity of Optimal Hotlink Assignment

The concept of hotlink assignment aims at reducing the navigation effort for users of a web directory or similar structure by inserting a limited number of additional hyperlinks called hotlinks. Given an access probability distribution of the leaves of the tree representing the web site, the goal of hotlink assignment algorithms is to minimize the expected path length between the root and the leaves. We prove that this optimization problem is NP-hard, even if only one outgoing hotlink is allowed for each node. This answers a question that has been open since the first formulation of the problem in Bose et al. (Proceedings of 11th International Symposium on Algorithms and Computation (ISAAC), 2000) nine years ago. In this work we also investigate the model where hotlinks are only allowed to point at the leaves of the tree. We demonstrate that for this model optimal solutions can be computed in O(n ²) time. Our algorithm L-OPT also operates in a more general setting, where the maximum number of outgoing hotlinks is specified individually for each node. The runtime is then O(n ³). Experimental evaluation shows that L-OPT terminates within less than one second on problem instances having up to half a million nodes.     

TSP问题的脂肪计算复杂性与启发式算法设计

旅行商问题(traveling salesman problem,简称TSP)是经典的NP-难解组合优化问题之一,求解它的高效启发式算法一直是计算机科学研究的热点.脂肪作为描述TSP结构特征的新工具,对启发式算法设计具有重要意义.目前,TSP问题的脂肪研究还处于初始阶段,缺乏理论分析结果及相关的启发式算法.首先分析了TSP问题的脂肪计算复杂性,通过构造偏移实例的技巧,证明了获取TSP的脂肪是NP-难解的,即在P(NP的假设下,不存在算法可以在多项式时间内获得完整脂肪.在此基础上,通过分析TSP问题局部最优解与脂肪的关系,给出了求解TSP问题的元启发式算法--动态候选集搜索(dynamic candidate set search,简称DCSS)算法.利用该算法,改进了目前求解TSP问题最好算法之一的LKH.TSPLIB典型实例的实验结果表明,改进后的算法在解的质量上有较为明显的提高.新的基于脂肪的启发式算法对于求解其他NP-难解问题具有一定的参考价值.     

两元指纹向量聚类问题的复杂性与改进启发式算法

证明丢失值位数不超过2的指纹向量聚类问题为NP-Hard,并给出Figueroa等人指纹向量聚类启发式算法的改进算法.主要改进了算法的实现方法.以链表存储相容顶点集合,并以逐位扫描指纹向量的方法产生相容点集链表,可将产生相容点集的时间复杂性由O(m·n·2p)减小为O(m·(n·p 1)·2p),可使划分一个唯一极大团或最大团的时间复杂性由O(m·p·2p)减小为O(m·2p).实际测试显示,改进算法的空间复杂性平均减少为原算法的49%以下,平均可用原算法20%的时间求解与原算法相同的实例.当丢失值位数超过6时,改进算法几乎总可用不超过原算法11%的时间计算与原算法相同的实例.     

NoC处理单元随机舍入的启发式应用映射

在性能约束的前提下,为了降低能量消耗,针对一个集成了异构IP块以分层星型拓扑互连的片上网络(NoC),采用多电压电平操作,运用一种统一方法来解决应用映射问题,并用混合整数线性程序公式化问题,提出了基于随机舍入的NoC处理单元启发式高效应用映射--HAMU法.实验结果表明,HAMU法的效能明显优于其他启发式方法.     

On the Complexity of SOS Programming and Applications in Control Systems

The minimization of a linear cost function subject to the condition that some matrix polynomials depending linearly on the decision variables are sums of squares of matrix polynomials (SOS) is known as SOS programming. This paper proposes an analysis of the complexity of SOS programming, in particular of the number of linear matrix inequality (LMI) scalar variables required for establishing whether a matrix polynomial is SOS. This number is analyzed for real and complex matrix polynomials, in the general case and in the case of some exact reductions achievable for some classes of matrix polynomials. An analytical formula is proposed in each case in order to provide this number as a function of the number of variables, degree and size of the matrix polynomials. Some tables reporting this number are also provided as reference for the reader. Two applications in control systems are presented in order to show the usefulness of the proposed results.     

Windows平台下密码模块替换技术及应用

分析了Windows平台下密码开发接口CryptoAPI的体系结构，提出了在Windows平台下通过CSP技术将国产软件或硬件密码模块集成到CrptoAPI体系中的方法，并且具体介绍其在SSL协议中的应用。该方法有助于提高国内电子商务和电子政务的安全性。     

Proof Nets and the Complexity of Processing Center Embedded Constructions

This paper shows how proof nets can be used to formalize the notion of incomplete dependency used in psycholinguistic theories of the unacceptability of center embedded constructions. Such theories of human language processing can usually be restated in terms of geometrical constraints on proof nets. The paper ends with a discussion of the relationship between these constraints and incremental semantic interpretation.     

启发式算法设计中的骨架分析与应用

骨架是指一个NP-难解问题实例的所有全局最优解的相同部分, 因其在启发式算法设计中的重要作用而成为该领域的研究热点. 本文对目前骨架及相关概念的研究成果进行了全面综述, 将骨架本身的研究工作归纳为三个层面: 理论基础层面主要考虑骨架与计算复杂性的关系问题; 应用基础层面主要考虑如何高效地获取骨架; 应用层面主要考虑如何利用骨架进行高效启发式算法设计. 在此基础上, 本文详细讨论了骨架研究亟待解决的难题, 并指出了解决这些问题的努力方向.     

Proof Transformation via Interpretation Functions: Results, Problems and Applications

Change is a constant factor in Software Engineering process. Redesign of a class structure requires transformation of the corresponding OCL constraints. In a previous paper we have shown how to use, what we call, interpretation functions for transformation of constraints. In this paper we discuss recently obtained results concerning proof transformations via such functions. In particular we detail the fact that they preserve proofs in equational logic, as well as proofs in other logical systems like propositional logic with modus ponens or proofs using resolution rule. Those results have direct applications to redesign of UML State Machines and Sequence Diagrams. If states in a State Machine are interpreted by State Invariants, then the topological relations between its states can be interpreted as logical relations between the corresponding formulas. Preservation of the consequence relation can bee seen as preservation of the topology of State Machines. We indicate also an unsolved problem and discuss the mining of its positive solution.     

Commentary on Alan M. Turing: The Applications of Probability to Cryptography

Abstract

In April 2012, two papers written by Alan Turing during the Second World War on the use of probability in cryptanalysis were released by GCHQ. The longer of these presented an overall framework for the use of Bayes's theorem and prior probabilities, including four examples worked out in detail: the Vigenère cipher, a letter subtractor cipher, the use of repeats to find depths, and simple columnar transposition. (The other paper was an alternative version of the section on repeats.) Turing stressed the importance in practical cryptanalysis of sometimes using only part of the evidence or making simplifying assumptions and presents in each case computational shortcuts to make burdensome calculations manageable. The four examples increase roughly in their difficulty and cryptanalytic demands. After the war, Turing's approach to statistical inference was championed by his assistant in Hut 8, Jack Good, which played a role in the later resurgence of Bayesian statistics.     

上下文无关文法推断中的几条启发规则及其应用

本文先简要介绍了一种上下文无关文法的推断方法--逐步求精法，然后论述了递归概念在文法推断中的核心作用，并从递归概念的特殊性质出发提出了多条启发规则，能有效减少无效探求和与用户交互的次数，尤其适合于文法较复杂、例句集信息量较大的情况。这些启发规则同时也适用于对上下文无关文法的其它推断方法。     

哈希证明系统及应用研究

哈希证明系统在2002年欧密会上由Cramcr和Shoup首次提出。哈希证明系统的概念自提出以来得到广泛 研究,目前已有多个修改版本。“投影性”和“平滑性”是哈希证明系统的两个重要特性,正是由于这两个特性使得哈希 证明系统除了用于设计CCA安全的公钥加密体制之外,还广泛应用于各种安全协议设计,比如:基于口令认证的密钥 交换协议、不经意传输协议、可否认的认证协议、零知识证明协议和承诺协议等。介绍了哈希证明系统及其变形的各 种定义,分析了定义之间的派生关系和安全级别关系,并讨论了哈希证明系统在密码学中的应用.     

Elliptic Curve Cryptography; Applications,challenges, recent advances,and future trends: A comprehensive survey

Elliptic Curve (EC) is the most recent and advanced technique of Elliptic Curve Cryptography (ECC). EC is often used to improve the security of open communication networks and to let specific persons with confirmed identities into the Modern Digital Era (MDE). Users of MDE make use of many technologies, such as social media, the cloud, and the IoT industry, among others. No matter what tool the users are using, the whole environment has to be able to keep their security and privacy preserved.The study of cryptography is required because unsecure networks make data transmission and the transfer of information susceptible to data theft and attack via an open channel. This makes it necessary to learn cryptography. The art of encrypting documents and communications using keys in such a way that only the individuals who are intended to receive them are able to decode and process them is referred to as cryptography. A digital signature, cryptographic data integrity, and authentication method all rely on the address of the receiver and the sender in addition to mathematical operations to find the signature. During the process of signature and verification, the solution that was presented is compared with the technique that is currently being used by ECDSA in order to illustrate the differences that exist between the two processes.This comprehensive survey of EC seeks to thoroughly investigate many scientific concepts, state-of-the-art, and innovative methodologies and implementations. This work will be useful for academics, who are interested in further analysis. Use and development of EC based schemes for cloud computing, e-health, and e-voting, is more secure as compared to RSA, and Diffie–Hellman schemes. In this comprehensive study, we claim that the adoption of EC methods in distributed computing and asynchronous networking provides significant benefits in distributed computing and interdependent networking.