On the equivalence of binary quartics

We give an extension and correction to a result stated in the first author’s paper [Cremona, J.E., 2001. Classical invariants and 2-descent on elliptic curves. J. Symbolic Comput. 31 (1–2), 71–87; Computational algebra and number theory. Milwaukee, WI, 1996], concerning the equivalence of binary quartics. In the earlier version the cases where I=0$I=0$ or J=0$J=0$ were not fully treated, and neither were the cases of reducible quartics or those whose resolvent cubic is reducible; these are dealt with here. We also give an alternative criterion for equivalence.     

The Variance of the height of binary search trees

By using analytic tools it is shown that the variance E(H_n−EH_n)² of the height H_n of binary search trees of size n is bounded.     

Free binary decision diagrams for the computation of EAR n

Free binary decision diagrams (FBDDs) are graph-based data structures representing Boolean functions with the constraint (additional to binary decision diagram) that each variable is tested at most once during the computation. The function EAR_n is the following Boolean function defined for n × n Boolean matrices: EAR_n(M) = 1 iff the matrix M contains two equal adjacent rows. We prove that each FBDD computing EAR_n has size at least and we present a construction of such diagrams of size approximately .     

On the metric complexity of continuous-time systems

In this paper, metric complexities of certain classes of continuous-time systems are studied, using the time-domain sampling approach and the concepts of Kolmogorov, Gel'fand and sampling n-widths for certain classes of Sobolev space. A sampling theorem is obtained which extends Shannon's sampling theorem to systems with possibly non-band-limited spectra. The theorem demonstrates that continuous-time systems in certain Sobolev spaces can be approximately reconstructed causally from their sampled systems. The Kolmogorov, Gel'fand and sampling n-widths of various uncertainty sets in the Sobolev spaces are derived. The results show that the sampling approach is in fact asymptotically optimal, when the sampling interval is selected to minimize the loss of information in the sampling process, for the modelling of systems in such Sobolev spaces.     

On the computational complexity of combinatorial flexibility problems

The concept of flexibility – originated in the context of heat exchanger networks design – is associated with a substructure which allows the same optimal value on the substructure (for example an optimal flow) as in the whole structure, for all the costs in a given range of costs. In this work, we extend the concept of flexibility to general combinatorial optimization problems, and prove several computational complexity results in this new framework. Under some monotonicity conditions, we prove that a combinatorial optimization problem can be polynomially reduced to its associated flexibility problem. However, the minimum cut, maximum weighted matching and shortest path problems have NP-complete associated flexibility problems. In order to obtain polynomial flexibility problems, we have to restrict ourselves to combinatorial optimization problems on matroids.     

On representations of 2-increasing binary aggregation functions

In this paper, we provide two different representations of 2-increasing binary aggregation functions by means of their lower and upper margins and a suitable copula.     

On the complexity of counting components of algebraic varieties

We give a uniform method for the two problems of counting the connected and irreducible components of complex algebraic varieties. Our algorithms are purely algebraic, i.e., they use only the field structure of C$\mathbb{C}$. They work in parallel polynomial time, i.e., they can be implemented by algebraic circuits of polynomial depth. The design of our algorithms relies on the concept of algebraic differential forms. A further important building block is an algorithm of Szántó computing a variant of characteristic sets. Furthermore, we use these methods to obtain a parallel polynomial time algorithm for computing the Hilbert polynomial of a projective variety which is arithmetically Cohen–Macaulay.     

On the use of binary and gray code schemes for continuous-tone picture representation

The paper discusses the idea of iterating the conversion of a continuous-tone picture from binary to Gray code representation. A simple recursive function is defined by means of which the value of the ith bit representing a picture point's grey level after the mth iteration is determined. The resulting rearrangement of grey levels as well as that of the bits throughout the planes is discussed next. The iteration is shown to repeat after 2″ steps, where n is the number of bit planes representing the picture. A data compression scheme is developed on the basis that prior to exact repetition, approximate repetitions take place during the iterations, and the resulting picture is almost the same as the original.     

The invariants of the binary decimic

We consider the algebra of invariants of binary forms of degree 10 with complex coefficients, construct a system of parameters with degrees 2, 4, 6, 6, 8, 9, 10 and 14 and find the 106 basic invariants.     

On the computational complexity of binary and analog symmetric hopfield nets

