On the power of small-depth threshold circuits

We investigate the power of threshold circuits of small depth. In particular, we give functions that require exponential size unweighted threshold circuits of depth 3 when we restrict the bottom fanin. We also prove that there are monotone functionsf _k that can be computed in depthk and linear size , -circuits but require exponential size to compute by a depthk–1 monotone weighted threshold circuit.     

Computing Boolean functions by polynomials and threshold circuits

We investigate the computational power of threshold—AND circuits versus threshold—XOR circuits. In contrast to the observation that small weight threshold—AND circuits can be simulated by small weight threshold—XOR circuit, we present a function with small size unbounded weight threshold—AND circuits for which all threshold—XOR circuits have exponentially many nodes. This answers the basic question of separating subsets of the hypercube by hypersurfaces induced by sparse real polynomials. We prove our main result by a new lower bound argument for threshold circuits. Finally we show that unbounded weight threshold gates cannot simulate alternation: There are -functions which need exponential size threshold—AND circuits. Received: August 8, 1996.     

Easy lower bound for a strange computational model

The paper gives a new proof of the well-known lower bound (n logn) for the algebraic complexity of the functionx ₁ ⁿ x ₂ ⁿ +...+x _n ⁿ (if the characteristic of the ground field does not dividen). As a tool, the proof uses a computational model that counts only duplicators.     

Evaluating spectral norms for constant depth circuits with symmetric gates

The Fourier spectrum and its norms are given as explicit arithmetic expressions and evaluated, for Boolean functions computed by classes of constant depth, read-once circuits consisting of an arbitrary set of symmetric gates. Previous results of this nature estimate the spectralL ₁ norm of functions computed by certain types of decision trees [20], [7], and in some cases, give randomizedprocedures that evaluate the spectrum by clever rounding [20]. One corollary of our results provides a large class ofAC ⁰ functions whose spectralL ₁ norm is exponential, thus generalizing the single example of such a function given in [9]. This shows that almost every read-onceAC ⁰ function does not belong in the classPL ₁ of functions with polynomially bounded spectral norms.Implications of our results and technique are discussed, for estimating the spectral norms ofany function in a constant depth circuit class, using the coding theoretic concept of weight distributions. Evaluating the spectral norms for any such function reduces to estimating certain non-trivial weight distributions of simple, linear codes.     

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.     

Exponential lower bounds for depth three Boolean circuits

We consider the class of unbounded fan-in depth three Boolean circuits, for which the bottom fan-in is limited by k and the top gate is an OR. It is known that the smallest such circuit computing the parity function has gates (for k = O(n ^1/2)) for some , and this was the best lower bound known for explicit (P-time computable) functions. In this paper, for k = 2, we exhibit functions in uniform NC ¹ that require size depth 3 circuits. The main tool is a theorem that shows that any circuit on n variables that accepts a inputs and has size s must be constant on a projection (subset defined by equations of the form x _i = 0, x _i = 1, x _i = x _j or x _i = ) of dimension at least log(a/s)log n. Received: April 1, 1997.     

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     

Malign Distributions for Average Case Circuit Complexity

In contrast to machine models like Turing machines or random access machines, circuits are a static computational model. The internal information flow of a computation is fixed in advance, independent of the actual input. Therefore, size and depth are natural and simple measures for circuits and provide a worst-case analysis. We consider a new model in which an internal gate is evaluated as soon as its result has been determined by a partial assignment of its inputs. This way, a dynamic notion of delay is obtained which gives rise to an average case measure for the time complexity of circuits. In a previous paper we have obtained tight upper and lower bounds for the average case complexity of several basic Boolean functions. This paper examines the asymptotic average case complexity for the set of alln-ary Boolean functions. In contrast to worst case analysis a simple counting argument does not work. We prove that with respect to the uniform probability distribution almost all Boolean functions require at leastn−log n−log log nexpected time. On the other hand, there is a significantly large subset of functions that can be computed with a constant average delay. Finally, for an arbitrary Boolean function we compare its worst case and average case complexity. It is shown that for each function that requires circuit depthd, i.e. of worst-case complexityd, the expected time complexity will be at leastd−log n−log dwith respect to an explicitly defined probability distribution. In addition, a nontrivial upper bound on the complexity of such a distribution will be obtained.     

On lower bounds for the complexity of polynomials and their multiples

We prove a theorem giving arbitrarily long explicit sequences of algebraic numbers such that any nonzero polynomial f(X) satisfying has nonscalar complexity for some positive constant C independent of s. A similar result is shown for rapidly growing rational sequences. Received: April 6 1999.     

Communication complexity towards lower bounds on circuit depth

Karchmer, Raz, and Wigderson (1995) discuss the circuit depth complexity of n-bit Boolean functions constructed by composing up to d = log n/log log n levels of k = log n-bit Boolean functions. Any such function is in AC¹ . They conjecture that circuit depth is additive under composition, which would imply that any (bounded fan-in) circuit for this problem requires depth. This would separate AC¹ from NC¹. They recommend using the communication game characterization of circuit depth. In order to develop techniques for using communication complexity to prove circuit depth lower bounds, they suggest an intermediate communication complexity problem which they call the Universal Composition Relation. We give an almost optimal lower bound of dk—O(d ²(k log k)^1/2) for this problem. In addition, we present a proof, directly in terms of communication complexity, that there is a function on k bits requiring circuit depth. Although this fact can be easily established using a counting argument, we hope that the ideas in our proof will be incorporated more easily into subsequent arguments which use communication complexity to prove circuit depth bounds. Received: July 30, 1999.     

