Pages that link to "Item:Q1117696"
From MaRDI portal
The following pages link to Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\) (Q1117696):
Displayed 50 items.
- The parallel complexity of two problems on concurrency (Q811123) (← links)
- On learning embedded midbit functions (Q817826) (← links)
- The equivalence of theories that characterize ALogTime (Q834715) (← links)
- Autoreducibility, mitoticity, and immunity (Q881593) (← links)
- Positive and negative proofs for circuits and branching programs (Q896677) (← links)
- Comparative complexity of quantum and classical OBDDs for total and partial functions (Q906414) (← links)
- Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}} (Q968272) (← links)
- An impossibility gap between width-4 and width-5 permutation branching programs (Q1041742) (← links)
- On the relative complexity of some languages in \(NC^ 1\) (Q1124355) (← links)
- On mod \(p\) transversals (Q1180406) (← links)
- Oracle branching programs and Logspace versus \(P^*\) (Q1183604) (← links)
- Regular languages in \(NC\) (Q1191027) (← links)
- Closure of varieties of languages under products with counter (Q1201878) (← links)
- Extensions to Barrington's M-program model (Q1208406) (← links)
- Succinct representation, leaf languages, and projection reductions (Q1271623) (← links)
- Relating polynomial time to constant depth (Q1274992) (← links)
- Nondeterministic \(NC^1\) computation (Q1276170) (← links)
- Function-algebraic characterizations of log and polylog parallel time (Q1332666) (← links)
- On ACC (Q1346616) (← links)
- Representing Boolean functions as polynomials modulo composite numbers (Q1346617) (← links)
- A note on a theorem of Barrington, Straubing and Thérien (Q1351160) (← links)
- Dyn-FO: A parallel, dynamic complexity class (Q1376403) (← links)
- Predicting nonlinear cellular automata quickly by decomposing them into linear ones (Q1376426) (← links)
- Efficient oblivious branching programs for threshold and mod functions (Q1384527) (← links)
- Universally serializable computation (Q1384538) (← links)
- Finite semigroup varieties defined by programs (Q1390876) (← links)
- Nondeterministic stack register machines (Q1391527) (← links)
- Deterministic summation modulo \(\mathcal B_{n}\), the semigroup of binary relations on \(0,1, \dots, n-1\) (Q1392020) (← links)
- An algebraic approach to data languages and timed languages (Q1398367) (← links)
- Completeness results for graph isomorphism. (Q1401960) (← links)
- Circuits and expressions with nonassociative gates (Q1567406) (← links)
- Programs over semigroups of dot-depth one (Q1575738) (← links)
- Multi-head finite automata: Data-independent versus data-dependent computations (Q1608894) (← links)
- Evaluation of circuits over nilpotent and polycyclic groups (Q1750355) (← links)
- Counting paths in VPA is complete for \(\#\mathrm{NC}^1\) (Q1759656) (← links)
- Functions computable in polynomial space (Q1775891) (← links)
- Counting modulo quantifiers on finite structures (Q1854352) (← links)
- Languages defined with modular counting quantifiers (Q1854424) (← links)
- Uniform constant-depth threshold circuits for division and iterated multiplication. (Q1872733) (← links)
- The correlation between parity and quadratic polynomials mod \(3\) (Q1881261) (← links)
- A note on logspace optimization (Q1904668) (← links)
- Small space analogues of Valiant's classes and the limitations of skew formulas (Q1947043) (← links)
- Better complexity bounds for cost register automata (Q1999991) (← links)
- A more efficient leveled strongly-unforgeable fully homomorphic signature scheme (Q2004727) (← links)
- On the structure of Boolean functions with small spectral norm (Q2012184) (← links)
- Satisfiability algorithm for syntactic read-\(k\)-times branching programs (Q2032296) (← links)
- Upper bound for torus polynomials (Q2117095) (← links)
- Compression techniques in group theory (Q2117795) (← links)
- Skew circuits of small width (Q2173307) (← links)
- Space efficient representations of finite groups (Q2194866) (← links)