Paper Info
Title
Ehrenfeucht-Fraïssé Games on Random Structures
Abstract
Certain results in circuit complexity (e.g., the theorem that AC0 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 $\Game_r(G,G)$ and $\Game_r(G^{{+}},G^{{+}})$ is almost surely a winning strategy in the game $\Game_r(G,G^{{+}})$. We also examine a result of [20] that ordered random graphs H = G (n ,p ) and H + = H *** {random k -clique} with p (n ) *** n *** 2/(k *** 1) (below the k -clique threshold) are almost surely indistinguishable by $\lfloor k/4 \rfloor$-variable first-order sentences of any fixed quantifier-rank r . We describe a winning strategy in the corresponding r -round $\lfloor k/4 \rfloor$-pebble game using a technique that combines strategies from several auxiliary games.
Year
DOI
Venue
2009
10.1007/978-3-642-02261-6_28
WoLLIC
Keywords
Field
DocType
random graph,corresponding r,circuit complexity,random structures,specific winning strategy,lfloor k,winning strategy,random edge,random k,random graphs h,random structure,first order,probabilistic method
Kripke structure,Discrete mathematics,Combinatorics,Random graph,Circuit complexity,Clique,Algorithm,Probabilistic method,Almost surely,Lemma (mathematics),Mathematics
Conference
Volume
ISSN
Citations 
5514
0302-9743
1
PageRank 
References 
Authors
0.37
17
1
Name
Order
Citations
PageRank
Benjamin Rossman129820.00