scientific article; zbMATH DE number 1142303

Publication date: 4 May 1998

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

lower bounds circuit complexity gate types

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Number-theoretic algorithms; complexity (11Y16)

Related Items

Directed monotone contact networks for threshold functions, Complexity models for incremental computation, On learning monotone DNF under product distributions, Monotone real circuits are more powerful than monotone Boolean circuits, The average sensitivity of bounded-depth circuits, Lower bounds for monotone real circuit depth and formula size and tree-like cutting planes, \(\Sigma\Pi\Sigma\) threshold formulas, Parameterized Parallel Computing and First-Order Logic, On ACC, On almost bad Boolean bases, Evaluating spectral norms for constant depth circuits with symmetric gates, Depth of Boolean functions realized by circuits over an arbitrary infinite basis, Query languages for bags and aggregate functions, A query language for NC, Pseudorandom generators and learning algorithms for \(\mathrm{AC}^ 0\), On the complexity of entailment in propositional multivalued logics, Parameterized circuit complexity and the \(W\) hierarchy, ERCW PRAMs and optical communication, The complexity of graph connectivity, Gap-languages and log-time complexity classes, Optimal bounds for the approximation of Boolean functions and some applications, On log-time alternating Turing machines of alternation depth k, On the complexity of second-best abductive explanations, Unnamed Item, On derandomization and average-case complexity of monotone functions, Circuit complexity of linear functions: gate elimination and feeble security, The strongest model of computation obeying 0-1 Principles, Some connections between bounded query classes and non-uniform complexity., Unnamed Item, Partition-based logical reasoning for first-order and propositional theories, The size of a revised knowledge base, Negation-limited circuit complexity of symmetric functions, Computing threshold functions by depth-3 threshold circuits with smaller thresholds of their gates, On input read-modes of alternating Turing machines, Interpolants, cut elimination and flow graphs for the propositional calculus, On the computation of Boolean functions by analog circuits of bounded fan-in, Partial-order Boolean games: informational independence in a logic-based model of strategic interaction, Improvements on Khrapchenko's theorem, Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy, Matching theory -- a sampler: From Dénes König to the present, The communication complexity of addition, Separating complexity classes related to \(\Omega\)-decision trees, Using the renormalization group to classify Boolean functions, The computational complexity of universal hashing, On the complexity of cutting-plane proofs using split cuts, Feasibly constructive proofs of succinct weak circuit lower bounds, Smallest formulas for the parity of \(2^k\) variables are essentially unique, On BPP versus \(NP\cup coNP\) for ordered read-once branching programs, Boolean expression diagrams, Pac-learning non-recursive Prolog clauses, Pac-learning non-recursive Prolog clauses, Linear-size log-depth negation-limited inverter for \(k\)-tonic binary sequences, An extension of Khrapchenko's theorem, Negation-limited complexity of parity and inverters, Hardness magnification near state-of-the-art lower bounds, Relating polynomial time to constant depth, Reductions in circuit complexity: An isomorphism theorem and a gap theorem, Time-space tradeoffs for satisfiability, Positive versions of polynomial time, An exponential lower bound for the size of monotone real circuits, The complexity of belief update, No feasible monotone interpolation for simple combinatorial reasoning, Can large fanin circuits perform reliable computations in the presence of faults?, Characterizing linear size circuits in terms of privacy, Circuit and decision tree complexity of some number theoretic problems, Preprocessing of intractable problems, The relative power of logspace and polynomial time reductions, Shallow circuits and concise formulae for multiple addition and multiplication, A feasible interpolation for random resolution, On the negation-limited circuit complexity of merging, Which problems have strongly exponential complexity?, Mining circuit lower bound proofs for meta-algorithms, The expressiveness of DAC