ABSTRACT. The abstract of the talk can be found in the PDF file as requested.

ABSTRACT. Non-clashing teaching, introduced by Kirkpatrick et al. [ALT 2019] and Fallat et al. [JMLR 2023], is the most efficient batch machine teaching model satisfying the collusion-avoidance benchmark of Goldman and Mathias [COLT 1993]. In the past few years, (positive) non-clashing teaching for the concept class of balls in graphs has been thoroughly studied, yielding numerous algorithmic and combinatorial results. This concept class also exhibits broad generality, as any finite binary concept class can be equivalently represented by a set of closed neighborhoods in a graph. In this talk, I will survey the complexity landscape of non-clashing teaching in graphs. I will present some of our recent results, including near-tight running time upper and lower bounds for general graphs, parameterized algorithmic and hardness results, and combinatorial bounds for broader graph classes.

ABSTRACT. Gerrymandering, the process of deliberately redistricting via manipulation of boundaries to favor a chosen candidate, is a recurring issue in elections. A standard setting to model voting is when voters and ballot boxes are located in $\mathbb{R}^2$, distances are computed using $\ell_2$-norm, the voting rule is plurality and each voter is assigned to vote at the opened ballot box nearest to them. Eiben et al. [AAAI '20] designed an optimal algorithm for the question where given a set $\mathcal{B}$ of $m$ ballot box locations and a set $\mathcal{V}$ of $n$ voters with known preferences over a set of candidates $\mathcal{C}$, the computational question is to decide if some $k$ ballot boxes can be opened from $\mathcal{B}$ such that a chosen candidate from $\mathcal{C}$ wins in at least $\ell$ of these ballot boxes? Gerrymandering seeks to exploit the fact that \emph{``all ballot boxes are equal"}, i.e., it doesn't matter how few voters voted at a ballot box or how small was the margin of victory as long as your chosen candidate wins. This is reflected in the lower bound construction of Eiben et al. [AAAI '20] where one ballot box gets only 9 votes while another ballot box has more than $(3/4)$-fraction of the $2^{O(k)}$ voters voting in it. In this paper, we study the question of how the complexity of Gerrymandering changes if we enforce a fairness condition that any two opened ballot boxes cannot have a big difference in how many voters are voting in them? Formally, given any integer $\beta\geq 1$, the \fgm problem has the additional condition that the ratio of the number of voters voting in any two of the opened ballot boxes is at most $\beta$. We completely resolve the complexity of \fgm by: \begin{itemize} \item Designing an algorithm running in $(m+n)^{\beta\cdot |\mathcal{C}|\cdot O (\sqrt{k})}$ time \item Obtaining a lower bound that there is no $f(k,n)\cdot m^{o(\sqrt{k})}$ time algorithm (for any computable function $f$) under the Exponential Time Hypothesis (ETH) even when $|\mathcal{C}|=2$. \end{itemize} Our lower bound construction is able to reduce the number of voters $n$ to be $\text{poly}(k)$ whereas Eiben et al. [AAAI '20] required it to be $\text{exp}(k)$.