A nonlinear lower bound for constant depth arithmetical circuits via the discrete uncertainty principle

We prove a superlinear lower bound on the size of a bounded depth bilinear arithmetical circuit computing cyclic convolution. Our proof uses the strengthening of the Donoho–Stark uncertainty principle [D.L. Donoho, P.B. Stark, Uncertainty principles and signal recovery, SIAM Journal of Applied Mathematics 49 (1989) 906–931] given by Tao [T. Tao, An uncertainty principle for cyclic groups of prime order, Mathematical Research Letters 12 (2005) 121–127], and a combinatorial lemma by Raz and Shpilka [R. Raz, A. Shpilka, Lower bounds for matrix product, in arbitrary circuits with bounded gates, SIAM Journal of Computing 32 (2003) 488–513]. This combination and an observation on ranks of circulant matrices, which we use to give a much shorter proof of the Donoho–Stark principle, may have other applications.     

Selection problems viaM-ary queries

It is well known that, for fixedk, to find thek-th largest ofn elementsn+(k?1)log₂ n+Θ(1) comparisons are necessary and sufficient. But do the same bounds apply if we use a different type of query? We show that the arity of the queries is relevant. In particular, we present upper and lower bounds for finding the maximum using 3-ary or 4-ary Boolean (YES/NO answers) queries. We also study general (e.g.,max, sort) 3-ary queries, and show bounds for finding the maximum and the second largest. For sort queries we show matching upper and lower bounds.     

Pseudorandom generators and learning algorithms forAC 0

For anyAC ⁰ functionf ofn bits, there is a polynomialp such that anyp(logn)-wise decomposable distribution foolsf. In other words,f cannot distinguish between the pseudorandom strings in the distribution and truly random strings. The polynomialp depends only on the size and depth of the circuit computingf.This subsumes and extends the class of distributions that were previously known to foolAC ⁰ functions, and partially answers an open question posed by Linial and Nisan in 1990, as to whether every polylog-wise independent distribution foolsAC ⁰ functions or not.Each polylog-wise decomposable distribution serves as a fixed training set of examples for learning (approximately interpolating) allAC ⁰ functions computed by circuits of some fixed depth and size. Furthermore, small, natural distributions (training sets) exist that yield deterministic learning algorithms that run in timeO (2^polylogn ) forAC ⁰ functions, where the degree of the polylog depends on the size and depth of the circuit to be learnt.This improves on the randomized algorithms with the same time complexity given, for example, by Linialet al. in 1989, where the examples for the training set are picked randomly from specific distributions.     

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.     

Complex polynomials and circuit lower bounds for modular counting

We study the power of constant-depth circuits containing negation gates, unbounded fan-in AND and OR gates, and a small number of MAJORITY gates. It is easy to show that a depth 2 circuit of sizeO(n) (wheren is the number of inputs) containingO(n) MAJORITY gates can determine whether the sum of the input bits is divisible byk, for any fixedk>1, whereas it is known that this requires exponentialsize circuits if we have no MAJORITY gates. Our main result is that a constant-depth circuit of size containingn ^o(1) MAJORITY gates cannot determine if the sum of the input bits is divisible byk; moreover, such a circuit must give the wrong answer on a constant fraction of the inputs. This result was previously known only fork=2. We prove this by obtaining an approximate representation of the behavior of constant-depth circuits by multivariate complex polynomials.     

High-performance low-leakage regions of nano-scaled CMOS digital gates under variations of threshold voltage and mobility

We propose a modeling methodology for both leakage power consumption and delay of basic CMOS digital gates in the presence of threshold voltage and mobility variations. The key parameters in determining the leakage and delay are OFF and ON currents, respectively, which are both affected by the variation of the threshold voltage. Additionally, the current is a strong function of mobility. The proposed methodology relies on a proper modeling of the threshold voltage and mobility variations, which may be induced by any source. Using this model, in the plane of threshold voltage and mobility, we determine regions for different combinations of performance (speed) and leakage. Based on these regions, we discuss the trade-off between leakage and delay where the leakage-delay-product is the optimization objective. To assess the accuracy of the proposed model, we compare its predictions with those of HSPICE simulations for both basic digital gates and ISCAS85 benchmark circuits in 45-, 65-, and 90-nm technologies.     

Circuit Complexity of Regular Languages

We survey the current state of knowledge on the circuit complexity of regular languages and we prove that regular languages that are in AC⁰ and ACC⁰ are all computable by almost linear size circuits, extending the result of Chandra et al. (J. Comput. Syst. Sci. 30:222–234, 1985). As a consequence we obtain that in order to separate ACC⁰ from NC¹ it suffices to prove for some ε>0 an Ω(n ^1+ε ) lower bound on the size of ACC⁰ circuits computing certain NC¹-complete functions. Partially supported by grant GA ČR 201/07/P276, project No. 1M0021620808 of MŠMT ČR and Institutional Research Plan No. AV0Z10190503.     

有效的权重不同参与者之间门限多重秘密共享

秘密共享方案中,一般研究Shamir门限秘密共享方案,该方案是基于多项式插值的门限秘密共享方案.基于中国剩余定理,对权重不同参与者之间秘密共享方案进行研究.同时,考虑了多重秘密共享,即通过一次秘密共享过程就可实现对任意个秘密的共享,而参与者秘密份额的长度仅为一个秘密的长度.最后基于中国剩余定理给出有效的权重不同参与者之间门限多重秘密共享方案.