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

DOI10.1007/978-3-319-23534-9_5zbMath1465.68098OpenAlexW2296108045MaRDI QIDQ2947167

Yijia Chen, Jörg Flum

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

Mathematics Subject Classification ID

Applications of game theory (91A80) Logic in computer science (03B70) Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19)

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