scientific article; zbMATH DE number 4012495

MaRDI QIDQ3762226zbMATH OpenFDO

Authors Ingo Wegener

Publication date 1987

Recommendations

Computational complexity of Boolean functions
scientific article; zbMATH DE number 194333
The complexity of Boolean functions in different characteristics
scientific article; zbMATH DE number 726918
On complexity of a particular Boolean functions class
scientific article; zbMATH DE number 4108153
Boolean function complexity. Advances and frontiers.
On the multiplicative complexity of Boolean functions
On the complexity of restrictions of Boolean functions
Multiplicative complexity of some Boolean functions

Cited in

(only showing first 100 items - show all)

Learning symmetric causal independence models
Approximability of minimum AND-circuits
Boolean circuit programming: A new paradigm to design parallel algorithms
On the relation between fuzzy max-Archimedean t-norm relational equations and the covering problem
Reviewing bounds on the circuit size of the hardest functions
On the construction of parallel computers from various basis of Boolean functions
Lower bounds for synchronous circuits and planar circuits
The power of nondeterminism in polynomial-size bounded-width branching programs
On Nečiporuk's theorem for branching programs
Functions computed by monotone Boolean formulas with no repeated variables
Construction of universal enumerators and formulas for threshold functions
Efficient monotone circuits for threshold functions
Neither reading few bits twice nor reading illegally helps much
Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
The complexity of computing the number of strings of given length in context-free languages
The complexity of the parity function in unbounded fan-in, unbounded depth circuits
Nonlinear lower bounds on the number of processors of circuits with sublinear separators
The complexity of computing symmetric functions using threshold circuits
General algorithm for two-dimensional totalistic cellular automata
Extensions to Barrington's M-program model
Double Horn functions
On data structures and asymmetric communication complexity
Hierarchy theorems for kOBDDs and kIBDDs
An exponential lower bound for the size of monotone real circuits
Convergence behavior and root signal sets of stack filters
Simplification in a satisfiability checker for VLSI applications
Bounded-width polynomial-size Boolean formulas compute exactly those functions in AC\(^ 0\)
Exact lower time bounds for computing Boolean functions on CREW PRAMs
Functional inversion and communication complexity
Some combinatorial-algebraic problems from complexity theory
Efficient data structures for Boolean functions
On the degree of Boolean functions as real polynomials
On almost bad Boolean bases
On the complexity of encoding in analog circuits
Complexity of Boolean functions over bases with unbounded fan-in gates
Better lower bounds for monotone threshold formulas
Reflections on ``Representations of sets of Boolean functions by commutative rings by Roman Smolensky
Efficient oblivious branching programs for threshold and mod functions
A catalog of Boolean concepts.
Interior and exterior functions of positive Boolean functions.
On the bottleneck counting argument
Can large fanin circuits perform reliable computations in the presence of faults?
Protecting data privacy in private information retrieval schemes
Time-space tradeoffs for branching programs
The minimum equivalent DNF problem and shortest implicants
On the complexity of balanced Boolean functions
Approximation quality for sorting rules.
Compact and efficiently verifiable models for concurrent systems
On the limits of gate elimination
Properties of symmetric Boolean functions
On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability
Submodular goal value of Boolean functions
The choice and agreement problems of a random function
Minimization of ordered, symmetric half-products
Systematic mistakes are likely in bounded optimal decision-making systems
Rough mereology: A new paradigm for approximate reasoning
Interpolation of the discrete logarithm in \(\mathbb{F}_{q}\) by Boolean functions and by polynomials in several variables modulo a divisor of \(q-1\).
Reconstruction of cooperative information systems under cost constraints: A rough set approach
Minimal polynomials for the conjunction of functions on disjoint variables can be very simple
On the complexity of planar Boolean circuits
On the number of ANDs versus the number of ORs in monotone Boolean circuits
Recognition and dualization of disguised bidual Horn functions.
Topics in the theory of DNA computing.
Complexity measures and decision tree complexity: a survey.
Malign distributions for average case circuit complexity.
Hilbert function and complexity lower bounds for symmetric Boolean functions
Circuit and decision tree complexity of some number theoretic problems
Computing a context-free grammar-generating series
On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
Mathematical models of quantum computation
Monotone simulations of non-monotone proofs.
Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions
Decompositions of positive self-dual Boolean functions
Sensitivity vs. block sensitivity of Boolean functions
\(\text{PI}_ k\) mass production and an optimal circuit for the Nečiporuk slice
FPGA implementation of a stochastic neural network for monotonic pseudo-Boolean optimization
The size and depth of layered Boolean circuits
Complexity of Boolean functions in intelligent systems for synthesis of digital integrated circuits
Feebly secure cryptographic primitives
Circuit complexity of linear functions: gate elimination and feeble security
Exact OBDD bounds for some fundamental functions
Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs
Bidual Horn functions and extensions
Minimum self-dual decompositions of positive dual-minor Boolean functions
\(P\)-sufficient statistics for PAC learning \(k\)-term-DNF formulas through enumeration
Identification of partial disjunction, parity, and threshold functions
On the multiplicative complexity of Boolean functions over the basis (\(\land,\oplus,1)\).
Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth
Dominance-based rough set approach to incomplete ordered information systems
Formula complexity of a linear function in a \(k\)-ary basis
Critical properties and complexity measures of read-once Boolean functions
On the complexity of the clone membership problem
Computing the number of affine equivalent classes on \(\mathcal{R}(s,n)/\mathcal{R}(k,n)\)
On the complexity of monotone circuits for threshold symmetric Boolean functions
Constructing depth-optimum circuits for adders and \textsc{And}-\textsc{Or} paths
The complexity of the standard multiplexer function in a class of switching circuits
Pushing the limits of Valiant's universal circuits: simpler, tighter and more compact
Efficient and scalable universal circuits
On \(\epsilon\)-sensitive monotone computations
Approximate bit dependency analysis to identify program synthesis problems as infeasible

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 Q3762226)