We investigate the computational properties of finite binary- and analog-state discrete-time symmetric Hopfield nets. For binary networks, we obtain a simulation of convergent asymmetric networks by symmetric networks with only a linear increase in network size and computation time. Then we analyze the convergence time of Hopfield nets in terms of the length of their bit representations. Here we construct an analog symmetric network whose convergence time exceeds the convergence time of any binary Hopfield net with the same representation length. Further, we prove that the MIN ENERGY problem for analog Hopfield nets is NP-hard and provide a polynomial time approximation algorithm for this problem in the case of binary nets. Finally, we show that symmetric analog nets with an external clock are computationally Turing universal.     

On the computational power of binary decision diagram with redundant variables

We introduce a BDD with redundant variables as an Indexed BDD (IBDD) and define PolyIBDD as the class of Boolean functions represented by polynomial-sized IBDDs for the number of input variables. Assuming that the class of languages on {0, 1}^* that are accepted by logarithmic space bounded DTMs is DLOG, the following relation holds. PolyIBDD = DLOG. That is to say that languages which belong to DLOG also belong to PolyIBDD. We also show examples of polynomial-sized IBDD's construction from logarithmic space bounded DTMs.     

On the computation of convex robust control invariant sets for nonlinear systems

In this paper we provide a method to compute robust control invariant sets for nonlinear discrete-time systems. A simple criterion to evaluate if a convex set in state space is a robust control invariant set for a nonlinear uncertain system is presented. The criterion is employed to design an algorithm for computing a polytopic robust control invariant set. The method is based on the properties of DC functions, i.e. functions which can be expressed as the difference of two convex functions. Since the elements of a wide class of nonlinear functions have DC representation or, at least, admit an arbitrarily close approximation, the method is quite general. The algorithm requires relatively low computational resources.     

On the message complexity of binary byzantine agreement under crash failures

Summary The binary Byzantine Agreement problem requiresn–1 receivers to agree on the binary value broadcast by a sender even when some of thesen processes may be faulty. We investigate the message complexity of protocols that solve this problem in the case of crash failures. In particular, we derive matching upper and lower bounds on the total, worst and average case number of meassages needed in the failure-free executions of such protocols.More specifically, we prove that any protocol that tolerates up tot faulty processes requires a total of at leastn+t–1 messages in its failure-free executions —and, therefore, at least [(n+t–1)/2] messages in the worst case and min (P ₀,P ₁)·(n+t–1) meassages in the average case, whereP _v is the probability that the value of the bit that the sender wants to broadcast isv. We also give protocols that solve the problem using only the minimum number of meassages for these three complexity measures. These protocols can be implemented by using 1-bit messages. Since a lower bound on the number of messages is also a lower bound on the number of meassage bits, this means that the above tight bounds on the number of messages are also tight bounds on the number of meassage bits. Vassos Hadzilacos received a BSE from Princeton University in 1980 and a PhD from Harvard University in 1984, both in Computer Science. In 1984 he joined the Department of Computer Science at the University of Toronto where he is currently an Associate Professor. In 1990–1991 he was visiting Associate Professor in the Department of Computer Science at Cornell University. His research interests are in the theory of distributed systems. Eugene Amdur obtained a B. Math from the University of Waterloo in 1986 and a M.Sc. from the University of Toronto in 1988. He is currently employed by the Vision and Robotics group at the University of Toronto in both technical and research capacities. His current areas of interest are vision, robotics, and networking. Samuel Weber received his B.Sc. in Mathematics and Computer Science and his M.Sc. in Computer Science from the University of Toronto. Currently, he is at Cornell University as a Ph.D. student in Computer Science with a minor in Psychology. His research interests include distributed systems, and the semantics of programming languages.     

On the complexity of signed and minus total domination in graphs

In this paper we present unified methods to solve the minus and signed total domination problems for chordal bipartite graphs and trees in O(n²) and O(n+m) time, respectively. We also prove that the decision problem for the signed total domination problem on doubly chordal graphs is NP-complete. Note that bipartite permutation graphs, biconvex bipartite graphs, and convex bipartite graphs are subclasses of chordal bipartite graphs.     

On complexity of optimal recombination for binary representations of solutions

We consider the optimization problem of finding the best possible offspring as a result of a recombination operator in an evolutionary algorithm, given two parent solutions. The optimal recombination is studied in the case where a vector of binary variables is used as a solution encoding. By means of efficient reductions of the optimal recombination problems (ORPs) we show the polynomial solvability of the ORPs for the maximum weight set packing problem, the minimum weight set partition problem, and for linear Boolean programming problems with at most two variables per inequality, and some other problems. We also identify several NP-hard cases of optimal recombination: the Boolean linear programming problems with three variables per inequality, the knapsack, the set covering, the p-median, and some other problems.