M. Makarov

most citedLogical complexity of induced subgraph isomorphism for certain graph families

1 citations · 1 across the 2 of their papers we have counts for

collaborators

2 papers

cs.DS2022

Toeplitz Low-Rank Approximation with Sublinear Query Complexity

Michael Kapralov, Hannah Lawrence, Mikhail Makarov +2

We present a sublinear query algorithm for outputting a near-optimal low-rank approximation to any positive semidefinite Toeplitz matrix $T \in R^{d \times d}$ . In particu…

math.CO2019★ 1 cited

Logical complexity of induced subgraph isomorphism for certain graph families

E. D. Kudryavtsev, M. V. Makarov, A. S. Shlychkova +1

We prove that, for every $ℓ \geq 4$ , there exists an $ℓ$ -vertex graph and a first order sentence having a quantifier depth at most $ℓ - 1$ defining the property of having an…