Lower bounds on arithmetic circuits via partial derivatives

In this paper we describe a new technique for obtaining lower bounds on restricted classes of non-monotone arithmetic circuits. The heart of this technique is a complexity measure for multivariate polynomials, based on the linear span of their partial derivatives. We use the technique to obtain new lower bounds for computing symmetric polynomials (that hold over fields of characteristic zero) and iterated matrix products (that hold for all fields).Dedicated to the memory of Roman Smolensky     

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.     

Lower bounds for modular counting by circuits with modular gates

We prove that constant depth circuits, with one layer of M O D _m gates at the inputs, followed by a fixed number of layers of M O D _p gates, where p is prime, require exponential size to compute the M O D _q function, if q is a prime that divides neither p nor m. Received: January 23, 1998.     

Lower bounds on treespan

Recently Fomin, Heggernes and Telle [Algorithmica 41 (2004) 73] introduced the notion of the treespan of a graph as a natural extension of the well-known bandwidth. They motivate this new concept from different viewpoints involving graph searching, tree decompositions and elimination orderings. In the present paper we prove several lower bounds on the treespan.     

云环境下基于运算电路的同态认证方案

针对云服务器上数据验证效率低的问题,为能够在正确执行用户指令的情况下依然保持对数据的高效验证,构造了一种支持云环境下基于运算电路的同态认证方案。首先,利用标签生成算法对验证标签进行多项式表示;其次,调用转化算法对验证标签进行转化以达到满足同态验证的形式,同时利用同态解密算法对验证标签的大小进行降维处理;最后,运用验证算法对检索结果进行验证。结果表明,所提方案能够支持任意次乘法同态而不会增加验证标签维数,克服了验证标签增长缺陷,提高了验证效率,但其计算复杂度会随着增强电路输入位的增加而增加。     

Monotone circuits for monotone weighted threshold functions

Weighted threshold functions with positive weights are a natural generalization of unweighted threshold functions. These functions are clearly monotone. However, the naive way of computing them is adding the weights of the satisfied variables and checking if the sum is greater than the threshold; this algorithm is inherently non-monotone since addition is a non-monotone function. In this work we by-pass this addition step and construct a polynomial size logarithmic depth unbounded fan-in monotone circuit for every weighted threshold function, i.e., we show that weighted threshold functions are in mAC¹. (To the best of our knowledge, prior to our work no polynomial monotone circuits were known for weighted threshold functions.)Our monotone circuits are applicable for the cryptographic tool of secret sharing schemes. Using general results for compiling monotone circuits (Yao, 1989) and monotone formulae (Benaloh and Leichter, 1990) into secret sharing schemes, we get secret sharing schemes for every weighted threshold access structure. Specifically, we get: (1) information-theoretic secret sharing schemes where the size of each share is quasi-polynomial in the number of users, and (2) computational secret sharing schemes where the size of each share is polynomial in the number of users.     

Graph-based evolutionary design of arithmetic circuits

We present an efficient graph-based evolutionary optimization technique, called evolutionary graph generation (EGG), and the proposed approach is applied to the design of combinational and sequential arithmetic circuits based on parallel counter-tree architecture. The fundamental idea of EGG is to employ general circuit graphs as individuals and manipulate the circuit graphs directly using new evolutionary graph operations without encoding the graphs into other indirect representations, such as the bit strings used in genetic algorithm (GA) proposed by Holland (1992) and trees used in genetic programming (GP) proposed by Koza et al. (1997). In this paper, the EGG system is applied to the design of constant-coefficient multipliers and the design of bit-serial data-parallel adders. The results demonstrate the potential capability of EGG to solve the practical design problems for arithmetic circuits with limited knowledge of computer arithmetic algorithms. The proposed EGG system can help to simplify and speed up the process of designing arithmetic circuits and can produce better solutions to the given problem     

Lower bounds on online deadline scheduling with preemption penalties

We generalize and improve previous results of online preemptive deadline scheduling with preemption penalties. We consider both the preemption-restart and the preemption-resume models, and give new or improved lower bounds on the competitive ratio of deterministic online algorithms. In many cases the bounds are optimal when the job deadlines are tight. Our results show that the competitiveness varies linearly with the penalty factor.     

Lower bounds for polynomials with algebraic coefficients

We give a method, based on algebraic geometry, to show lower bounds for the complexity of polynomials with algebraic coefficients. Typical examples are polynomials with coefficients which are roots of unity, such as

$\text{Σ}\text{j=1}\text{d}\text{e}{}^{\mathrm{<mtext>2\pi i</mtext><mtext>i</mtext>}}\text{X}{}^{\mathrm{i}}$

and

$\text{Σ}\text{j=i}\text{d}\text{e}{}^{\mathrm{<mtext>2\pi i</mtext><mtext>pi</mtext>}}\text{X}{}^{\mathrm{j}}$

where p_j is the jth prime number.We apply the method also to systems of linear equations.     

Linear lower bounds on unbounded fan-in boolean circuits

A practical method for representing Turner Combinators is presented, which needs only O(n log n) space in the worst case for translating lambda expressions of length n. No precomputation is necessary in our translation, which should be contrasted with Burton's proposal. The runtime system can be implemented with virtually no essential change to Turner's reduction machine.     

