Math @ Duke

Publications [#348692] of Benjamin Rossman
Papers Published
 Rossman, B, EhrenfeuchtFraïssé Games on Random Structures,
Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5514 LNAI
(August, 2009),
pp. 350364, ISBN 364202260X [doi]
(last updated on 2023/06/02)
Abstract: 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 EhrenfeuchtFraï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 RazborovSmolensky 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 rround EhrenfeuchtFraï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 kclique} with p(n)∈ ≪∈2/(k∈∈1) (below the kclique threshold) are almost surely indistinguishable by variable firstorder sentences of any fixed quantifierrank r. We describe a winning strategy in the corresponding rround pebble game using a technique that combines strategies from several auxiliary games. © 2009 Springer Berlin Heidelberg.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

