Ehrenfeucht-Fraïssé Games on Random Structures

DOI10.1007/978-3-642-02261-6_28zbMath1246.03057OpenAlexW2094189083MaRDI QIDQ3638295

Benjamin Rossman

Publication date: 2 July 2009

Published in: Logic, Language, Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02261-6_28

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Model theory of finite structures (03C13) Combinatorial games (91A46) Descriptive complexity and finite models (68Q19)

Related Items (1)

The Ehrenfeucht-Fraïssé Method and the Planted Clique Conjecture

Cites Work

• Unnamed Item
• Unnamed Item
• The average sensitivity of bounded-depth circuits
• Elements of finite model theory.
• Lower bounds for recognizing small cliques on CRCW PRAM's
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Upper and lower bounds for first order expressibility
• A simple lower bound for monotone clique using a communication game
• Number of variables is equivalent to space
• Constant depth circuits, Fourier transform, and learnability
• Parity, circuits, and the polynomial-time hierarchy
• A logic for constant-depth circuits
• Definability by constant-depth polynomial-size circuits
• A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with at most (1/6)log log n Negation Gates

This page was built for publication: Ehrenfeucht-Fraïssé Games on Random Structures