Pages that link to "Item:Q1117696"

The following pages link to Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\) (Q1117696):

Displayed 50 items.

• Optimal advice (Q672755) ‎ (← links)
• Knapsack problems for NL (Q673615) ‎ (← links)
• \(NC^ 1\): The automata-theoretic viewpoint (Q685708) ‎ (← links)
• Towards optimal simulations of formulas by bounded-width programs (Q685723) ‎ (← links)
• Planar and grid graph reachability problems (Q733742) ‎ (← links)
• Non-uniform automata over groups (Q804303) ‎ (← links)
• 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)
• 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)
• 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)
• Robustness of PSPACE-complete sets (Q2379952) ‎ (← links)
• Learning expressions and programs over monoids (Q2490112) ‎ (← links)
• The computational power of Benenson automata (Q2575082) ‎ (← links)
• On the computational power of probabilistic and quantum branching program (Q2581534) ‎ (← links)
• A note on some languages in uniform \(ACC^ 0\) (Q2638770) ‎ (← links)
• On uniformity within \(NC^ 1\) (Q2640342) ‎ (← links)
• Extensions of an idea of McNaughton (Q3489464) ‎ (← links)