New Lower Bounds of the Size of Error-Correcting Codes for the Z-Channel

Optimization problems on graphs are formulated to obtain new lower bounds of the size of error-correcting codes for the Z-channel.     

Nonbinary Quantum Goppa Codes Exceeding the Quantum Gilbert-Varshamov Bound

An explicit construction for nonbinary quantum Goppa codes exceeding the quantum Gilbert-Varshamov bound is given. First, we introduce a weighted symplectic inner product and show a method how to transform weighted codes into quantum codes with respect to the standard symplectic inner product. Then an algorithm to construct a quantum code out of any hyperelliptic curve is presented and implemented in Magma. Finally, we apply a generalization of this algorithm to a tower of function fields by Stichtenoth and show that these codes lie above the quantum Gilbert-Varshamov bound.      

Partition-Based Lower Bound for Max-CSP

In this paper we address Max-CSP, a constraint optimization problem typically solved using a branch and bound scheme. It is well known that the efficiency of branch and bound greatly depends on the quality of the available lower bound. Previous approaches aggregate to the lower bound individual contributions of unassigned variables. In this paper, we augment this approach by adding global contributions of disjoint subsets of unassigned variables, which requires a partition of the set of unassigned variables. Using this idea, we introduce the partition-based lower bound. It improves previous approaches based on individual contributions in the sense that our method can be added up to previous bounds, possibly increasing their value. We demonstrate our method presenting two new algorithms, PFC-PRDAC and PFC-MPRDAC, which are the natural successors of PFC-RDAC and PFC-MRDAC augmented with our approach. We provide experimental evidence for the superiority of the new algorithms on random problems and real instances of weighted over-constrained problems.     

Lower Bound Methods and Separation Results for On-Line Learning Models

We consider the complexity of concept learning in various common models for on-line learning, focusing on methods for proving lower bounds to the learning complexity of a concept class. Among others, we consider the model for learning with equivalence and membership queries. For this model we give lower bounds on the number of queries that are needed to learn a concept class in terms of the Vapnik-Chervonenkis dimension of , and in terms of the complexity of learning with arbitrary equivalence queries. Furthermore, we survey other known lower bound methods and we exhibit all known relationships between learning complexities in the models considered and some relevant combinatorial parameters. As it turns out, the picture is almost complete. This paper has been written so that it can be read without previous knowledge of Computational Learning Theory.     

多状态网络可靠度下界的矩阵分解算法

为减少计算多状态网络可靠度精确值的复杂性,提出基于分解计算多状态网络不可靠度精确值的思想,在此基础上提出一个求解多状态网络不可靠度动态上界(对应于可靠度动态下界)的算法.算法先通过分解运算去除某些边引起的d-最小割集之间的相关性,将网络不可靠度转化为多个互斥事件的概率之和,再应用MESP界求取这些事件的概率,计算网络不可靠度上界,对应得到可靠度下界,并计算了得到的可靠度下界与精确值间的绝对误差界.通过定义d-最小割集矩阵,利用矩阵分解实现算法,结构清晰、便于编程计算.相关引理的证明及算例分析表明随着分解的深入,算法能够得到满足精度要求的可靠度下界.     

Lower bounds for the multiplicative complexity of matrix multiplication

We prove a lower bound of km + mn + k—m + n— 3 for the multiplicative complexity of the multiplication of -matrices with -matrices using the substitution method. Received: July 8, 1997.     

Lower bounds for maximal and convex layers problems

In this paper we derive tight lower bounds for the maximal and convex layers problems in the plane. Our lower bound proofs for the maxima problem and convex hull problem are simpler than those previously known. We also obtain an (nlog n) lower bound for the maximal depth problem, and the convex depth problem, when the points are given in sorted order of their x-coordinates.     

Lower bounds for the bilinear complexity of associative algebras

Let R(A) denote the bilinear complexity (also called rank) of a finite dimensional associative algebra A.?We prove that if the decomposition of into simple algebras contains only noncommutative factors, that is, the division algebra is noncommutative or . In particular, -matrix multiplication requires at least essential bilinear multiplications. We also derive lower bounds of the form essential bilinear multiplications. We also derive lower bounds of the form for the algebra of upper triangular -matrices and the algebra of truncated bivariate polynomials in the indeterminates X,Y over some field k.?A class of algebras that has received wide attention in this context con-sists of those algebras A for which the Alder—Strassen Bound is sharp, i.e., R(A) = 2dim A—t is the number of maximal twosided ideals in A. These algebras are called algebras of minimal rank. We determine all semisimple algebras of minimal rank over arbitrary fields and all algebras of minimal rank over algebraically closed fields. Received: January 12, 2000.     

一种基于下界估计的动态表调度算法

调度是高层次综合的核心步骤之一。该文分析了常用的调度算法,并提出一种基于下界估计的动态表调度算法,实验数据表明该方法可以有效地实现多目标的优化。     

布尔函数线路复杂度的一个新的下界

