\(\Sigma_ 1^ 1\)-formulae on finite structures
From MaRDI portal
Publication:1054720
DOI10.1016/0168-0072(83)90038-6zbMath0519.03021OpenAlexW2036656440MaRDI QIDQ1054720
Publication date: 1983
Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0168-0072(83)90038-6
Nonstandard models of arithmetic (03H15) Interpolation, preservation, definability (03C40) Basic properties of first-order languages and structures (03C07)
Related Items (only showing first 100 items - show all)
Expressiveness of Logic Programs under the General Stable Model Semantics ⋮ Parameterized Parallel Computing and First-Order Logic ⋮ Approximating Boolean Functions with Depth-2 Circuits ⋮ Quantified Derandomization: How to Find Water in the Ocean ⋮ Faster All-Pairs Shortest Paths via Circuit Complexity ⋮ Circuit Lower Bounds for Average-Case MA ⋮ Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization ⋮ Extensions of an idea of McNaughton ⋮ Reachability is harder for directed than for undirected finite graphs ⋮ On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions ⋮ Worst-Case to Average-Case Reductions for Subclasses of P ⋮ NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN ⋮ Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle? ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the correlation of symmetric functions ⋮ Unnamed Item ⋮ Notes on polynomially bounded arithmetic ⋮ Unnamed Item ⋮ y= 2xVS.y= 3x ⋮ A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas ⋮ Bounded Independence Plus Noise Fools Products ⋮ Graph Connectivity, Monadic NP and built-in relations of moderate degree ⋮ Circuit complexity of regular languages ⋮ Injecting inconsistencies into models of PA ⋮ Unnamed Item ⋮ Natural proofs ⋮ An exact characterization of symmetric functions in \(qAC^{0}[2\)] ⋮ The descriptive complexity approach to LOGCFL ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Circuit complexity and the expressive power of generalized first-order formulas ⋮ Infinitary logic for computer science ⋮ A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus$ via the Coin Problem] ⋮ Descriptional and Computational Complexity of Finite Automata ⋮ Fine-grained cryptography revisited ⋮ The non-hardness of approximating circuit size ⋮ Sampling Lower Bounds: Boolean Average-Case and Permutations ⋮ Propositional proof complexity ⋮ Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates ⋮ On the correlation of symmetric functions ⋮ Ehrenfeucht-Fraïssé Games on Random Structures ⋮ Parity helps to compute majority ⋮ On the Symmetries of and Equivalence Test for Design Polynomials. ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ Fourier bounds and pseudorandom generators for product tests ⋮ Lower bounds for modular counting by circuits with modular gates ⋮ Unnamed Item ⋮ Unnamed Item ⋮ From Circuit Complexity to Faster All-Pairs Shortest Paths ⋮ Witnessing functions in bounded arithmetic and search problems ⋮ Affine projections of symmetric polynomials. ⋮ Bounded-width polynomial-size Boolean formulas compute exactly those functions in AC\(^ 0\) ⋮ Threshold circuits of bounded depth ⋮ A simple function that requires exponential size read-once branching programs ⋮ The average sensitivity of bounded-depth circuits ⋮ Subset sum ``cubes and the complexity of primality testing ⋮ A lower bound for depth-3 circuits with MOD \(m\) gates ⋮ Threshold functions and bounded depth monotone circuits ⋮ Incompressible functions, relative-error extractors, and the power of nondeterministic reductions ⋮ On ACC ⋮ Circuits constructed with MOD\(_ q\) gates cannot compute ``and in sublinear size ⋮ Lower bounds on the size of bounded depth circuits over a complete basis with logical addition ⋮ One-way functions and circuit complexity ⋮ First-order spectra with one binary predicate ⋮ Circuit lower bounds from learning-theoretic approaches ⋮ Circuits in bounded arithmetic. I ⋮ A note on some languages in uniform \(ACC^ 0\) ⋮ Arity and alternation: a proper hierarchy in higher order logics ⋮ On uniformity within \(NC^ 1\) ⋮ Limits on the power of concurrent-write parallel machines ⋮ Top-down lower bounds for depth-three circuits ⋮ Parallel computation with threshold functions ⋮ Counting quantifiers, successor relations, and logarithmic space ⋮ The average sensitivity of bounded-depth formulas ⋮ Random oracles separate PSPACE from the polynomial-time hierarchy ⋮ On the shrinkage exponent for read-once formulae ⋮ DNF sparsification and a faster deterministic counting algorithm ⋮ A satisfiability algorithm and average-case hardness for formulas over the full binary basis ⋮ Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\) ⋮ With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy ⋮ Dyn-FO: A parallel, dynamic complexity class ⋮ Finitely representable databases ⋮ Predicting nonlinear cellular automata quickly by decomposing them into linear ones ⋮ Algebraic methods and bounded formulas ⋮ Upper and lower bounds for some depth-3 circuit classes ⋮ \(\text{Count}(q)\) does not imply \(\text{Count}(p)\) ⋮ On winning Ehrenfeucht games and monadic NP ⋮ On the relative complexity of some languages in \(NC^ 1\) ⋮ On deterministic approximation of DNF ⋮ A Short Implicant of a CNF Formula with Many Satisfying Assignments ⋮ Bounds in ontology-based data access via circuit complexity ⋮ A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝 Frege systems] ⋮ Collapsing modular counting in bounded arithmetic and constant depth propositional proofs ⋮ Finite semigroup varieties defined by programs ⋮ Some lower bounds in parameterized \(\mathrm{AC}^{0}\) ⋮ Capturing \(k\)-ary existential second order logic with \(k\)-ary inclusion-exclusion logic ⋮ Circuit complexity of linear functions: gate elimination and feeble security ⋮ Lower bounds for constant-depth circuits in the presence of help bits
Cites Work
This page was built for publication: \(\Sigma_ 1^ 1\)-formulae on finite structures
