Pages that link to "Item:Q1054720"
From MaRDI portal
The following pages link to \(\Sigma_ 1^ 1\)-formulae on finite structures (Q1054720):
Displaying 50 items.
- Existential second-order logic and modal logic with quantified accessibility relations (Q259071) (← links)
- 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)
- 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)
- Randomness buys depth for approximate counting (Q483707) (← links)
- Local restrictions from the Furst-Saxe-Sipser paper (Q519884) (← links)
- Descriptional and computational complexity of finite automata -- a survey (Q553312) (← links)
- On adaptive DLOGTIME and POLYLOGTIME reductions (Q672322) (← links)
- A note on the power of majority gates and modular gates (Q673905) (← 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)
- Finite-model theory -- A personal perspective (Q688663) (← links)
- On the correlation between parity and modular polynomials (Q692898) (← links)
- First-order logics: some characterizations and closure properties (Q715044) (← links)
- A short implicant of a CNF formula with many satisfying assignments (Q727982) (← links)
- Non-uniform automata over groups (Q804303) (← links)
- On the complexity of counting in the polynomial hierarchy (Q808260) (← links)
- Pseudorandom bits for constant depth circuits (Q808707) (← links)
- The parallel complexity of two problems on concurrency (Q811123) (← 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)
- 0-1 laws and decision problems for fragments of second-order logic (Q920075) (← links)
- Bounded-depth, polynomial-size circuits for symmetric functions (Q1063574) (← links)
- Threshold functions and bounded depth monotone circuits (Q1088970) (← 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)
- Random oracles separate PSPACE from the polynomial-time hierarchy (Q1108794) (← 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)
- Rudimentary reductions revisited (Q1183444) (← links)
- A simple lower bound for monotone clique using a communication game (Q1190521) (← links)
- Regular languages in \(NC\) (Q1191027) (← links)
- Formulas, regular languages and Boolean circuits (Q1193413) (← links)
- Infinitary logics and 0-1 laws (Q1193591) (← links)
- The complexity of computing symmetric functions using threshold circuits (Q1193637) (← links)
- The quantifier structure of sentences that characterize nondeterministic time complexity (Q1198956) (← links)
- On read-once threshold formulae and their randomized decision tree complexity (Q1208407) (← links)
- First-order definability on finite structures (Q1263576) (← links)
- Threshold circuits of small majority-depth (Q1273878) (← links)
- Reductions in circuit complexity: An isomorphism theorem and a gap theorem (Q1276160) (← links)
- Functions with bounded symmetric communication complexity, programs over commutative monoids, and ACC (Q1317485) (← links)
- Bounded-width polynomial-size Boolean formulas compute exactly those functions in AC\(^ 0\) (Q1327317) (← links)
- On ACC (Q1346616) (← links)