The Ehrenfeucht-Fraïssé Method and the Planted Clique Conjecture
From MaRDI portal
Publication:2947167
DOI10.1007/978-3-319-23534-9_5zbMath1465.68098MaRDI QIDQ2947167
Publication date: 22 September 2015
Published in: Fields of Logic and Computation II (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-23534-9_5
91A80: Applications of game theory
03B70: Logic in computer science
03C13: Model theory of finite structures
68Q19: Descriptive complexity and finite models
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of explicit constructions
- Expected complexity of graph partitioning problems
- Hiding cliques for cryptographic security
- On monadic NP vs monadic co-NP
- Arity hierarchies
- How Hard Is It to Approximate the Best Nash Equilibrium?
- An application of games to the completeness problem for formalized theories
- Reachability is harder for directed than for undirected finite graphs
- Ehrenfeucht-Fraïssé Games on Random Structures
- Small Clique Detection and Approximate Nash Equilibria
- Zero-One Laws for Sparse Random Graphs
- Large Cliques Elude the Metropolis Process
- Yet another hierarchy theorem
- Computational Complexity