Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
From MaRDI portal
Publication:1095871
DOI10.1007/BF01137685zbMath0632.94030OpenAlexW2009994177WikidataQ29042011 ScholiaQ29042011MaRDI QIDQ1095871
Publication date: 1987
Published in: Mathematical Notes (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01137685
Related Items (more than 100 items found - showing only first 100)
Hardness Characterisations and Size-width Lower Bounds for QBF Resolution ⋮ Immunity and Simplicity for Exact Counting and Other Counting Classes ⋮ Solution Sets for Equations over Free Groups are EDT0L Languages ⋮ A Hierarchy Theorem for Interactive Proofs of Proximity ⋮ On small depth threshold circuits ⋮ Approximate Degree in Classical and Quantum Computing ⋮ Faster All-Pairs Shortest Paths via Circuit Complexity ⋮ Nonuniform ACC Circuit Lower Bounds ⋮ Randomized feasible interpolation and monotone circuits with a local oracle ⋮ Skew Circuits of Small Width ⋮ Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization ⋮ Characterizing Propositional Proofs as Noncommutative Formulas ⋮ Collapsing modular counting in bounded arithmetic and constant depth propositional proofs ⋮ The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials ⋮ Separating counting communication complexity classes ⋮ Constructive Relationships Between Algebraic Thickness and Normality ⋮ On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions ⋮ Worst-Case to Average-Case Reductions for Subclasses of P ⋮ Constant-Round Interactive Proof Systems for AC0[2 and NC1] ⋮ On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1 ⋮ Unnamed Item ⋮ On the probabilistic degree of OR over the reals ⋮ Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle? ⋮ A note on uniform circuit lower bounds for the counting hierarchy (extended abstract) ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The work of Mark Braverman ⋮ Communication and information complexity ⋮ Monomial Boolean functions with large high-order nonlinearities ⋮ On the correlation of symmetric functions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The Computational Power of Depth Five Arithmetic Circuits ⋮ On polynomial approximations to AC ⋮ Agnostic Learning from Tolerant Natural Proofs ⋮ Depth Reduction for Composites ⋮ Learning Read-Constant Polynomials of Constant Degree Modulo Composites ⋮ NEXP Does Not Have Non-uniform Quasipolynomial-Size ACC Circuits of o(loglogn) Depth ⋮ Degree lower bounds of tower-type for approximating formulas with parity quantifiers ⋮ Circuit complexity of regular languages ⋮ Natural proofs ⋮ An exact characterization of symmetric functions in \(qAC^{0}[2\)] ⋮ A lower bound for primality ⋮ Fine-grained secure attribute-based encryption ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the degree of univariate polynomials over the integers ⋮ New bounds for energy complexity of Boolean functions ⋮ Unnamed Item ⋮ On the modulo degree complexity of Boolean functions ⋮ On the Probabilistic Degrees of Symmetric Boolean Functions ⋮ Fine-grained cryptography revisited ⋮ Unnamed Item ⋮ Propositional proof complexity ⋮ Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates ⋮ On systems of equations over free partially commutative groups ⋮ On the correlation of symmetric functions ⋮ Ehrenfeucht-Fraïssé Games on Random Structures ⋮ Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates ⋮ Expander-Based Cryptography Meets Natural Proofs ⋮ Depth Reduction for Circuits with a Single Layer of Modular Counting Gates ⋮ Parity helps to compute majority ⋮ On the Symmetries of and Equivalence Test for Design Polynomials. ⋮ Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs ⋮ Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits ⋮ Unnamed Item ⋮ The Power of Programs over Monoids in DA ⋮ Unnamed Item ⋮ Unnamed Item ⋮ From Circuit Complexity to Faster All-Pairs Shortest Paths ⋮ Pseudorandom Functions: Three Decades Later ⋮ Reed-Muller Codes ⋮ Asymptotic invariants, complexity of groups and related problems ⋮ Affine projections of symmetric polynomials. ⋮ Exact lower time bounds for computing Boolean functions on CREW PRAMs ⋮ The expressive power of voting polynomials ⋮ Expander-based cryptography meets natural proofs ⋮ Correlation lower bounds from correlation upper bounds ⋮ The correlation between parity and quadratic polynomials mod \(3\) ⋮ Threshold circuits of bounded depth ⋮ A lower bound for depth-3 circuits with MOD \(m\) gates ⋮ Fine-grained secure computation ⋮ Exploring crypto dark matter: new simple PRF candidates and their applications ⋮ Fine-grained secure attribute-based encryption ⋮ Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2\)] ⋮ On the degree of Boolean functions as real polynomials ⋮ On ACC ⋮ Representing Boolean functions as polynomials modulo composite numbers ⋮ Circuits constructed with MOD\(_ q\) gates cannot compute ``and in sublinear size ⋮ A note on a theorem of Barrington, Straubing and Thérien ⋮ Circuit lower bounds from learning-theoretic approaches ⋮ A note on some languages in uniform \(ACC^ 0\) ⋮ On uniformity within \(NC^ 1\) ⋮ Energy complexity of satisfying assignments in monotone circuits: on the complexity of computing the best case ⋮ Implicit function theorem over free groups.
Cites Work
This page was built for publication: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
