# Ehrenfeucht-Fraïssé Games on Random Structures

Published

Conference Paper

Certain results in circuit complexity (e.g., the theorem that AC 0 functions have low average sensitivity) [5, 17] imply the existence of winning strategies in Ehrenfeucht-Fraïssé games on pairs of random structures (e.g., ordered random graphs G∈=∈G(n,1/2) and G ∈+∈∈=∈G∈ ∪∈{random edge}). Standard probabilistic methods in circuit complexity (e.g., the Switching Lemma [11] or Razborov-Smolensky Method [19, 21]), however, give no information about how a winning strategy might look. In this paper, we attempt to identify specific winning strategies in these games (as explicitly as possible). For random structures G and G ∈+∈, we prove that the composition of minimal strategies in r-round Ehrenfeucht-Fraïssé games and is almost surely a winning strategy in the game . We also examine a result of [20] that ordered random graphs H∈=∈G(n,p) and H ∈+∈∈=∈H∈ ∪∈{random k-clique} with p(n)∈ ≪-∈2/(k∈-∈1) (below the k-clique threshold) are almost surely indistinguishable by -variable first-order sentences of any fixed quantifier-rank r. We describe a winning strategy in the corresponding r-round -pebble game using a technique that combines strategies from several auxiliary games. © 2009 Springer Berlin Heidelberg.

### Full Text

### Duke Authors

### Cited Authors

- Rossman, B

### Published Date

- August 20, 2009

### Published In

### Volume / Issue

- 5514 LNAI /

### Start / End Page

- 350 - 364

### Electronic International Standard Serial Number (EISSN)

- 1611-3349

### International Standard Serial Number (ISSN)

- 0302-9743

### International Standard Book Number 10 (ISBN-10)

- 364202260X

### International Standard Book Number 13 (ISBN-13)

- 9783642022609

### Digital Object Identifier (DOI)

- 10.1007/978-3-642-02261-6_28

### Citation Source

- Scopus