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.
- Circuits constructed with MOD\(_ q\) gates cannot compute ``and'' in sublinear size (Q1346618) (← links)
- First-order spectra with one binary predicate (Q1350533) (← links)
- Circuits in bounded arithmetic. I (Q1353986) (← links)
- Counting quantifiers, successor relations, and logarithmic space (Q1362332) (← links)
- On the shrinkage exponent for read-once formulae (Q1367534) (← links)
- Dyn-FO: A parallel, dynamic complexity class (Q1376403) (← links)
- Finitely representable databases (Q1376408) (← links)
- Predicting nonlinear cellular automata quickly by decomposing them into linear ones (Q1376426) (← links)
- Algebraic methods and bounded formulas (Q1377552) (← links)
- Upper and lower bounds for some depth-3 circuit classes (Q1377575) (← links)
- \(\text{Count}(q)\) does not imply \(\text{Count}(p)\) (Q1377601) (← links)
- Finite semigroup varieties defined by programs (Q1390876) (← links)
- Circuits and expressions with nonassociative gates (Q1567406) (← links)
- Programs over semigroups of dot-depth one (Q1575738) (← links)
- A slight sharpening of LMN (Q1604204) (← links)
- Which problems have strongly exponential complexity? (Q1604206) (← links)
- The average sensitivity of bounded-depth formulas (Q1653335) (← links)
- Capturing \(k\)-ary existential second order logic with \(k\)-ary inclusion-exclusion logic (Q1693039) (← links)
- First-order expressibility of languages with neutral letters or: The Crane Beach conjecture (Q1776372) (← links)
- Counting modulo quantifiers on finite structures (Q1854352) (← links)
- Languages defined with modular counting quantifiers (Q1854424) (← links)
- Affine projections of symmetric polynomials. (Q1872730) (← links)
- Subset sum ``cubes'' and the complexity of primality testing (Q1885040) (← links)
- Top-down lower bounds for depth-three circuits (Q1904663) (← links)
- On winning Ehrenfeucht games and monadic NP (Q1919539) (← links)
- On deterministic approximation of DNF (Q1923857) (← links)
- Circuit complexity of linear functions: gate elimination and feeble security (Q1946842) (← links)
- Feasibly constructive proofs of succinct weak circuit lower bounds (Q2007873) (← links)
- Explicit list-decodable codes with optimal rate for computationally bounded channels (Q2029777) (← links)
- Upper bound for torus polynomials (Q2117095) (← links)
- The expressive power of \(k\)-ary exclusion logic (Q2273014) (← links)
- Prediction from partial information and hindsight, with application to circuit lower bounds (Q2311545) (← links)
- A new proof of Ajtai's completeness theorem for nonstandard finite structures (Q2339960) (← links)
- Threshold circuits of bounded depth (Q2366275) (← links)
- Arity and alternation: a proper hierarchy in higher order logics (Q2385450) (← links)
- Bounds in ontology-based data access via circuit complexity (Q2411040) (← links)
- Some lower bounds in parameterized \(\mathrm{AC}^{0}\) (Q2417855) (← links)
- A characterization of definability of second-order generalized quantifiers with applications to non-definability (Q2453584) (← links)
- Arity hierarchies (Q2563982) (← links)
- Circuit lower bounds from learning-theoretic approaches (Q2636410) (← links)
- A note on some languages in uniform \(ACC^ 0\) (Q2638770) (← links)
- On uniformity within \(NC^ 1\) (Q2640342) (← links)
- Homomorphic Evaluation Requires Depth (Q2796133) (← links)
- The Expressive Power of k-ary Exclusion Logic (Q2820708) (← links)
- Fine-Grained Cryptography (Q2829959) (← links)
- A Short Implicant of a CNF Formula with Many Satisfying Assignments (Q2942635) (← links)
- A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝] Frege systems (Q2944868) (← links)
- Collapsing modular counting in bounded arithmetic and constant depth propositional proofs (Q2944908) (← links)
- Advice Coins for Classical and Quantum Computation (Q3012792) (← links)
- Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates (Q3012933) (← links)