Buchumschlag

A very sharp threshold for first order logic distinguishability of random graphs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Benjamini, Itai, Zhukovskii, Maksim
Format:	Preprint
Veröffentlicht:	2022
Schlagworte:	Combinatorics Logic in Computer Science Logic Probability
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

First order complexity of finite random structures
von: Demin, Danila, et al.
Veröffentlicht: (2024)

First order distinguishability of sparse random graphs
von: Hershko, Tal, et al.
Veröffentlicht: (2024)

A logical approach to concentration
von: Benedikt, Michael, et al.
Veröffentlicht: (2026)

A logical limit law for the sequential model of preferential attachment graphs
von: Özdemir, Alperen
Veröffentlicht: (2024)

On first-order transductions of classes of graphs
von: Braunfeld, Samuel, et al.
Veröffentlicht: (2022)

Decomposing graphs into stable and ordered parts
von: Buffière, Hector, et al.
Veröffentlicht: (2025)

Local and global $d$-rigidity are not definable in the first order logic of graphs
von: Bernstein, Daniel Irving, et al.
Veröffentlicht: (2025)

First-order logic axiomatization of metric graph theory
von: Chalopin, Jérémie, et al.
Veröffentlicht: (2022)

Elementary first-order model checking for sparse graphs
von: Gajarský, Jakub, et al.
Veröffentlicht: (2024)

On the expressive power of inquisitive team logic and inquisitive first-order logic
von: Kontinen, Juha, et al.
Veröffentlicht: (2026)

Logical limit laws for Mallows random permutations
von: Muller, Tobias, et al.
Veröffentlicht: (2023)

Borel Local Lemma: arbitrary random variables and limited exponential growth
von: Bernshteyn, Anton, et al.
Veröffentlicht: (2024)

On semantics of first-order justification logic with binding modalities
von: Yavorskaya, Tatiana, et al.
Veröffentlicht: (2025)

The failure of cut-elimination in cyclic proof for first-order logic with inductive definitions
von: Oda, Yukihiro, et al.
Veröffentlicht: (2021)

Majority dynamics on finite trees
von: Benjamini, Itai, et al.
Veröffentlicht: (2025)

Two variable logic with ultimately periodic counting
von: Benedikt, Michael, et al.
Veröffentlicht: (2020)

Making first order linear logic a generating grammar
von: Slavnov, Sergey
Veröffentlicht: (2022)

Epsilon-saturation for stable graphs and Littlestone classes
von: Malliaris, Maryanthe, et al.
Veröffentlicht: (2025)

Proofs as stateful programs: A first-order logic with abstract Hoare triples, and an interpretation into an imperative language
von: Powell, Thomas
Veröffentlicht: (2023)

Decomposition horizons and a characterization of stable hereditary classes of graphs
von: Braunfeld, Samuel, et al.
Veröffentlicht: (2022)

On the Metric Temporal Logic for Continuous Stochastic Processes
von: Ikeda, Mitsumasa, et al.
Veröffentlicht: (2023)

Characterizations of monadically dependent tree-ordered weakly sparse structures
von: Buffière, Hector, et al.
Veröffentlicht: (2026)

Indivisibility and uniform computational strength
von: Gill, Kenneth
Veröffentlicht: (2023)

Monadic Second-Order Logic of Permutations
von: Jelínek, Vít, et al.
Veröffentlicht: (2025)

Decidability for Sturmian words
von: Hieronymi, Philipp, et al.
Veröffentlicht: (2021)

Generic sampling and invariant measures on the space of $k$-uniform hypergraphs
von: Ackerman, Nathanael, et al.
Veröffentlicht: (2025)

Separating complexity classes of LCL problems on grids
von: Berlow, Katalin, et al.
Veröffentlicht: (2025)

Order-invariant cluster first-order logic on graph classes of bounded degree
von: Ghasemi, Fatemeh, et al.
Veröffentlicht: (2026)

Going deep and going wide: Counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth
von: Adler, Isolde, et al.
Veröffentlicht: (2025)

A linear proof language for second-order intuitionistic linear logic
von: Díaz-Caro, Alejandro, et al.
Veröffentlicht: (2023)

The proof theory and semantics of second-order (intuitionistic) tense logic
von: Becker, Justus, et al.
Veröffentlicht: (2026)

Constant time testability of first-order logic with modulo counting on finitary graphs
von: Adler, Isolde, et al.
Veröffentlicht: (2026)

First-order transducibility among classes of sparse graphs
von: Gajarský, Jakub, et al.
Veröffentlicht: (2025)

Probabilistic programming interfaces for random graphs: Markov categories, graphons, and nominal sets
von: Ackerman, Nathanael L., et al.
Veröffentlicht: (2023)

Synthesis for prefix first-order logic on data words
von: Grange, Julien, et al.
Veröffentlicht: (2024)

Flip-Breakability: A Combinatorial Dichotomy for Monadically Dependent Graph Classes
von: Dreier, Jan, et al.
Veröffentlicht: (2024)

Zeta Functions and the (Linear) Logic of Markov Processes
von: Seiller, Thomas
Veröffentlicht: (2020)

On the cartesian product of well-orderings
von: Vialard, Isa
Veröffentlicht: (2022)

Advances in Algorithmic Meta Theorems
von: Siebertz, Sebastian, et al.
Veröffentlicht: (2024)

Separability Properties of Monadically Dependent Graph Classes
von: Bonnet, Édouard, et al.
Veröffentlicht: (2025)