The Experts below are selected from a list of 21753 Experts worldwide ranked by ideXlab platform
Rocco A Servedio - One of the best experts on this subject based on the ideXlab platform.
-
addition is exponentially harder than counting for shallow Monotone circuits
Symposium on the Theory of Computing, 2017Co-Authors: Xi Chen, Igor Carboni Oliveira, Rocco A ServedioAbstract:Let Addk,N denote the Boolean Function which takes as input k strings of N bits each, representing k numbers a(1),…,a(k) in {0,1,…,2N-1}, and outputs 1 if and only if a(1) + … + a(k) ≥ 2N. Let MAJt,n denote a Monotone unweighted threshold gate, i.e., the Boolean Function which takes as input a single string x E {0,1}n and outputs 1 if and only if x1 + … + xn ≥ t. The Function Addk,N may be viewed as a Monotone Function that performs addition, and MAJt,n may be viewed as a Monotone gate that performs counting. We refer to circuits that are composed of MAJ gates as Monotone majority circuits. The main result of this paper is an exponential lower bound on the size of bounded-depth Monotone majority circuits that compute Addk,N. More precisely, we show that for any constant d ≥ 2, any depth-d Monotone majority circuit that computes Addd,N must have size 2Ω(N1/d). As Addk,N can be computed by a single Monotone weighted threshold gate (that uses exponentially large weights), our lower bound implies that constant-depth Monotone majority circuits require exponential size to simulate Monotone weighted threshold gates. This answers a question posed by Goldmann and Karpinski (STOC'93) and recently restated by Hastad (2010, 2014). We also show that our lower bound is essentially best possible, by constructing a depth-d, size 2O(N1/d) Monotone majority circuit for Addd,N. As a corollary of our lower bound, we significantly strengthen a classical theorem in circuit complexity due to Ajtai and Gurevich (JACM'87). They exhibited a Monotone Function that is in AC0 but requires super-polynomial size for any constant-depth Monotone circuit composed of unbounded fan-in AND and OR gates. We describe a Monotone Function that is in depth-3 AC0 but requires exponential size Monotone circuits of any constant depth, even if the circuits are composed of MAJ gates.
-
addition is exponentially harder than counting for shallow Monotone circuits
arXiv: Computational Complexity, 2015Co-Authors: Xi Chen, Igor Carboni Oliveira, Rocco A ServedioAbstract:Let $U_{k,N}$ denote the Boolean Function which takes as input $k$ strings of $N$ bits each, representing $k$ numbers $a^{(1)},\dots,a^{(k)}$ in $\{0,1,\dots,2^{N}-1\}$, and outputs 1 if and only if $a^{(1)} + \cdots + a^{(k)} \geq 2^N.$ Let THR$_{t,n}$ denote a Monotone unweighted threshold gate, i.e., the Boolean Function which takes as input a single string $x \in \{0,1\}^n$ and outputs $1$ if and only if $x_1 + \cdots + x_n \geq t$. We refer to circuits that are composed of THR gates as Monotone majority circuits. The main result of this paper is an exponential lower bound on the size of bounded-depth Monotone majority circuits that compute $U_{k,N}$. More precisely, we show that for any constant $d \geq 2$, any depth-$d$ Monotone majority circuit computing $U_{d,N}$ must have size $\smash{2^{\Omega(N^{1/d})}}$. Since $U_{k,N}$ can be computed by a single Monotone weighted threshold gate (that uses exponentially large weights), our lower bound implies that constant-depth Monotone majority circuits require exponential size to simulate Monotone weighted threshold gates. This answers a question posed by Goldmann and Karpinski (STOC'93) and recently restated by Hastad (2010, 2014). We also show that our lower bound is essentially best possible, by constructing a depth-$d$, size-$2^{O(N^{1/d})}$ Monotone majority circuit for $U_{d,N}$. As a corollary of our lower bound, we significantly strengthen a classical theorem in circuit complexity due to Ajtai and Gurevich (JACM'87). They exhibited a Monotone Function that is in AC$^0$ but requires super-polynomial size for any constant-depth Monotone circuit composed of unbounded fan-in AND and OR gates. We describe a Monotone Function that is in depth-$3$ AC$^0$ but requires exponential size Monotone circuits of any constant depth, even if the circuits are composed of THR gates.
W U Zhengpeng - One of the best experts on this subject based on the ideXlab platform.
-
study on the strengthening buffer operator based on the strictly Monotone Function
Journal of Communication University of China, 2013Co-Authors: W U ZhengpengAbstract:Based on the present theories of buffer operators,We propose in this paper several kinds of buffer operators based on the strictly Monotone Function,which all have the universality and practicability.we prove them to be strengthening buffer operators.The problem of some contradictions between qualitative analysis and quantiative forecast in pretreatment for vibration data sequences is resolved effectively.
-
analysis on the strengthening buffer operator based on the strictly Monotone Function
International Journal of Applied Physics and Mathematics, 2013Co-Authors: H U Xiaoli, W U ZhengpengAbstract:We construct four kinds of new strengthening buffer operators by using inverse Function theorem based on the axiom system of buffer operator. And demonstrate the GuanShi strengthening buffer operator which we compare with is a special case of our new operators. After studying the inner link and characteristics between the GuanShi and our new buffer operators, we greatly develop the application scope of strengthening buffer operator. This paper researches on buffer operators' construction with Functions and gives a new direction for construction of buffer operators.
Pawel Pasteczka - One of the best experts on this subject based on the ideXlab platform.
-
scales of quasi arithmetic means determined by an invariance property
Journal of Difference Equations and Applications, 2015Co-Authors: Pawel PasteczkaAbstract:It is well known that if {𝒫t}t∈R denotes the set of power means, then the mapping R∋t↦𝒫t(v)∈(min v,max v) is both 1 − 1 and onto for any non-constant sequence v=(v1,…,vn) of positive numbers. Briefly, the family of power means is a scale. If I is an interval and f:I→R is a continuous, strictly Monotone Function, then f−1((1/n)∑f(vi)) is a natural generalization of the power mean, so called quasi-arithmetic mean generated by f. A famous theorem says that the only homogeneous, quasi-arithmetic means are power means. We prove that, upon replacing the homogeneity requirement by an invariant-type axiom, one gets a family of quasi-arithmetic means building up a scale, too.
-
scales of quasi arithmetic means determined by invariance property
arXiv: Classical Analysis and ODEs, 2014Co-Authors: Pawel PasteczkaAbstract:It is well known that if $\mathcal{P}_t$ denotes a set of power means then the mapping $\mathbb{R} \ni t \mapsto \mathcal{P}_t(v) \in (\min v, \max v)$ is both 1-1 and onto for any non-constant sequence $v = (v_1,\dots,\,v_n)$ of positive numbers. Shortly: the family of power means is a scale. If $I$ is an interval and $f \colon I \rightarrow \mathbb{R}$ is a continuous, strictly Monotone Function then $f^{-1}(\tfrac{1}{n} \sum f(v_i))$ is a natural generalization of power means, so called quasi-arithmetic mean generated by $f$. A famous folk theorem says that the only homogeneous, quasi-a\-rith\-me\-tic means are power means. We prove that, upon replacing the homogeneity requirement by an invariant-type axiom, one gets a family of quasi-arithmetic means building up a scale, too.
Hiroshi Imai - One of the best experts on this subject based on the ideXlab platform.
-
obdds of a Monotone Function and of its prime implicants
International Symposium on Algorithms and Computation, 1996Co-Authors: Kazuyoshi Hayase, Hiroshi ImaiAbstract:Coudert made a breakthrough in the two-level logic minimization problem with Ordered Binary Decision Diagrams (OBDDs, in short) recently [3]. This paper discusses relationship between the two OBDDs of a Monotone Function and of its prime implicant set to clarify the complexity of this practically efficient method. We show that there exists a Monotone Function which has an O(n) size sum-of-products but cannot be represented by a polynomial size OBDD. In other words, we cannot obtain the OBDD of the prime implicant set of a Monotone Function in an output-size sensitive manner, once we have constructed the OBDD of that Function as in [3], in the worst case. A positive result is also given for a meaningful class of matroid Functions.
Kazuyoshi Hayase - One of the best experts on this subject based on the ideXlab platform.
-
On Relationship Between a Monotone Function and the Set of its Prime Implicants in OBDD Size
2016Co-Authors: Kazuyoshi HayaseAbstract:A state-of-the-art method for two-level logic minimization has been proposed by Coud-ert [3]. It uses OBDDs to represent not only Boolean Functions but also the sets of their prime implicants to overcome the explosion of the number of prime implicants [4]. This method has been shown to be quite efficient in practical use but its computational com-plexity has been scarcely clarified. In this paper, it is shown that there exists a Monotone Function that has an $O(n) $ size DNF and an exponential lower bound in OBDD size, which is a solution to open questions concerned with computational complexity in [3].
-
obdds of a Monotone Function and of its prime implicants
International Symposium on Algorithms and Computation, 1996Co-Authors: Kazuyoshi Hayase, Hiroshi ImaiAbstract:Coudert made a breakthrough in the two-level logic minimization problem with Ordered Binary Decision Diagrams (OBDDs, in short) recently [3]. This paper discusses relationship between the two OBDDs of a Monotone Function and of its prime implicant set to clarify the complexity of this practically efficient method. We show that there exists a Monotone Function which has an O(n) size sum-of-products but cannot be represented by a polynomial size OBDD. In other words, we cannot obtain the OBDD of the prime implicant set of a Monotone Function in an output-size sensitive manner, once we have constructed the OBDD of that Function as in [3], in the worst case. A positive result is also given for a meaningful class of matroid Functions.