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 study the problem of allocating a set of indivisible goods among a set of
agents with \emph{2-value additive valuations}. In this setting, each good is
valued either $1$ or $\sfrac{p}{q}$, for some fixed co-prime numbers $p,q\in
\NN$ such that $1\leq q < p$. Our goal is to find an allocation maximizing the
\emph{Nash social welfare} (\NSW), i.e., the geometric mean of the valuations
of the agents. In this work, we give a complete characterization of
polynomial-time tractability of \NSW\ maximization that solely depends on the
values of $q$.
We start by providing a rather simple polynomial-time algorithm to find a
maximum \NSW\ allocation when the valuation functions are \emph{integral}, that
is, $q=1$. We then exploit more involved techniques to get an algorithm
producing a maximum \NSW\ allocation for the \emph{half-integral} case, that
is, $q=2$. Finally, we show it is \classNP-hard to compute an allocation with
maximum \NSW\ whenever $q\geq3$.

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 study polynomial-time approximation algorithms for two closely-related
problems, namely computing shortcuts and transitive-closure spanners (TC
spanner). For a directed unweighted graph $G=(V, E)$ and an integer $d$, a set
of edges $E'\subseteq V\times V$ is called a $d$-TC spanner of $G$ if the graph
$H:=(V, E')$ has (i) the same transitive-closure as $G$ and (ii) diameter at
most $d.$ The set $E''\subseteq V\times V$ is a $d$-shortcut of $G$ if $E\cup
E''$ is a $d$-TC spanner of $G$. Our focus is on the following $(\alpha_D,
\alpha_S)$-approximation algorithm: given a directed graph $G$ and integers $d$
and $s$ such that $G$ admits a $d$-shortcut (respectively $d$-TC spanner) of
size $s$, find a $(d\alpha_D)$-shortcut (resp. $(d\alpha_D)$-TC spanner) with
$s\alpha_S$ edges, for as small $\alpha_S$ and $\alpha_D$ as possible.
As our main result, we show that, under the Projection Game Conjecture (PGC),
there exists a small constant $\epsilon>0$, such that no polynomial-time
$(n^{\epsilon},n^{\epsilon})$-approximation algorithm exists for finding
$d$-shortcuts as well as $d$-TC spanners of size $s$. Previously,
super-constant lower bounds were known only for $d$-TC spanners with constant
$d$ and ${\alpha_D}=1$ [Bhattacharyya, Grigorescu, Jung, Raskhodnikova,
Woodruff 2009]. Similar lower bounds for super-constant $d$ were previously
known only for a more general case of directed spanners [Elkin, Peleg 2000]. No
hardness of approximation result was known for shortcuts prior to our result.
As a side contribution, we complement the above with an upper bound of the
form $(n^{\gamma_D}, n^{\gamma_S})$-approximation which holds for $3\gamma_D +
2\gamma_S > 1$ (e.g., $(n^{1/5+o(1)}, n^{1/5+o(1)})$-approximation).

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].

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].