布尔函数的线路复杂下界问题与Ｐ＝？ＮＰ问题有密切关系，若证明了ＮＰ中某问题的线路复杂度是非多项式的，则Ｐ≠ＮＰ。但证明了一个具体的布尔函数具有非线性的线路复杂度下界却是计算复杂性理论中最难的问题之一。迄今此问题的最好结果是由Ｎ．Ｂｌｕｍ于１８９４年给出的，他证明了一个布尔函数具有３ｎ－３的线路复杂度下界。本文针对同一个布尔函数，给出一个更好的下界３ｎ＋１。     

A Tight Lower Bound for a Special Case of Quadratic 0–1 Programming

We consider a still NP-complete partial case of the unconstrained binary quadratic optimization problem that can be described in terms of an undirected graph with red edges having negative weights and green edges having positive weights. The maximum vertex degree of the graph is three. It can be assumed w.l.o.g. that every vertex is incident to a red and a green edge. We are looking for a vertex cover with respect to the red edges which covers a subset of green edges of total weight as small as possible. We prove that for all connected such graphs except a subclass of special graphs having exactly five green edges it is possible to find a vertex cover with respect to the red edges for which the total weight of uncovered green edges is at least 1/4 fraction of the total weight of all green edges.     

A lower bound method for quantum circuits

Quantum circuits, which are shallow, limited in the number of gates and additional workspace qubits, are popular for quantum computation because they form the simplest possible model similar to the classical model of a network of Boolean gates and capable of performing non-trivial computation. We give a new lower bound technique for such circuits and use it to give another proof that deterministic computation of the parity function cannot be performed by such circuits.     

Lower bounds for monotone span programs

Span programs provide a linear algebraic model of computation. Lower bounds for span programs imply lower bounds for formula size, symmetric branching programs, and contact schemes. Monotone span programs correspond also to linear secret-sharing schemes. We present a new technique for proving lower bounds for monotone span programs. We prove a lower bound of (m ^2.5) for the 6-clique function. Our results improve on the previously known bounds for explicit functions.     

A Tight Lower Bound for Computing the Diameter of a 3D Convex Polytope

The diameter of a set P of n points in ℝ ^d is the maximum Euclidean distance between any two points in P. If P is the vertex set of a 3-dimensional convex polytope, and if the combinatorial structure of this polytope is given, we prove that, in the worst case, deciding whether the diameter of P is smaller than 1 requires Ω(nlog n) time in the algebraic computation tree model. It shows that the O(nlog n) time algorithm of Ramos for computing the diameter of a point set in ℝ³ is optimal for computing the diameter of a 3-polytope. We also give a linear time reduction from Hopcroft’s problem of finding an incidence between points and lines in ℝ² to the diameter problem for a point set in ℝ⁷.     

A Linear Time Lower Bound on McCreight and General Updating Algorithms for Suffix Trees

Suffix trees are the fundamental data structure of combinatorial pattern matching on words. Suffix trees have been used in order to give optimal solutions to a great variety of problems on static words, but for practical situations, such as in a text editor, where the incremental changes of the text make dynamic updating of the corresponding suffix trees necessary, this data structure alone has not been used with success. We prove that, for dynamic modifications of order O(1) of words of length n, any suffix tree updating algorithm, such as the ones proposed by McCreight, requires O(n) worst-case running time, as for the full reconstruction of the suffix tree. Consequently, we argue that this data structure alone is not appropriate for the solution of combinatorial problems on words that change dynamically.     

A Separation Bound for Real Algebraic Expressions

Real algebraic expressions are expressions whose leaves are integers and whose internal nodes are additions, subtractions, multiplications, divisions, k-th root operations for integral k, and taking roots of polynomials whose coefficients are given by the values of subexpressions. We consider the sign computation of real algebraic expressions, a task vital for the implementation of geometric algorithms. We prove a new separation bound for real algebraic expressions and compare it analytically and experimentally with previous bounds. The bound is used in the sign test of the number type leda::real. Partially supported by the IST Programme of the EU as a Shared-cost RTD (FET Open) Project under Contract No IST-2000-26473 (ECG—Effective Computational Geometry for Curves and Surfaces).     

A 3-Party Simultaneous Protocol for SUM-INDEX

Abstract. We show that the SUM-INDEX function can be computed by a 3-party simultaneous protocol in which one player sends only O(n ^ɛ ) bits and the other sends O(n ^1-C(ɛ) ) bits (0<C(ɛ)<1 ). This implies that, in the Valiant—Nisan—Wigderson approach for proving circuit lower bounds, the SUM-INDEX function is not suitable as a target function.     

Lower Bounds for Dynamic Tree Embedding in Bipartite Networks

There are many parallel computations that are tree structured. The structure of a tree is usually unpredictable at compiler-time; the tree grows gradually during the course of a computation. The dynamic tree embedding problem is to distribute the processes of a parallel computation over processors in a parallel computer such that processors perform roughly the same amount of computation, and that communicating processes are assigned to processors that are close to each other. In this paper, we establish lower bounds for the performance ratio of dynamic tree embedding in bipartite static networks, including numerous important networks such asn-dimensional meshes,n-dimensional tori,k-aryn-cubes, cube-connected cycles, and butterflies. Our lower bounds are obtained from both tree and network properties and are applicable to a general class of dynamic tree embedding algorithms.