BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Isolde Adler

Isolde Adler contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Discrete MathematicsLogic in Computer ScienceData Structures and Algorithmsmath.CODatabasesmath.LOComputational Complexity

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
7works
0followers
7topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

7 published item(s)

preprint2021arXiv

On Testability of First-Order Properties in Bounded-Degree Graphs

We study property testing of properties that are definable in first-order logic (FO) in the bounded-degree graph and relational structure models. We show that any FO property that is defined by a formula with quantifier prefix $\exists^*\forall^*$ is testable (i.e., testable with constant query complexity), while there exists an FO property that is expressible by a formula with quantifier prefix $\forall^*\exists^*$ that is not testable. In the dense graph model, a similar picture is long known (Alon, Fischer, Krivelevich, Szegedy, Combinatorica 2000), despite the very different nature of the two models. In particular, we obtain our lower bound by a first-order formula that defines a class of bounded-degree expanders, based on zig-zag products of graphs. We expect this to be of independent interest. We then prove testability of some first-order properties that speak about isomorphism types of neighbourhoods, including testability of $1$-neighbourhood-freeness, and $r$-neighbourhood-freeness under a mild assumption on the degrees.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Towards Approximate Query Enumeration with Sublinear Preprocessing Time

This paper aims at providing extremely efficient algorithms for approximate query enumeration on sparse databases, that come with performance and accuracy guarantees. We introduce a new model for approximate query enumeration on classes of relational databases of bounded degree. We first prove that on databases of bounded degree any local first-order definable query can be enumerated approximately with constant delay after a constant time preprocessing phase. We extend this, showing that on databases of bounded tree-width and bounded degree, every query that is expressible in first-order logic can be enumerated approximately with constant delay after a sublinear (more precisely, polylogarithmic) time preprocessing phase. Durand and Grandjean (ACM Transactions on Computational Logic 2007) proved that exact enumeration of first-order queries on databases of bounded degree can be done with constant delay after a linear time preprocessing phase. Hence we achieve a significant speed-up in the preprocessing phase. Since sublinear running time does not allow reading the whole input database even once, sacrificing some accuracy is inevitable for our speed-up. Nevertheless, our enumeration algorithms come with guarantees: With high probability, (1) only tuples are enumerated that are answers to the query or `close' to being answers to the query, and (2) if the proportion of tuples that are answers to the query is sufficiently large, then all answers will be enumerated. Here the notion of `closeness' is a tuple edit distance in the input database. For local first-order queries, only actual answers are enumerated, strengthening (1). Moreover, both the `closeness' and the proportion required in (2) are controllable. We combine methods from property testing of bounded degree graphs with logic and query enumeration, which we believe can inspire further research.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Faster Property Testers in a Variation of the Bounded Degree Model

Property testing algorithms are highly efficient algorithms, that come with probabilistic accuracy guarantees. For a property P, the goal is to distinguish inputs that have P from those that are far from having P with high probability correctly, by querying only a small number of local parts of the input. In property testing on graphs, the distance is measured by the number of edge modifications (additions or deletions), that are necessary to transform a graph into one with property P. Much research has focussed on the query complexity of such algorithms, i. e. the number of queries the algorithm makes to the input, but in view of applications, the running time of the algorithm is equally relevant. In (Adler, Harwath STACS 2018), a natural extension of the bounded degree graph model of property testing to relational databases of bounded degree was introduced, and it was shown that on databases of bounded degree and bounded tree-width, every property that is expressible in monadic second-order logic with counting (CMSO) is testable with constant query complexity and sublinear running time. It remains open whether this can be improved to constant running time. In this paper we introduce a new model, which is based on the bounded degree model, but the distance measure allows both edge (tuple) modifications and vertex (element) modifications. Our main theorem shows that on databases of bounded degree and bounded tree-width, every property that is expressible in CMSO is testable with constant query complexity and constant running time in the new model. We also show that every property that is testable in the classical model is testable in our model with the same query complexity and running time, but the converse is not true. We argue that our model is natural and our meta-theorem showing constant-time CMSO testability supports this.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Vapnik-Chervonenkis Dimension and Density on Johnson and Hamming Graphs

VC-dimension and VC-density are measures of combinatorial complexity of set systems. VC-dimension was first introduced in the context of statistical learning theory, and is tightly related to the sample complexity in PAC learning. VC-density is a refinement of VC-dimension. Both notions are also studied in model theory, in the context of \emph{dependent} theories. A set system that is definable by a formula of first-order logic with parameters has finite VC-dimension if and only if the formula is a dependent formula. In this paper we study the VC-dimension and the VC-density of the edge relation $Exy$ on Johnson graphs and on Hamming graphs. On a graph $G$, the set system defined by the formula $Exy$ is the vertex set of $G$ along with the collection of all \emph{open neighbourhoods} of $G$. We show that the edge relation has VC-dimension at most $4$ on Johnson graphs and at most $3$ on Hamming graphs and these bounds are optimal. We furthermore show that the VC-density of the edge relation on the class of all Johnson graphs is $2$, and on the class of all Hamming graphs the VC-density is $2$ as well. Moreover, we show that our bounds on the VC-dimension carry over to the class of all induced subgraphs of Johnson graphs, and to the class of all induced subgraphs of Hamming graphs, respectively. It also follows that the VC-dimension of the set systems of \emph{closed neighbourhoods} in Johnson graphs and Hamming graphs is bounded. Johnson graphs and Hamming graphs are well known examples of distance transitive graphs. Neither of these graph classes is nowhere dense nor is there a bound on their (local) clique-width. Our results contrast this by giving evidence of structural tameness of the graph classes.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

A lower bound for the tree-width of planar graphs with vital linkages

The disjoint paths problem asks, given an graph G and k + 1 pairs of terminals (s_0,t_0), ...,(s_k,t_k), whether there are k+1 pairwise disjoint paths P_0, ...,P_k, such that P_i connects s_i to t_i. Robertson and Seymour have proven that the problem can be solved in polynomial time if k is fixed. Nevertheless, the constants involved are huge, and the algorithm is far from implementable. The algorithm uses a bound on the tree-width of graphs with vital linkages, and deletion of irrelevant vertices. We give single exponential lower bounds both for the tree-width of planar graphs with vital linkages, and for the size of the grid necessary for finding irrelevant vertices.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Nowhere dense graph classes, stability, and the independence property

A class of graphs is nowhere dense if for every integer r there is a finite upper bound on the size of cliques that occur as (topological) r-minors. We observe that this tameness notion from algorithmic graph theory is essentially the earlier stability theoretic notion of superflatness. For subgraph-closed classes of graphs we prove equivalence to stability and to not having the independence property.

0 citations0 reviewsNo code linkedOpen access