scientific article
From MaRDI portal
Publication:3762226
zbMath0623.94018MaRDI QIDQ3762226
Publication date: 1987
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
computational complexityTuring machinesmonotone circuitsminimizationlower boundcircuit complexityparallel computationsbranching programsBoolean circuitsbounded-depth circuitsBoolean formulacomputation modelsparallel random access machinescomplexity of Boolean functionscombinational complexityplanar circuitssynchronous circuitsnonuniform complexity measures
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Boolean functions (06E30)
Related Items
A multiple-valued logic approach to the design and verification of hardware circuits, Bounded-width polynomial-size Boolean formulas compute exactly those functions in AC\(^ 0\), Approximation quality for sorting rules., Exact lower time bounds for computing Boolean functions on CREW PRAMs, Compact and efficiently verifiable models for concurrent systems, Functional inversion and communication complexity, A simple function that requires exponential size read-once branching programs, Monotone real circuits are more powerful than monotone Boolean circuits, Secret-sharing schemes for very dense graphs, Limiting negations in non-deterministic circuits, Some combinatorial-algebraic problems from complexity theory, Efficient data structures for Boolean functions, Polynomial-size binary decision diagrams for the exactly half-\(d\)-hyperclique problem reading each input bit twice, On the limits of gate elimination, 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, Coverage metrics for temporal logic model checking, A generalization of Spira's theorem and circuits with small segregators or separators, Delay optimization of linear depth Boolean circuits with prescribed input arrival times, Lower bounds for synchronous circuits and planar circuits, The power of nondeterminism in polynomial-size bounded-width branching programs, An information statistics approach to data stream and communication complexity, On Nečiporuk's theorem for branching programs, Reflections on ``Representations of sets of Boolean functions by commutative rings by Roman Smolensky, Functions computed by monotone Boolean formulas with no repeated variables, Construction of universal enumerators and formulas for threshold functions, Properties of symmetric Boolean functions, Efficient monotone circuits for threshold functions, Complexity of computation in finite fields, Efficient oblivious branching programs for threshold and mod functions, Neither reading few bits twice nor reading illegally helps much, On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability, Unsupervised learnable neuron model with nonlinear interaction on dendrites, A catalog of Boolean concepts., Forms of representation for simple games: sizes, conversions and equivalences, Size-energy tradeoffs for unate circuits computing symmetric Boolean functions, On the complexity of regular-grammars with integer attributes, Interior and exterior functions of positive Boolean functions., Submodular goal value of Boolean functions, On the nonnegative rank of distance matrices, The choice and agreement problems of a random function, Cyclic Boolean circuits, Lower bounds to the complexity of symmetric Boolean functions, Random Boolean formulas representing any Boolean function with asymptotically equal probability, Polynomial size \(\Omega\)-branching programs and their computational power, Comment on Kochol's paper ``Efficient monotone circuits for threshold functions, On the complexity of min-max sorting networks, On the readability of monotone Boolean formulae, Incremental branching programs, Very large cliques are easy to detect, 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, Length of polynomials over finite groups, On a small class of Boolean sums, A size-depth trade-off for the analog computation of Boolean functions, On the size of binary decision diagrams representing Boolean functions, Models and quantifier elimination for quantified Horn formulas, On the computation of Boolean functions by analog circuits of bounded fan-in, Lower bounds for monotone span programs, The complexity of computing symmetric functions using threshold circuits, Some computational problems in linear algebra as hard as matrix multiplication, General algorithm for two-dimensional totalistic cellular automata, One-way permutations, computational asymmetry and distortion., Reductions for monotone Boolean circuits, The optimal read-once branching program complexity for the direct storage access function, On convex complexity measures, Extensions to Barrington's M-program model, Minimization of ordered, symmetric half-products, Fundamentals of quantum information theory, Investigation of the global dynamics of cellular automata using Boolean derivatives, Playing monotone games to understand learning behaviors, Smallest formulas for the parity of \(2^k\) variables are essentially unique, First-order logics: some characterizations and closure properties, Systematic mistakes are likely in bounded optimal decision-making systems, Learning symmetric causal independence models, Rough mereology: A new paradigm for approximate reasoning, Planar acyclic computation, Double Horn functions, Approximability of minimum AND-circuits, On data structures and asymmetric communication complexity, Boolean circuit programming: A new paradigm to design parallel algorithms, Hierarchy theorems for \(k\)OBDDs and \(k\)IBDDs, On the bottleneck counting argument, An exponential lower bound for the size of monotone real circuits, Can large fanin circuits perform reliable computations in the presence of faults?, 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, Protecting data privacy in private information retrieval schemes, Convergence behavior and root signal sets of stack filters, Simplification in a satisfiability checker for VLSI applications, The conjunctive complexity of quadratic Boolean functions, Time-space tradeoffs for branching programs, The minimum equivalent DNF problem and shortest implicants, Theory revision with queries: Horn, read-once, and parity formulas, Compiling propositional weighted bases, Monotone simulations of non-monotone proofs., Proofs with monotone cuts, Pushing the limits of Valiant's universal circuits: simpler, tighter and more compact, A Generalization of Spira’s Theorem and Circuits with Small Segregators or Separators, On lower bounds for read-\(k\)-times branching programs, The delay of circuits whose inputs have specified arrival times, Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions, On the Complexity of the Hidden Weighted Bit Function for Various BDD Models, Communication Complexity and Lower Bounds on Multilective Computations, Decompositions of positive self-dual Boolean functions, Sensitivity vs. block sensitivity of Boolean functions, Fast Pseudorandom Functions Based on Expander Graphs, On the parallel complexity of linear groups, Sufficient conditions for the local repetition-freeness of minimal π-schemes realizing linear Boolean functions, \(\text{PI}_ k\) mass production and an optimal circuit for the Nečiporuk slice, Complexity of the Realization of a Linear Boolean Function in the Class of π-Schemes, Worst-case hardness suffices for derandomization: A new method for hardness-randomness trade-offs, Randomization and nondeterminism are comparable for ordered read-once branching programs, A Note on polynomial-size circuits with low resource-bounded Kolmogorov complexity, Extensions of an idea of McNaughton, Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines, Lower bounds for Boolean circuits of bounded negation width, Local bounds for the optimal information ratio of secret sharing schemes, FPGA implementation of a stochastic neural network for monotonic pseudo-Boolean optimization, ON THE CIRCUIT-SIZE OF INVERSES, Efficient and scalable universal circuits, A Well-Mixed Function with Circuit Complexity 5n ±o(n): Tightness of the Lachish-Raz-Type Bounds, Symmetry structure in discrete models of biochemical systems: natural subsystems and the weak control hierarchy in a new model of computation driven by interactions, How Do Read-Once Formulae Shrink?, Smallest Formulas for Parity of 2 k Variables Are Essentially Unique, On \(\epsilon\)-sensitive monotone computations, The size and depth of layered Boolean circuits, Privacy in non-private environments, A well-mixed function with circuit complexity \(5n\): tightness of the Lachish-Raz-type bounds, Feebly secure cryptographic primitives, Circuit complexity of linear functions: gate elimination and feeble security, FACTORIZATIONS OF THE THOMPSON–HIGMAN GROUPS, AND CIRCUIT COMPLEXITY, Exact OBDD bounds for some fundamental functions, A Theoretical and Numerical Analysis of the Worst-Case Size of Reduced Ordered Binary Decision Diagrams, 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, On the number of zero-patterns of a sequence of polynomials, Bayesian network modelling through qualitative patterns, First order LUB approximations: characterization and algorithms, \(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)\)., Approximate bit dependency analysis to identify program synthesis problems as infeasible, Gate Elimination for Linear Functions and New Feebly Secure Constructions, Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth, Dominance-based rough set approach to incomplete ordered information systems, Asymptotical behaviour of some non-uniform measures, Using the renormalization group to classify Boolean functions, THE ${\mathcal R}$- AND ${\mathcal L}$-ORDERS OF THE THOMPSON–HIGMAN MONOID Mk, 1 AND THEIR COMPLEXITY, Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication, Division in logspace-uniformNC1, Computer science and decision theory, The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis, Applying approximate counting for computing the frequency moments of long data streams, Unnamed Item, Competitive Boolean function evaluation: beyond monotonicity, and the symmetric case, Computing in fault tolerant broadcast networks and noisy decision trees, On the complexity of Fibonacci coding, Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication, Building Bridges Between Sets of Partial Orders, Formula complexity of a linear function in a \(k\)-ary basis, Construction of Lightweight S-Boxes Using Feistel and MISTY Structures, Algebraic cryptography: new constructions and their security against provable break, On the complexity of the clone membership problem, Computing the number of affine equivalent classes on \(\mathcal{R}(s,n)/\mathcal{R}(k,n)\), Unnamed Item, Interpolation of the discrete logarithm in \(\mathbb{F}_{q}\) by Boolean functions and by polynomials in several variables modulo a divisor of \(q-1\)., The word problem of the Brin-Thompson group is \textsf{coNP}-complete, A Feebly Secure Trapdoor Function, Reconstruction of cooperative information systems under cost constraints: A rough set approach, Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs, On the complexity of monotone circuits for threshold symmetric Boolean functions, On Negations in Boolean Networks, Minimal polynomials for the conjunction of functions on disjoint variables can be very simple, Coded Circuit for Trusted Computing: Towards Dynamic Integrity Measurement, Constructing depth-optimum circuits for adders and \textsc{And}-\textsc{Or} paths, On the relative succinctness of sentential decision diagrams, On the influence of the variable ordering for algorithmic learning using OBDDs, On the complexity of planar Boolean circuits, On the number of ANDs versus the number of ORs in monotone Boolean circuits, Threshold Circuits for Iterated Matrix Product and Powering, The complexity of the standard multiplexer function in a class of switching circuits, On converting CNF to DNF, 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, Mining circuit lower bound proofs for meta-algorithms, On the approximability of the largest sphere rule ensemble classification problem, Unnamed Item, On the Readability of Monotone Boolean Formulae, On the performance of networks with multiple busses, Synthesis for testability: Binary Decision Diagrams, Neural networks and complexity theory, Succinct attribute-based signatures for bounded-size circuits by combining algebraic and arithmetic proofs, The size of reduced OBDDs and optimal read-once branching programs for almost all Boolean functions, Paradigms for Unconditional Pseudorandom Generators, Time-release cryptography from minimal circuit assumptions, Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory, Unnamed Item, On the computational power of discrete Hopfield nets, ON THE MEANING OF WORKS BY V. M. KHRAPCHENKO, Finding Effective SAT Partitionings Via Black-Box Optimization, OKFDDs versus OBDDs and OFDDs, OR-Toffoli and OR-Peres Reversible Gates, Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems, THE GROUPS OF RICHARD THOMPSON AND COMPLEXITY, On a class of cell circuits, New lower bounds and hierarchy results for restricted branching programs, Natural proofs, Monotone term decision lists, Pseudorandom generators without the XOR lemma, Unnamed Item, A lower bound on CNF encodings of the at-most-one constraint, Branching program size is almost linear in formula size, On the power of Las Vegas II: Two-way finite automata, Exact OBDD Bounds for Some Fundamental Functions, Extracting all the randomness and reducing the error in Trevisan's extractors, A generalization of the algorithm of Heidtmann to non-monotone formulas, The Decomposition Tree for analyses of Boolean functions, A nonlinear lower bound on the practical combinational complexity, CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS, Unnamed Item, Lower Bounds for DeMorgan Circuits of Bounded Negation Width, Hardness magnification near state-of-the-art lower bounds, Notes on Hazard-Free Circuits, Unnamed Item, Unnamed Item, On the relation between BDDs and FDDs, Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses, Unnamed Item, Secret sharing schemes for ports of matroids of rank 3
