Bounded-width polynomial-size branching programs recognize exactly those languages in $NC^ 1$

DOI10.1016/0022-0000(89)90037-8zbMath0667.68059OpenAlexW4240781210WikidataQ29543597 ScholiaQ29543597MaRDI QIDQ1117696

Publication date: 1989

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(89)90037-8

zbMATH Keywords

branching programs bounded width $NC^ 1$word problem for nonsolvable groups

Mathematics Subject Classification ID

Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).

Related Items (only showing first 100 items - show all)

Uniform constant-depth threshold circuits for division and iterated multiplication. ⋮ Function-algebraic characterizations of log and polylog parallel time ⋮ The correlation between parity and quadratic polynomials mod $3$ ⋮ The equivalence of theories that characterize ALogTime ⋮ On learning width two branching programs ⋮ On ACC ⋮ Representing Boolean functions as polynomials modulo composite numbers ⋮ Robustness of PSPACE-complete sets ⋮ A note on a theorem of Barrington, Straubing and Thérien ⋮ A note on some languages in uniform $ACC^ 0$ ⋮ On uniformity within $NC^ 1$ ⋮ A note on logspace optimization ⋮ A generalization of Spira's theorem and circuits with small segregators or separators ⋮ The complexity of intersecting finite automata having few final states ⋮ Dyn-FO: A parallel, dynamic complexity class ⋮ Predicting nonlinear cellular automata quickly by decomposing them into linear ones ⋮ Skew circuits of small width ⋮ Hadamard tensors and lower bounds on multiparty communication complexity ⋮ Comments on ``Arithmetic complexity, Kleene closure, and formal power series ⋮ On the relative complexity of some languages in $NC^ 1$ ⋮ Uniform derandomization from pathetic lower bounds ⋮ Autoreducibility, mitoticity, and immunity ⋮ Efficient oblivious branching programs for threshold and mod functions ⋮ Universally serializable computation ⋮ A Circuit Complexity Approach to Transductions ⋮ Visibly Counter Languages and the Structure of $$\mathrm {NC}^{1}$$ ⋮ Linear circuits, two-variable logic and weakly blocked monoids ⋮ Finite semigroup varieties defined by programs ⋮ Nondeterministic stack register machines ⋮ Deterministic summation modulo $\mathcal B_{n}$, the semigroup of binary relations on $0,1, \dots, n-1$ ⋮ Symmetry structure in discrete models of biochemical systems: natural subsystems and the weak control hierarchy in a new model of computation driven by interactions ⋮ An algebraic approach to data languages and timed languages ⋮ Positive and negative proofs for circuits and branching programs ⋮ Computational fuzzy extractor from LWE ⋮ Complexity of regular functions ⋮ Completeness results for graph isomorphism. ⋮ Space efficient representations of finite groups ⋮ Small space analogues of Valiant's classes and the limitations of skew formulas ⋮ Comparative complexity of quantum and classical OBDDs for total and partial functions ⋮ Deciding FO-definability of regular languages ⋮ Ring-based identity based encryption -- asymptotically shorter MPK and tighter security ⋮ NIKE from affine determinant programs ⋮ Direct computation of branching programs and its applications to more efficient lattice-based cryptography ⋮ An automaton group with \textsf{PSPACE}-complete word problem ⋮ Lattice-based FHE as secure as PKE ⋮ On mod $p$ transversals ⋮ On the computational power of programs over $\mathsf{BA}_2$ monoid ⋮ Oracle branching programs and Logspace versus $P^*$ ⋮ Length of polynomials over finite groups ⋮ Optimal advice ⋮ Knapsack problems for NL ⋮ First-order rewritability of ontology-mediated queries in linear temporal logic ⋮ Regular languages in $NC$ ⋮ Evaluation of circuits over nilpotent and polycyclic groups ⋮ $NC^ 1$: The automata-theoretic viewpoint ⋮ Towards optimal simulations of formulas by bounded-width programs ⋮ Closure of varieties of languages under products with counter ⋮ Better complexity bounds for cost register automata ⋮ On the correlation between parity and modular polynomials ⋮ Learning read-constant polynomials of constant degree modulo composites ⋮ Counting paths in VPA is complete for $\#\mathrm{NC}^1$ ⋮ A more efficient leveled strongly-unforgeable fully homomorphic signature scheme ⋮ Extensions to Barrington's M-program model ⋮ Arithmetizing classes around {\textsf{NC}}$^{1}$ and {\textsf{L}} ⋮ Leaf languages and string compression ⋮ Learning expressions and programs over monoids ⋮ On the structure of Boolean functions with small spectral norm ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ Functions computable in polynomial space ⋮ Tight conditional lower bounds for longest common increasing subsequence ⋮ First-order logics: some characterizations and closure properties ⋮ The algebraic theory of Parikh automata ⋮ A moderately exponential time algorithm for $k$-IBDD satisfiability ⋮ Satisfiability algorithm for syntactic read-$k$-times branching programs ⋮ Decompositions of Triangle-Dense Graphs ⋮ No Tits alternative for cellular automata ⋮ Planar and grid graph reachability problems ⋮ The word problem of the Brin-Thompson group is \textsf{coNP}-complete ⋮ Algebraic Complexity Classes ⋮ Succinct representation, leaf languages, and projection reductions ⋮ Relating polynomial time to constant depth ⋮ Nondeterministic $NC^1$ computation ⋮ Quantum Homomorphic Encryption for Polynomial-Sized Circuits ⋮ Counting classes and the fine structure between $\mathrm{NC}^1$ and $L$ ⋮ Circuits and expressions with nonassociative gates ⋮ Lattice-Based Fully Dynamic Multi-key FHE with Short Ciphertexts ⋮ Programs over semigroups of dot-depth one ⋮ An impossibility gap between width-4 and width-5 permutation branching programs ⋮ Complexity theory. Abstracts from the workshop held November 11--17, 2018 ⋮ The computational power of Benenson automata ⋮ Counting modulo quantifiers on finite structures ⋮ Languages defined with modular counting quantifiers ⋮ On the computational power of probabilistic and quantum branching program ⋮ Hardness of approximation for knapsack problems ⋮ Non-uniform automata over groups ⋮ The parallel complexity of two problems on concurrency ⋮ Multi-head finite automata: Data-independent versus data-dependent computations ⋮ Upper bound for torus polynomials ⋮ Compression techniques in group theory ⋮ On learning embedded midbit functions

Cites Work

This page was built for publication: Bounded-width polynomial-size branching programs recognize exactly those languages in $NC^ 1$

Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)