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.
- Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates (Q3088133) (← links)
- Circuit Lower Bounds for Average-Case MA (Q3194723) (← links)
- Approximating Boolean Functions with Depth-2 Circuits (Q3451753) (← links)
- Extensions of an idea of McNaughton (Q3489464) (← links)
- Reachability is harder for directed than for undirected finite graphs (Q3489984) (← links)
- Descriptional and Computational Complexity of Finite Automata (Q3618565) (← links)
- Ehrenfeucht-Fraïssé Games on Random Structures (Q3638295) (← links)
- Witnessing functions in bounded arithmetic and search problems (Q4227882) (← links)
- <i>y</i>= 2<i>x</i>VS.<i>y</i>= 3<i>x</i> (Q4358061) (← links)
- Faster All-Pairs Shortest Paths via Circuit Complexity (Q4554074) (← links)
- (Q4612482) (← links)
- Bounded Independence Plus Noise Fools Products (Q4641587) (← links)
- Graph Connectivity, Monadic NP and built-in relations of moderate degree (Q4645196) (← links)
- On the correlation of symmetric functions (Q4717052) (← links)
- On the correlation of symmetric functions (Q4879208) (← links)
- A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem (Q4957916) (← links)
- A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas (Q5002707) (← links)
- (Q5005174) (← links)
- (Q5005182) (← links)
- From Circuit Complexity to Faster All-Pairs Shortest Paths (Q5009891) (← links)
- (Q5028429) (← links)
- Parameterized Parallel Computing and First-Order Logic (Q5049039) (← links)
- Quantified Derandomization: How to Find Water in the Ocean (Q5060673) (← links)
- (Q5077146) (← links)
- Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization (Q5080481) (← links)
- Fourier bounds and pseudorandom generators for product tests (Q5091757) (← links)
- Parity helps to compute majority (Q5091774) (← links)
- On the Symmetries of and Equivalence Test for Design Polynomials. (Q5092415) (← links)
- (Q5092467) (← links)
- A super-quadratic lower bound for depth four arithmetic circuits (Q5092474) (← links)
- Lower bounds for modular counting by circuits with modular gates (Q5096324) (← links)
- On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions (Q5098770) (← links)
- Worst-Case to Average-Case Reductions for Subclasses of P (Q5098780) (← links)
- NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN (Q5100043) (← links)
- (Q5101347) (← links)
- (Q5140844) (← links)
- Circuit complexity and the expressive power of generalized first-order formulas (Q5204302) (← links)
- Infinitary logic for computer science (Q5204339) (← links)
- Sampling Lower Bounds: Boolean Average-Case and Permutations (Q5216796) (← links)
- Expressiveness of Logic Programs under the General Stable Model Semantics (Q5278207) (← links)
- Notes on polynomially bounded arithmetic (Q5687325) (← links)
- (Q5875501) (← links)
- Natural proofs (Q5906823) (← links)
- Injecting inconsistencies into models of PA (Q5916455) (← links)
- Fine-grained cryptography revisited (Q5918348) (← links)
- The non-hardness of approximating circuit size (Q5918358) (← links)
- Circuit complexity of regular languages (Q5918477) (← links)
- An exact characterization of symmetric functions in \(qAC^{0}[2]\) (Q5941440) (← links)
- The descriptive complexity approach to LOGCFL (Q5946058) (← links)
- Propositional proof complexity (Q6064569) (← links)