Pages that link to "Item:Q3318683"
From MaRDI portal
The following pages link to Parity, circuits, and the polynomial-time hierarchy (Q3318683):
Displayed 50 items.
- A simple function that requires exponential size read-once branching programs (Q287023) (← links)
- The average sensitivity of bounded-depth circuits (Q290255) (← links)
- A lower bound for depth-3 circuits with MOD \(m\) gates (Q293324) (← links)
- Incompressible functions, relative-error extractors, and the power of nondeterministic reductions (Q301524) (← links)
- Collapse of the hierarchy of constant-depth exact quantum circuits (Q347120) (← links)
- DNF sparsification and a faster deterministic counting algorithm (Q354649) (← links)
- A satisfiability algorithm and average-case hardness for formulas over the full binary basis (Q354655) (← links)
- Linear circuits, two-variable logic and weakly blocked monoids (Q391307) (← links)
- Lifting lower bounds for tree-like proofs (Q475337) (← links)
- Isomorphism testing of Boolean functions computable by constant-depth circuits (Q476155) (← links)
- Lower bounds against weakly-uniform threshold circuits (Q486977) (← links)
- Local restrictions from the Furst-Saxe-Sipser paper (Q519884) (← links)
- The communication complexity of addition (Q519955) (← links)
- Descriptional and computational complexity of finite automata -- a survey (Q553312) (← links)
- The intractability of computing the Hamming distance (Q557834) (← links)
- The isomorphism conjecture for constant depth reductions (Q619896) (← 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 correlation between parity and modular polynomials (Q692898) (← links)
- First-order logics: some characterizations and closure properties (Q715044) (← links)
- Mean-payoff games and propositional proofs (Q716324) (← 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)
- Ehrenfeucht-Fraïssé games in finite set theory (Q963464) (← links)
- Universal algebra and hardness results for constraint satisfaction problems (Q1014634) (← links)
- Parallelizing quantum circuits (Q1029356) (← 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)