Top-down lower bounds for depth-three circuits

We present a top-down lower bound method for depth-three , , ¬-circuits which is simpler than the previous methods and in some cases gives better lower bounds. In particular, we prove that depth-three , , ¬-circuits that compute parity (or majority) require size at least , respectively). This is the first simple proof of a strong lower bound by a top-down argument for non-monotone circuits.     

Symmetric approximation arguments for monotone lower bounds without sunflowers

We propose a symmetric version of Razborov's method of approximation to prove lower bounds for monotone circuit complexity. Traditionally, only DNF formulas have been used as approximators, whereas we use both CNF and DNF formulas. As a consequence we no longer need the Sun ower Lemma that has been essential for the method of approximation. The new approximation argument corresponds to Haken's recent method for proving lower bounds for monotone circuit complexity (counting bottlenecks) in a natural way.?We provide lower bounds for the BMS problem introduced by Haken, Andreev's polynomial problem, and for Clique. The exponential bounds obtained are the same as those previously best known for the respective problems. Received: July 16, 1996.     

Upper bounds for reversible circuits based on Young subgroups

We present tighter upper bounds on the number of Toffoli gates needed in reversible circuits. Both multiple controlled Toffoli gates and mixed polarity Toffoli gates have been considered for this purpose. The calculation of the bounds is based on a synthesis approach based on Young subgroups that results in circuits using a more generalized gate library. Starting from an upper bound for this library we derive new bounds which improve the existing bound by around 77%.     

Lower bounds on lengths of checking sequences

Lower bounds on the lengths of checking sequences constructed for testing from Finite State Machine-based specifications are established. These bounds consider the case where a distinguishing sequence is used in forming state recognition and transition verification subsequences and identify the effects of overlapping among such subsequences. Empirical results show that the existing methods for construction of checking sequences provide checking sequences with lengths that are within acceptable distance to these lower bounds.     

Lower bounds for sorting on mesh-connected architectures

Summary Lower bounds for sorting on mesh-connected arrays of processors are presented. For sorting N=n₁ n ₂...n _r elements on an n ₁×n₂×... ×n _r array 2(n ₁+...+n _r–1)+n _r data interchange steps are needed asymptotically. For two dimensions these bounds are asymptotically best possible provided that n ₁ and n ₂ are powers of 2. In this case the generalized s ²-way merge sort of Thompson and Kung turns out to be asymptotically optimal. The minimal asymptotic bound of 2 2N interchange steps can be obtained only by sorting algorithms suitable for N/2×2N meshes. For r3 dimensions an analysis of aspect-ratios also demonstrates that there exist mesh-connected architectures which are better suited for sorting than simple r-dimensional cubes.This work was done at the Institut für Informatik und Praktische Mathematik, University of Kiel, Federal Republic of Germany     

Lower bounds for convex programmes

An important aspect associated with the solution of any mathematical programme; is a sensitivity analysis applied to the various parameters of the programme. For the case of linear programmes, the notion of sensitivity analysis is fully developed. However, for non-linear programmes there is a scarcity of useful results. It is the purpose of this paper to establish lower bounds on the solution of a convex programme when the parameters of the programme are allowed to vary. Such bounds may be useful, for example, in establishing the minimal effects of inflation on optimal cost estimations.     

Lower bounds for context-free grammars

Ellul, Krawetz, Shallit and Wang prove an exponential lower bound on the size of any context-free grammar generating the language of all permutations over some alphabet. We generalize their method and obtain exponential lower bounds for many other languages, among them the set of all squares of given length, and the set of all words containing each symbol at most twice.     

Lower bounds for asynchronous consensus

Impossibility results and best-case lower bounds are proved for the number of message delays and the number of processes required to reach agreement in an asynchronous consensus algorithm that tolerates non-Byzantine failures. General algorithms exist that achieve these lower bounds in the normal case, when the response time of non-faulty processes and the transmission delay of messages they send to one another are bounded. Our theorems allow algorithms to do better in certain exceptional cases, and such algorithms are presented. Two of these exceptional algorithms may be of practical interest.     

Using an induction prover for verifying arithmetic circuits

We show that existing theorem proving technology can be used effectively for mechanically verifying a family of arithmetic circuits. A theorem prover implementing: (i) a decision procedure for quantifier-free Presburger arithmetic with uninterpreted function symbols; (ii) conditional rewriting; and (iii) heuristics for carefully selecting induction schemes from terminating recursive function definitions; and (iv) well integrated with backtracking, can automatically verify number-theoretic properties of parameterized and generic adders, multipliers and division circuits. This is illustrated using our theorem prover Rewrite Rule Laboratory (RRL). To our knowledge, this is the first such demonstration of the capabilities of a theorem prover mechanizing induction. The above features of RRL are briefly discussed using illustrations from the verification of adder, multiplier and division circuits. Extensions to the prover likely to make it even more effective for hardware verification are discussed. Furthermore, it is believed that these results are scalable, and the proposed approach is likely to be effective for other arithmetic circuits as well.