10 citations · 52 across the 22 of their papers we have counts for
Showing 2018Show all
3 papers · 1 filter
math.LO2018★ 5 cited
A separation theorem for simple theories
M. Malliaris, S. Shelah
This paper builds model-theoretic tools to detect changes in complexity among the simple theories. We develop a generalization of dividing, called shearing, which depends on a so-c…
cs.LG2018
Private PAC learning implies finite Littlestone dimension
Noga Alon, Roi Livni, Maryanthe Malliaris +1
We show that every approximately differentially private learning algorithm (possibly improper) for a class with Littlestone dimension~ requires exam…
math.LO2018★ 3 cited
An example of a new simple theory
M. Malliaris, S. Shelah
We construct a countable simple theory which, in Keisler's order, is strictly above the random graph (but "barely so") and also in some sense orthogonal to the building blocks of t…