Spectrum of FO logic with quantifier depth 4 is finite

Source

ACM Transactions on Computational Logic

DATE OF PUBLICATION

03/28/2024

Authors

Yury Yarovikov

Maksim Zhukovskii

Abstract

The k-spectrum is the set of all α > 0 such that G(n,n−α) does not obey the 0-1 law for FO sentences with quantifier depth at most k. In this article, we prove that the minimum k such that the k-spectrum is infinite equals 5.

Full text DOWNLOAD pdf

Anatomical Position Embeddings

Mikhail Goncharov, Valentin Samokhin, Eugenia Soboleva, Roman Sokolov, Boris Shirokikh, Mikhail Belyaev, Anvar Kurmukov, Ivan Oseledets

SOURCE

Self-Attentive Sequential Recommendations with Hyperbolic Representations

Evgeny Frolov, Tatiana Matveeva, Leyla Mirvakhabova, Ivan Oseledets

SOURCE

General Lipschitz: Certified Robustness Against Resolvable Semantic Transformations via Transformation-Dependent Randomized Smoothing

Dmitrii Korzh, Mikhail Pautov, Olga Tsymboi, Ivan Oseledets

SOURCE

A case study of spatiotemporal forecasting techniques for weather forecasting

Shakir Showkat Sofi, Ivan Oseledets

SOURCE

RECE: Reduced Cross-Entropy Loss for Large-Catalogue Sequential Recommenders

Danil Gusak, Gleb Mezentsev, Ivan Oseledets, Evgeny Frolov

SOURCE

SparseGrad: A Selective Method for Efficient Fine-tuning of MLP Layers

Viktoriia Chekalina, Anna Rudenko, Gleb Mezentsev, Aleksandr Mikhalev, Alexander Panchenko, Ivan Oseledets

SOURCE

A perspective on the artificial intelligence's transformative role in advancing diffractive optics

Svetlana Khonina, Nikolay Kazanskiy, Albert Efimov, A.V. Nikonorov, Ivan Oseledets, R.V. Skidanov, M.A. Butt

SOURCE

Spectrum of FO logic with quantifier depth 4 is finite

Abstract

Similar publications