scientific article; zbMATH DE number 1161568

Publication date: 10 June 1998

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

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Parallel algorithms in computer science (68W10) Analytic circuit theory (94C05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (90)

On symmetric circuits and fixed-point logics ⋮ Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata ⋮ Local Reductions ⋮ Dependence logic with a majority quantifier ⋮ Circuit lower bounds from learning-theoretic approaches ⋮ On the complexity of the string generation problem ⋮ The Complexity of Satisfiability for Fragments of Hybrid Logic—Part I ⋮ Collapse of the hierarchy of constant-depth exact quantum circuits ⋮ Evaluating Matrix Circuits ⋮ Monitoring hyperproperties with circuits ⋮ The conjugacy problem in free solvable groups and wreath products of abelian groups is in ${\mathsf {TC}^0}$ ⋮ Depth-first search in directed planar graphs, revisited ⋮ Parallel complexity for nilpotent groups ⋮ Resource trade-offs in syntactically multilinear arithmetic circuits ⋮ Why does deep and cheap learning work so well? ⋮ Dual VP classes ⋮ The connectivity of Boolean satisfiability: dichotomies for formulas and circuits ⋮ Bounds in ontology-based data access via circuit complexity ⋮ Partial order games ⋮ Visibly Counter Languages and the Structure of $$\mathrm {NC}^{1}$$ ⋮ Parallel Identity Testing for Skew Circuits with Big Powers and Applications ⋮ Active Linking Attacks ⋮ Positive and negative proofs for circuits and branching programs ⋮ A type-assignment of linear erasure and duplication ⋮ Knapsack and the power word problem in solvable Baumslag–Solitar groups ⋮ Improved parallel algorithms for generalized Baumslag groups ⋮ A faster algorithm for determining the linear feasibility of systems of BTVPI constraints ⋮ Recognizing Lexicographically Smallest Words and Computing Successors in Regular Languages ⋮ Logical labeling schemes ⋮ Circuit complexity of linear functions: gate elimination and feeble security ⋮ Small space analogues of Valiant's classes and the limitations of skew formulas ⋮ Knapsack in graph groups ⋮ The Complexity of Complexity ⋮ Cryptographic hardness under projections for time-bounded Kolmogorov complexity ⋮ Circuit complexity of regular languages ⋮ Team semantics for the specification and verification of hyperproperties ⋮ Work-sensitive dynamic complexity of formal languages ⋮ Achieving New Upper Bounds for the Hypergraph Duality Problem through Logic ⋮ Seeking computational efficiency boundaries: the Păun's conjecture ⋮ Tree compression using string grammars ⋮ Counting the number of perfect matchings in $K_{5}$-free graphs ⋮ Walking on data words ⋮ NEXP Does Not Have Non-uniform Quasipolynomial-Size ACC Circuits of o(loglogn) Depth ⋮ Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth ⋮ Reasoning and Query Answering in Description Logics ⋮ Resolution over linear equations and multilinear proofs ⋮ Evaluation of circuits over nilpotent and polycyclic groups ⋮ THE COMPLEXITY OF MODEL CHECKING FOR BOOLEAN FORMULAS ⋮ Log-space conjugacy problem in the Grigorchuk group ⋮ Models of quantum computation and quantum programming languages ⋮ Characterizing Valiant's algebraic complexity classes ⋮ Finding a vector orthogonal to roughly half a collection of vectors ⋮ Better complexity bounds for cost register automata ⋮ Parallel Computation Using Active Self-assembly ⋮ Counting paths in VPA is complete for $\#\mathrm{NC}^1$ ⋮ Characterizing sets of jobs that admit optimal greedy-like algorithms ⋮ Using the renormalization group to classify Boolean functions ⋮ Arithmetizing classes around {\textsf{NC}}$^{1}$ and {\textsf{L}} ⋮ Low complexity algorithms in knot theory ⋮ Division in logspace-uniformNC¹ ⋮ The intractability of computing the Hamming distance ⋮ On the complexity of matrix rank and rigidity ⋮ The descriptive complexity approach to LOGCFL ⋮ On measures of space over real and complex numbers ⋮ Unnamed Item ⋮ Understanding cutting planes for QBFs ⋮ Unnamed Item ⋮ Conjugacy in Baumslag's group, generic case complexity, and division in power circuits ⋮ On the relation between structured $d$-DNNFs and SDDs ⋮ Membership Testing: Removing Extra Stacks from Multi-stack Pushdown Automata ⋮ The non-hardness of approximating circuit size ⋮ Unnamed Item ⋮ Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization ⋮ Low-complexity computations for nilpotent subgroup problems ⋮ Algebraic Complexity Classes ⋮ The complexity of weakly recognizing morphisms ⋮ Ontologies and Databases: The DL-Lite Approach ⋮ On the Descriptive Complexity of Color Coding ⋮ The conjugacy problem in free solvable groups and wreath products of abelian groups is in $\mathsf{TC}^0$ ⋮ Counting of Teams in First-Order Team Logics ⋮ Unnamed Item ⋮ On the Complexity of Szilard Languages of Regulated Grammars ⋮ On the relative succinctness of sentential decision diagrams ⋮ On limitations of structured (deterministic) DNNFs ⋮ On the space and circuit complexity of parameterized problems: classes and completeness ⋮ Better complexity bounds for cost register automata ⋮ No easy puzzles: hardness results for jigsaw puzzles ⋮ Asymptotic invariants, complexity of groups and related problems ⋮ Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata ⋮ Infinitary affine proofs

This page was built for publication: