scientific article; zbMATH DE number 3607492
From MaRDI portal
Publication:4172915
Cited in
(60)- Nearly optimal hierarchies for network and formula size
- Decomposition of graphs and monotone formula size of homogeneous functions
- One-way functions and circuit complexity
- Limits on the power of concurrent-write parallel machines
- On characterizations of the class PSPACE/poly
- Random problems
- Feasible arithmetic computations: Valiant's hypothesis
- Construction of universal enumerators and formulas for threshold functions
- Size-depth tradeoff in non-monotone Boolean formulae
- A 3n-lower bound on the network complexity of Boolean functions
- An improved algorithm for finding saddlepoints of two-person zero-sum games
- Improved processor bounds for combinatorial problems in RNC
- Algebraic nonlinearity and its applications to cryptography
- An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph
- Asymptotics of growth for non-monotone complexity of multi-valued logic function systems
- The minimum number of negations in circuits for systems of multi-valued functions
- On the depth of \(k\)-valued logic functions over arbitrary bases
- On Bellman's and Knuth's problems and their generalizations
- Feebly secure cryptographic primitives
- Circuit complexity of linear functions: gate elimination and feeble security
- Space-bounded quantum complexity
- Exact value of the nonmonotone complexity of Boolean functions
- Relation between two measures of the computation complexity for systems of monomials
- Depth of functions of the \(k\)-valued logic in infinite bases
- Gate elimination for linear functions and new feebly secure constructions
- scientific article; zbMATH DE number 3644481 (Why is no real title available?)
- Parity, circuits, and the polynomial-time hierarchy
- Optimal interconnection in digital systems satisfying concurrency constraints
- A Feebly Secure Trapdoor Function
- A generalization of Spira's theorem and circuits with small segregators or separators
- Depth of Boolean functions realized by circuits over an arbitrary infinite basis
- Parallelizable algebras
- On the parallel complexity of linear groups
- ON THE CONNECTION BETWEEN THE COMPLEXITY AND CREDIBILITY OF INFERRED MODELS
- Prolegomenon to the relation between social theory and method*
- On the complexity of multivalued logic functions over some infinite basis
- Nonuniform complexity classes specified by lower and upper bounds
- A lower bound for the complexity of Craig's interpolants in sentential logic
- On the complexity of unitary transformations
- Simulation of circuits of functional elements by the universal Turing machine
- Two-way automata and length-preserving homomorphisms
- The complexity of error-correcting codes
- ON THE COMPLEXITY OF CIRCUITS IN BASES CONTAINING MONOTONE ELEMENTS WITH ZERO WEIGHTS
- IMPROVEMENT OF THE LOWER BOUND FOR THE COMPLEXITY OF EXPONENTIATION
- On the meaning of works by V. M. Khrapchenko
- On the complexity of computation of a pair of monomials in two variables
- Constructive universal algebra: An introduction
- A curious new result in switching theory
- Improvement of nonmonotone complexity estimates of k-valued logic functions
- On the size of binary decision diagrams representing Boolean functions
- Modal logic is more succinct iff bi-implication is available in some form
- Boolean basis, formula size, and number of modal operators
- Range avoidance for low-depth circuits and connections to pseudorandomness
- The exact circuit complexity of Boolean functions in an infinite basis
- Towards a complexity theory of synchronous parallel computation
- The 1982 ACM Turing Award lecture. An overview of computational complexity
- Secret sharing, slice formulas, and monotone real circuits
- Non-uniform automata over groups
- Probabilistic satisfiability: algorithms with the presence and absence of a phase transition
- Polynomial size \(\Omega\)-branching programs and their computational power
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4172915)
