Publications - Current Year

We consider the problem of selecting a committee of $k$ alternatives among
$m$ alternatives, based on the ordinal rank list of voters. Our focus is on the
case where both voters and alternatives lie on a metric space-specifically, on
the line-and the objective is to minimize the additive social cost. The
additive social cost is the sum of the costs for all voters, where the cost for
each voter is defined as the sum of their distances to each member of the
selected committee.
We propose a new voting rule, the Polar Comparison Rule, which achieves upper
bounds of $1 + \sqrt{2} \approx 2.41$ and $7/3 \approx 2.33$ distortions for $k
= 2$ and $k = 3$, respectively, and we show that these bounds are tight.
Furthermore, we generalize this rule, showing that it maintains a distortion of
roughly $7/3$ based on the remainder of the committee size when divided by
three. We also establish lower bounds on the achievable distortion based on the
parity of $k$ and for both small and large committee sizes.

We consider the problem of selecting a committee of $k$ alternatives among
$m$ alternatives, based on the ordinal rank list of voters. Our focus is on the
case where both voters and alternatives lie on a metric space-specifically, on
the line-and the objective is to minimize the additive social cost. The
additive social cost is the sum of the costs for all voters, where the cost for
each voter is defined as the sum of their distances to each member of the
selected committee.
We propose a new voting rule, the Polar Comparison Rule, which achieves upper
bounds of $1 + \sqrt{2} \approx 2.41$ and $7/3 \approx 2.33$ distortions for $k
= 2$ and $k = 3$, respectively, and we show that these bounds are tight.
Furthermore, we generalize this rule, showing that it maintains a distortion of
roughly $7/3$ based on the remainder of the committee size when divided by
three. We also establish lower bounds on the achievable distortion based on the
parity of $k$ and for both small and large committee sizes.

A central result of Marx [ToC '10] proves that there are $k$-vertex graphs
$H$ of maximum degree $3$ such that $n^{o(k /\log k)}$ time algorithms for
detecting colorful $H$-subgraphs would refute the Exponential-Time Hypothesis
(ETH). This result is widely used to obtain almost-tight conditional lower
bounds for parameterized problems under ETH.
Our first contribution is a new and fully self-contained proof of this result
that further simplifies a recent work by Karthik et al. [SOSA 2024]. Towards
this end, we introduce a novel graph parameter, the linkage capacity
$\gamma(H)$, and show with an elementary proof that detecting colorful
$H$-subgraphs in time $n^{o(\gamma(H))}$ refutes ETH. Then, we use a simple
construction of communication networks credited to Bene\v{s} to obtain
$k$-vertex graphs of maximum degree $3$ and linkage capacity $\Omega(k / \log
k)$, avoiding the use of expander graphs. We also show that every graph $H$ of
treewidth $t$ has linkage capacity $\Omega(t / \log t)$, thus recovering the
stronger result of Marx [ToC '10] with a simplified proof.
Additionally, we obtain new tight lower bounds for certain types of patterns
by analyzing their linkage capacity. For example, we prove that almost all
$k$-vertex graphs of polynomial average degree $\Omega(k^{\beta})$ for some
$\beta > 0$ have linkage capacity $\Theta(k)$, which implies tight lower bounds
for such patterns $H$. As an application of these results, we also obtain tight
lower bounds for counting small induced subgraphs having a certain property
$\Phi$, improving bounds from [Roth et al., FOCS 2020].