Sandra Zilles
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Sandra Zilles has a total of 26 co-authors. Here are the top co-authors by number of shared publications:
- Boting Yang
University of Regina
5 shared publications - Hans Ulrich Simon
Faculty of Mathematics Ruhr-University Bochum Germany
4 shared publications - Ziyuan Gao
University of Regina
4 shared publications - Yuan Xue
Univ Regina, Dept Comp Sci, Regina, SK S4S0A2, Canada
3 shared publications Ashwani Kumar
University of Regina
2 shared publications- Farnam Mansouri
David R. Cheriton School of Computer Science University of Waterloo Waterloo ON Canada
2 shared publications
Latest Publications
- Open Access
The Computational Complexity of Almost Stable Clustering with Penalties
We investigate the complexity of stable (or perturbation-resilient) instances of $\mathrm{k-M\small{EANS}}$ and $\mathrm{k-M\small{EDIAN}}$ clustering problems in metrics with small doubling dimension. While these problems have been extensively studied under multiplicative perturbation resilience in low-dimensional Euclidean spaces (e.g., (Friggstad et al., 2019; Cohen-Addad and Schwiegelshohn, 2017)), we adopt a more general notion of stability, termed ``almost stable'', which is closer to the notion of $(α, \varepsilon)$-perturbation resilience introduced by Balcan and Liang (2016). Additionally, we extend our results to $\mathrm{k-M\small{EANS}}$/$\mathrm{k-M\small{EDIAN}}$ with penalties, where each data point is either assigned to a cluster centre or incurs a penalty. We show that certain special cases of almost stable $\mathrm{k-M\small{EANS}}$/$\mathrm{k-M\small{EDIAN}}$ (with penalties) are solvable in polynomial time. To complement this, we also examine the hardness of almost stable instances and $(1 + \frac{1}{poly(n)})$-stable instances of $\mathrm{k-M\small{EANS}}$/$\mathrm{k-M\small{EDIAN}}$ (with penalties), proving super-polynomial lower bounds on the runtime of any exact algorithm under the widely believed Exponential Time Hypothesis (ETH).Open AccessThe Computational Complexity of Almost Stable Clustering with Penalties
We investigate the complexity of stable (or perturbation-resilient) instances of $\mathrm{k-M\small{EANS}}$ and $\mathrm{k-M\small{EDIAN}}$ clustering problems in metrics with small doubling dimension. While these problems have been extensively studied under multiplicative perturbation resilience in low-dimensional Euclidean spaces (e.g., (Friggstad et al., 2019; Cohen-Addad and Schwiegelshohn, 2017)), we adopt a more general notion of stability, termed ``almost stable'', which is closer to the notion of $(α, \varepsilon)$-perturbation resilience introduced by Balcan and Liang (2016). Additionally, we extend our results to $\mathrm{k-M\small{EANS}}$/$\mathrm{k-M\small{EDIAN}}$ with penalties, where each data point is either assigned to a cluster centre or incurs a penalty. We show that certain special cases of almost stable $\mathrm{k-M\small{EANS}}$/$\mathrm{k-M\small{EDIAN}}$ (with penalties) are solvable in polynomial time. To complement this, we also examine the hardness of almost stable instances and $(1 + \frac{1}{poly(n)})$-stable instances of $\mathrm{k-M\small{EANS}}$/$\mathrm{k-M\small{EDIAN}}$ (with penalties), proving super-polynomial lower bounds on the runtime of any exact algorithm under the widely believed Exponential Time Hypothesis (ETH). - Open Access
Formal Models of Active Learning from Contrastive Examples
Machine learning can greatly benefit from providing learning algorithms with pairs of contrastive training examples -- typically pairs of instances that differ only slightly, yet have different class labels. Intuitively, the difference in the instances helps explain the difference in the class labels. This paper proposes a theoretical framework in which the effect of various types of contrastive examples on active learners is studied formally. The focus is on the sample complexity of learning concept classes and how it is influenced by the choice of contrastive examples. We illustrate our results with geometric concept classes and classes of Boolean functions. Interestingly, we reveal a connection between learning from contrastive examples and the classical model of self-directed learning.
Open AccessFormal Models of Active Learning from Contrastive Examples
Machine learning can greatly benefit from providing learning algorithms with pairs of contrastive training examples -- typically pairs of instances that differ only slightly, yet have different class labels. Intuitively, the difference in the instances helps explain the difference in the class labels. This paper proposes a theoretical framework in which the effect of various types of contrastive examples on active learners is studied formally. The focus is on the sample complexity of learning concept classes and how it is influenced by the choice of contrastive examples. We illustrate our results with geometric concept classes and classes of Boolean functions. Interestingly, we reveal a connection between learning from contrastive examples and the classical model of self-directed learning.
- 5 June 2024
- Published by Elsevier in Theoretical Computer Science
- Vol. 1007
The zero-visibility cops and robber game on graph products
- 5 June 2024
- Published by Elsevier in Theoretical Computer Science
- Vol. 1007
The zero-visibility cops and robber game on graph products
- 19 March 2023
- Published by Springer Nature in Journal of Combinatorial Optimization
- Vol. 45 (3) , 1-22
Fast searching on cactus graphs
- 19 March 2023
- Published by Springer Nature in Journal of Combinatorial Optimization
- Vol. 45 (3) , 1-22
Fast searching on cactus graphs
- 18 September 2022
- Published by Springer Nature
- p. 394-405
Fast Searching on k-Combinable Graphs
- 30 September 2021
- Published by Springer Nature
- Vol. 2381, 217-223
Machine Learning to Identify Gene Interactions from High-Throughput Mutant Crosses
Advances in molecular genetics through high-throughput gene mutagenesis and genetic crossing have enabled gene interaction mapping across whole genomes. Detecting gene interactions in even small microbial genomes relies on measuring growth phenotypes in thousands of crossed strains followed by statistical analysis to compare single and double mutants. The preferred computational approach is to use a multiplicative model that factors phenotype scores of single gene mutants to identify gene interactions in double mutants. Here we present how machine learning models that consider the characteristics of the phenotypic data improve on the classical multiplicative model. Importantly, machine learning improves the selection of cutoff values to identify gene interactions from phenotypic scores.
- 30 September 2021
- Published by Springer Nature
- Vol. 2381, 217-223
Machine Learning to Identify Gene Interactions from High-Throughput Mutant Crosses
Advances in molecular genetics through high-throughput gene mutagenesis and genetic crossing have enabled gene interaction mapping across whole genomes. Detecting gene interactions in even small microbial genomes relies on measuring growth phenotypes in thousands of crossed strains followed by statistical analysis to compare single and double mutants. The preferred computational approach is to use a multiplicative model that factors phenotype scores of single gene mutants to identify gene interactions in double mutants. Here we present how machine learning models that consider the characteristics of the phenotypic data improve on the classical multiplicative model. Importantly, machine learning improves the selection of cutoff values to identify gene interactions from phenotypic scores.
- 17 February 2021
- Published by Springer Nature in Journal of Combinatorial Optimization
- Vol. 43 (5) , 1545-1570
A simple method for proving lower bounds in the zero-visibility cops and robber game
- 17 February 2021
- Published by Springer Nature in Journal of Combinatorial Optimization
- Vol. 43 (5) , 1545-1570
A simple method for proving lower bounds in the zero-visibility cops and robber game
- Open Access
Optimal Collusion-Free Teaching
Formal models of learning from teachers need to respect certain criteria to avoid collusion. The most commonly accepted notion of collusion-freeness was proposed by Goldman and Mathias (1996), and various teaching models obeying their criterion have been studied. For each model $M$ and each concept class $\mathcal{C}$, a parameter $M$-$\mathrm{TD}(\mathcal{C})$ refers to the teaching dimension of concept class $\mathcal{C}$ in model $M$---defined to be the number of examples required for teaching a concept, in the worst case over all concepts in $\mathcal{C}$. This paper introduces a new model of teaching, called no-clash teaching, together with the corresponding parameter $\mathrm{NCTD}(\mathcal{C})$. No-clash teaching is provably optimal in the strong sense that, given any concept class $\mathcal{C}$ and any model $M$ obeying Goldman and Mathias's collusion-freeness criterion, one obtains $\mathrm{NCTD}(\mathcal{C})\le M$-$\mathrm{TD}(\mathcal{C})$. We also study a corresponding notion $\mathrm{NCTD}^+$ for the case of learning from positive data only, establish useful bounds on $\mathrm{NCTD}$ and $\mathrm{NCTD}^+$, and discuss relations of these parameters to the VC-dimension and to sample compression. In addition to formulating an optimal model of collusion-free teaching, our main results are on the computational complexity of deciding whether $\mathrm{NCTD}^+(\mathcal{C})=k$ (or $\mathrm{NCTD}(\mathcal{C})=k$) for given $\mathcal{C}$ and $k$. We show some such decision problems to be equivalent to the existence question for certain constrained matchings in bipartite graphs. Our NP-hardness results for the latter are of independent interest in the study of constrained graph matchings.Open AccessOptimal Collusion-Free Teaching
Formal models of learning from teachers need to respect certain criteria to avoid collusion. The most commonly accepted notion of collusion-freeness was proposed by Goldman and Mathias (1996), and various teaching models obeying their criterion have been studied. For each model $M$ and each concept class $\mathcal{C}$, a parameter $M$-$\mathrm{TD}(\mathcal{C})$ refers to the teaching dimension of concept class $\mathcal{C}$ in model $M$---defined to be the number of examples required for teaching a concept, in the worst case over all concepts in $\mathcal{C}$. This paper introduces a new model of teaching, called no-clash teaching, together with the corresponding parameter $\mathrm{NCTD}(\mathcal{C})$. No-clash teaching is provably optimal in the strong sense that, given any concept class $\mathcal{C}$ and any model $M$ obeying Goldman and Mathias's collusion-freeness criterion, one obtains $\mathrm{NCTD}(\mathcal{C})\le M$-$\mathrm{TD}(\mathcal{C})$. We also study a corresponding notion $\mathrm{NCTD}^+$ for the case of learning from positive data only, establish useful bounds on $\mathrm{NCTD}$ and $\mathrm{NCTD}^+$, and discuss relations of these parameters to the VC-dimension and to sample compression. In addition to formulating an optimal model of collusion-free teaching, our main results are on the computational complexity of deciding whether $\mathrm{NCTD}^+(\mathcal{C})=k$ (or $\mathrm{NCTD}(\mathcal{C})=k$) for given $\mathcal{C}$ and $k$. We show some such decision problems to be equivalent to the existence question for certain constrained matchings in bipartite graphs. Our NP-hardness results for the latter are of independent interest in the study of constrained graph matchings. - 21 May 2018
- Published by Springer Nature in Algorithmica
- Vol. 80 (12) , 3959-3981
The Fast Search Number of a Complete k-Partite Graph
- 21 May 2018
- Published by Springer Nature in Algorithmica
- Vol. 80 (12) , 3959-3981
The Fast Search Number of a Complete k-Partite Graph
- 1 March 2018
- Published by Elsevier in Theoretical Computer Science
- Vol. 716, 107-123
On the teaching complexity of linear sets
- 1 March 2018
- Published by Elsevier in Theoretical Computer Science
- Vol. 716, 107-123
On the teaching complexity of linear sets