Pages that link to "Item:Q3318683"

The following pages link to Parity, circuits, and the polynomial-time hierarchy (Q3318683):

Displayed 50 items.

• The intractability of computing the Hamming distance (Q557834) ‎ (← links)
• On adaptive DLOGTIME and POLYLOGTIME reductions (Q672322) ‎ (← links)
• On input read-modes of alternating Turing machines (Q672377) ‎ (← links)
• A note on the power of majority gates and modular gates (Q673905) ‎ (← links)
• Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy (Q685431) ‎ (← links)
• \(NC^ 1\): The automata-theoretic viewpoint (Q685708) ‎ (← links)
• On the power of small-depth threshold circuits (Q685717) ‎ (← links)
• Exponential lower bounds for the pigeonhole principle (Q687506) ‎ (← links)
• On the power of interaction (Q751809) ‎ (← links)
• Non-uniform automata over groups (Q804303) ‎ (← links)
• Large parallel machines can be extremely slow for small problems (Q807013) ‎ (← links)
• On the complexity of counting in the polynomial hierarchy (Q808260) ‎ (← links)
• The parallel complexity of two problems on concurrency (Q811123) ‎ (← links)
• Borel separability of the coanalytic Ramsey sets (Q861824) ‎ (← links)
• Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A? (Q912625) ‎ (← links)
• Lower bounds for constant-depth circuits in the presence of help bits (Q917289) ‎ (← links)
• Lower bounds for recognizing small cliques on CRCW PRAM's (Q919820) ‎ (← links)
• On the computational complexity of the Riemann mapping (Q942023) ‎ (← links)
• Random sequence generation by cellular automata (Q1082817) ‎ (← links)
• Unbounded fan-in circuits and associative functions (Q1083202) ‎ (← links)
• ``During'' cannot be expressed by ``after'' (Q1085154) ‎ (← links)
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition (Q1095871) ‎ (← links)
• One-way functions and circuit complexity (Q1096587) ‎ (← links)
• Limits on the power of concurrent-write parallel machines (Q1103403) ‎ (← links)
• Parallel computation with threshold functions (Q1107324) ‎ (← links)
• The complexity of symmetric functions in bounded-depth circuits (Q1107989) ‎ (← links)
• Semigroups and languages of dot-depth two (Q1109125) ‎ (← links)
• Relativized alternation and space-bounded computation (Q1111024) ‎ (← links)
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\) (Q1117696) ‎ (← links)
• With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy (Q1118405) ‎ (← links)
• On the relative complexity of some languages in \(NC^ 1\) (Q1124355) ‎ (← links)
• Inverse monoids of dot-depth two (Q1124363) ‎ (← links)
• Some notes on threshold circuits, and multiplication in depth 4 (Q1182104) ‎ (← links)
• Rudimentary reductions revisited (Q1183444) ‎ (← links)
• An arithmetic model of computation equivalent to threshold circuits (Q1186610) ‎ (← links)
• Learning in parallel (Q1187024) ‎ (← links)
• The graph of multiplication is equivalent to counting (Q1190513) ‎ (← links)
• A simple lower bound for monotone clique using a communication game (Q1190521) ‎ (← links)
• The invariant problem for binary string structures and the parallel complexity theory of queries (Q1191022) ‎ (← links)
• Regular languages in \(NC\) (Q1191027) ‎ (← links)
• Formulas, regular languages and Boolean circuits (Q1193413) ‎ (← links)
• The complexity of computing symmetric functions using threshold circuits (Q1193637) ‎ (← links)
• The quantifier structure of sentences that characterize nondeterministic time complexity (Q1198956) ‎ (← links)
• Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets (Q1199689) ‎ (← links)
• Extensions to Barrington's M-program model (Q1208406) ‎ (← links)
• On read-once threshold formulae and their randomized decision tree complexity (Q1208407) ‎ (← links)
• A constant-space sequential model of computation for first-order logic (Q1271562) ‎ (← links)
• A lower bound for perceptrons and an oracle separation of the \(PP^{PH}\) hierarchy (Q1271610) ‎ (← links)
• Attribute-efficient learning in query and mistake-bound models (Q1271616) ‎ (← links)
• Threshold circuits of small majority-depth (Q1273878) ‎ (← links)