7 citations · 26 across the 17 of their papers we have counts for
5 papers · 1 filter
Faster Property Testers in a Variation of the Bounded Degree Model
Isolde Adler, Polly Fahey
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…
On the tree-width of even-hole-free graphs
Pierre Aboulker, Isolde Adler, Eun Jung Kim +2
The class of all even-hole-free graphs has unbounded tree-width, as it contains all complete graphs. Recently, a class of (even-hole, )-free graphs was constructed, that still…
An explicit construction of graphs of bounded degree that are far from being Hamiltonian
Isolde Adler, Noleen Köhler
Hamiltonian cycles in graphs were first studied in the 1850s. Since then, an impressive amount of research has been dedicated to identifying classes of graphs that allow Hamiltonia…
On Testability of First-Order Properties in Bounded-Degree Graphs
Isolde Adler, Noleen Köhler, Pan Peng
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…
Vapnik-Chervonenkis Dimension and Density on Johnson and Hamming Graphs
Bjarki Geir Benediktsson, Dugald Macpherson, Isolde Adler
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…