Publications - Last Year

We consider the well-studied Robust $(k, z)$-Clustering problem, which
generalizes the classic $k$-Median, $k$-Means, and $k$-Center problems. Given a
constant $z\ge 1$, the input to Robust $(k, z)$-Clustering is a set $P$ of $n$
weighted points in a metric space $(M,\delta)$ and a positive integer $k$.
Further, each point belongs to one (or more) of the $m$ many different groups
$S_1,S_2,\ldots,S_m$. Our goal is to find a set $X$ of $k$ centers such that
$\max_{i \in [m]} \sum_{p \in S_i} w(p) \delta(p,X)^z$ is minimized.
This problem arises in the domains of robust optimization [Anthony, Goyal,
Gupta, Nagarajan, Math. Oper. Res. 2010] and in algorithmic fairness. For
polynomial time computation, an approximation factor of $O(\log m/\log\log m)$
is known [Makarychev, Vakilian, COLT $2021$], which is tight under a plausible
complexity assumption even in the line metrics. For FPT time, there is a
$(3^z+\epsilon)$-approximation algorithm, which is tight under GAP-ETH [Goyal,
Jaiswal, Inf. Proc. Letters, 2023].
Motivated by the tight lower bounds for general discrete metrics, we focus on
\emph{geometric} spaces such as the (discrete) high-dimensional Euclidean
setting and metrics of low doubling dimension, which play an important role in
data analysis applications. First, for a universal constant $\eta_0 >0.0006$,
we devise a $3^z(1-\eta_{0})$-factor FPT approximation algorithm for discrete
high-dimensional Euclidean spaces thereby bypassing the lower bound for general
metrics. We complement this result by showing that even the special case of
$k$-Center in dimension $\Theta(\log n)$ is $(\sqrt{3/2}- o(1))$-hard to
approximate for FPT algorithms. Finally, we complete the FPT approximation
landscape by designing an FPT $(1+\epsilon)$-approximation scheme (EPAS) for
the metric of sub-logarithmic doubling dimension.

We explore the fair distribution of a set of $m$ indivisible chores among $n$
agents, where each agent's costs are evaluated using a monotone cost function.
Our focus lies on two fairness criteria: envy-freeness up to any item (EFX) and
a relaxed notion, namely envy-freeness up to the transfer of any item (tEFX).
We demonstrate that a 2-approximate EFX allocation exists and is computable in
polynomial time for three agents with subadditive cost functions, improving
upon the previous $(2 + \sqrt{6})$ approximation for additive cost functions.
This result requires extensive case analysis. Christoforidis et al. (IJCAI'24)
independently claim the same approximation for additive cost functions;
however, we provide a counter-example to their algorithm. We expand the number
of agents to any number to get the same approximation guarantee with the
assumption of partially identical ordering (IDO) for the cost functions.
Additionally, we establish that a tEFX allocation is achievable for three
agents if one has an additive 2-ratio bounded cost function, while the others
may have general monotone cost functions. This is an improvement from the prior
requirement of two agents with additive 2-ratio bounded cost functions. This
allocation can also be extended to agent groups with identical valuations.
Further, we show various analyses of EFX allocations for chores, such as the
relaxations for additive $\alpha$-ratio-bounded cost functions.

We study the problem of fairly allocating indivisible goods to a set of
agents with additive leveled valuations. A valuation function is called leveled
if and only if bundles of larger size have larger value than bundles of smaller
size. The economics literature has well studied such valuations.
We use the maximin-share (MMS) and EFX as standard notions of fairness. We
show that an algorithm introduced by Christodoulou et al. ([11]) constructs an
allocation that is EFX and $\frac{\lfloor \frac{m}{n} \rfloor}{\lfloor
\frac{m}{n} \rfloor + 1}\text{-MMS}$. In the paper, it was claimed that the
allocation is EFX and $\frac{2}{3}\text{-MMS}$. However, the proof of the
MMS-bound is incorrect. We give a counter-example to their proof and then prove
a stronger approximation of MMS.

The Unbounded Subset Sum (USS) problem is an NP-hard computational problem
where the goal is to decide whether there exist non-negative integers $x_1,
\ldots, x_n$ such that $x_1 a_1 + \ldots + x_n a_n = b$, where $a_1 < \cdots <
a_n < b$ are distinct positive integers with $\text{gcd}(a_1, \ldots, a_n)$
dividing $b$. The problem can be solved in pseudopolynomial time, while
specialized cases, such as when $b$ exceeds the Frobenius number of $a_1,
\ldots, a_n$ simplify to a total problem where a solution always exists.
This paper explores the concept of totality in USS. The challenge in this
setting is to actually find a solution, even though we know its existence is
guaranteed. We focus on the instances of USS where solutions are guaranteed for
large $b$. We show that when $b$ is slightly greater than the Frobenius number,
we can find the solution to USS in polynomial time.
We then show how our results extend to Integer Programming with Equalities
(ILPE), highlighting conditions under which ILPE becomes total. We investigate
the diagonal Frobenius number, which is the appropriate generalization of the
Frobenius number to this context. In this setting, we give a polynomial-time
algorithm to find a solution of ILPE. The bound obtained from our algorithmic
procedure for finding a solution almost matches the recent existential bound of
Bach, Eisenbrand, Rothvoss, and Weismantel (2024).

The immense success of ML systems relies heavily on large-scale, high-quality
data. The high demand for data has led to many paradigms that involve selling,
exchanging, and sharing data, motivating the study of economic processes with
data as an asset. However, data differs from classical economic assets in terms
of free duplication: there is no concept of limited supply since it can be
replicated at zero marginal cost. This distinction introduces fundamental
differences between economic processes involving data and those concerning
other assets.
We study a parallel to exchange (Arrow-Debreu) markets where data is the
asset. Here, agents with datasets exchange data fairly and voluntarily, aiming
for mutual benefit without monetary compensation. This framework is
particularly relevant for non-profit organizations that seek to improve their
ML models through data exchange, yet are restricted from selling their data for
profit.
We propose a general framework for data exchange, built on two core
principles: (i) fairness, ensuring that each agent receives utility
proportional to their contribution to others; contributions are quantifiable
using standard credit-sharing functions like the Shapley value, and (ii)
stability, ensuring that no coalition of agents can identify an exchange among
themselves which they unanimously prefer to the current exchange. We show that
fair and stable exchanges exist for all monotone continuous utility functions.
Next, we investigate the computational complexity of finding approximate fair
and stable exchanges. We present a local search algorithm for instances with
monotone submodular utility functions, where each agent contributions are
measured using the Shapley value. We prove that this problem lies in CLS under
mild assumptions. Our framework opens up several intriguing theoretical
directions for research in data economics.

It is known since 1975 (\cite{HK75}) that maximum cardinality matchings in
bipartite graphs with $n$ nodes and $m$ edges can be computed in time
$O(\sqrt{n} m)$. Asymptotically faster algorithms were found in the last decade
and maximum cardinality bipartite matchings can now be computed in near-linear
time~\cite{NearlyLinearTimeBipartiteMatching,
AlmostLinearTimeMaxFlow,AlmostLinearTimeMinCostFlow}. For general graphs, the
problem seems harder. Algorithms with running time $O(\sqrt{n} m)$ were given
in~\cite{MV80,Vazirani94,Vazirani12,Vazirani20,Vazirani23,Goldberg-Karzanov,GT91,Gabow:GeneralMatching}.
Mattingly and Ritchey~\cite{Mattingly-Ritchey} and Huang and
Stein~\cite{Huang-Stein} discuss implementations of the Micali-Vazirani
Algorithm. We describe an implementation of Gabow's
algorithm~\cite{Gabow:GeneralMatching} in C++ based on
LEDA~\cite{LEDAsystem,LEDAbook} and report on running time experiments. On
worst-case graphs, the asymptotic improvement pays off dramatically. On random
graphs, there is no improvement with respect to algorithms that have a
worst-case running time of $O(n m)$. The performance seems to be near-linear.
The implementation is available open-source.

We prove a robust contraction decomposition theorem for $H$-minor-free
graphs, which states that given an $H$-minor-free graph $G$ and an integer $p$,
one can partition in polynomial time the vertices of $G$ into $p$ sets
$Z_1,\dots,Z_p$ such that $\operatorname{tw}(G/(Z_i \setminus Z')) = O(p +
|Z'|)$ for all $i \in [p]$ and $Z' \subseteq Z_i$. Here,
$\operatorname{tw}(\cdot)$ denotes the treewidth of a graph and $G/(Z_i
\setminus Z')$ denotes the graph obtained from $G$ by contracting all edges
with both endpoints in $Z_i \setminus Z'$.
Our result generalizes earlier results by Klein [SICOMP 2008] and Demaine et
al. [STOC 2011] based on partitioning $E(G)$, and some recent theorems for
planar graphs by Marx et al. [SODA 2022], for bounded-genus graphs (more
generally, almost-embeddable graphs) by Bandyapadhyay et al. [SODA 2022], and
for unit-disk graphs by Bandyapadhyay et al. [SoCG 2022].
The robust contraction decomposition theorem directly results in
parameterized algorithms with running time $2^{\widetilde{O}(\sqrt{k})} \cdot
n^{O(1)}$ or $n^{O(\sqrt{k})}$ for every vertex/edge deletion problems on
$H$-minor-free graphs that can be formulated as Permutation CSP Deletion or
2-Conn Permutation CSP Deletion. Consequently, we obtain the first
subexponential-time parameterized algorithms for Subset Feedback Vertex Set,
Subset Odd Cycle Transversal, Subset Group Feedback Vertex Set, 2-Conn
Component Order Connectivity on $H$-minor-free graphs. For other problems which
already have subexponential-time parameterized algorithms on $H$-minor-free
graphs (e.g., Odd Cycle Transversal, Vertex Multiway Cut, Vertex Multicut,
etc.), our theorem gives much simpler algorithms of the same running time.

Co-lex partial orders were recently introduced in (Cotumaccio et al., SODA
2021 and JACM 2023) as a powerful tool to index finite state automata, with
applications to regular expression matching. They generalize Wheeler orders
(Gagie et al., Theoretical Computer Science 2017) and naturally reflect the
co-lexicographic order of the strings labeling source-to-node paths in the
automaton. Briefly, the co-lex width $p$ of a finite-state automaton measures
how sortable its states are with respect to the co-lex order among the strings
they accept. Automata of co-lex width $p$ can be compressed to $O(\log p)$ bits
per edge and admit regular expression matching algorithms running in time
proportional to $p^2$ per matched character.
The deterministic co-lex width of a regular language $\mathcal L$ is the
smallest width of such a co-lex order, among all DFAs recognizing $\mathcal L$.
Since languages of small co-lex width admit efficient solutions to automata
compression and pattern matching, computing the co-lex width of a language is
relevant in these applications. The paper introducing co-lex orders determined
that the deterministic co-lex width $p$ of a language $\mathcal L$ can be
computed in time proportional to $m^{O(p)}$, given as input any DFA $\mathcal
A$ for $\mathcal L$, of size (number of transitions) $m =|\mathcal A|$.
In this paper, using new techniques, we show that it is possible to decide in
$O(m^p)$ time if the deterministic co-lex width of the language recognized by a
given minimum DFA is strictly smaller than some integer $p\ge 2$. We complement
this upper bound with a matching conditional lower bound based on the Strong
Exponential Time Hypothesis. The problem is known to be PSPACE-complete when
the input is an NFA (D'Agostino et al., Theoretical Computer Science 2023);
thus, together with that result, our paper essentially settles the complexity
of the problem.

We study dynamic $(1-\epsilon)$-approximate rounding of fractional matchings
-- a key ingredient in numerous breakthroughs in the dynamic graph algorithms
literature. Our first contribution is a surprisingly simple deterministic
rounding algorithm in bipartite graphs with amortized update time
$O(\epsilon^{-1} \log^2 (\epsilon^{-1} \cdot n))$, matching an (unconditional)
recourse lower bound of $\Omega(\epsilon^{-1})$ up to logarithmic factors.
Moreover, this algorithm's update time improves provided the minimum (non-zero)
weight in the fractional matching is lower bounded throughout. Combining this
algorithm with novel dynamic \emph{partial rounding} algorithms to increase
this minimum weight, we obtain several algorithms that improve this dependence
on $n$. For example, we give a high-probability randomized algorithm with
$\tilde{O}(\epsilon^{-1}\cdot (\log\log n)^2)$-update time against adaptive
adversaries. (We use Soft-Oh notation, $\tilde{O}$, to suppress polylogarithmic
factors in the argument, i.e., $\tilde{O}(f)=O(f\cdot \mathrm{poly}(\log f))$.)
Using our rounding algorithms, we also round known $(1-\epsilon)$-decremental
fractional bipartite matching algorithms with no asymptotic overhead, thus
improving on state-of-the-art algorithms for the decremental bipartite matching
problem. Further, we provide extensions of our results to general graphs and to
maintaining almost-maximal matchings.

We study online bipartite edge coloring, with nodes on one side of the graph
revealed sequentially. The trivial greedy algorithm is $(2-o(1))$-competitive,
which is optimal for graphs of low maximum degree, $\Delta=O(\log n)$ [BNMN
IPL'92]. Numerous online edge-coloring algorithms outperforming the greedy
algorithm in various settings were designed over the years (e.g., AGKM FOCS'03,
BMM SODA'10, CPW FOCS'19, BGW SODA'21, KLSST STOC'22, BSVW STOC'24), all
crucially relying on randomization. A commonly-held belief, first stated by
[BNMN IPL'92], is that randomization is necessary to outperform greedy.
Surprisingly, we refute this belief, by presenting a deterministic algorithm
that beats greedy for sufficiently large $\Delta=\Omega(\log n)$, and in
particular has competitive ratio $\frac{e}{e-1}+o(1)$ for all
$\Delta=\omega(\log n)$. We obtain our result via a new and surprisingly simple
randomized algorithm that works against adaptive adversaries (as opposed to
oblivious adversaries assumed by prior work), which implies the existence of a
similarly-competitive deterministic algorithm [BDBKTW STOC'90].

Given two matroids $\mathcal{M}_1$ and $\mathcal{M}_2$ over the same
$n$-element ground set, the matroid intersection problem is to find a largest
common independent set, whose size we denote by $r$. We present a simple and
generic auction algorithm that reduces $(1-\varepsilon)$-approximate matroid
intersection to roughly $1/\varepsilon^2$ rounds of the easier problem of
finding a maximum-weight basis of a single matroid. Plugging in known
primitives for this subproblem, we obtain both simpler and improved algorithms
in two models of computation, including:
* The first near-linear time/independence-query
$(1-\varepsilon)$-approximation algorithm for matroid intersection. Our
randomized algorithm uses $\tilde{O}(n/\varepsilon + r/\varepsilon^5)$
independence queries, improving upon the previous $\tilde{O}(n/\varepsilon +
r\sqrt{r}/{\varepsilon^3})$ bound of Quanrud (2024).
* The first sublinear exact parallel algorithms for weighted matroid
intersection, using $O(n^{2/3})$ rounds of rank queries or $O(n^{5/6})$ rounds
of independence queries. For the unweighted case, our results improve upon the
previous $O(n^{3/4})$-round rank-query and $O(n^{7/8})$-round
independence-query algorithms of Blikstad (2022).

Constrained Forest Problems (CFPs) as introduced by Goemans and Williamson in
1995 capture a wide range of network design problems with edge subsets as
solutions, such as Minimum Spanning Tree, Steiner Forest, and Point-to-Point
Connection. While individual CFPs have been studied extensively in individual
computational models, a unified approach to solving general CFPs in multiple
computational models has been lacking. Against this background, we present the
shell-decomposition algorithm, a model-agnostic meta-algorithm that efficiently
computes a $(2+\epsilon)$-approximation to CFPs for a broad class of forest
functions. To demonstrate the power and flexibility of this result, we
instantiate our algorithm for 3 fundamental, NP-hard CFPs in 3 different
computational models. For example, for constant $\epsilon$, we obtain the
following $(2+\epsilon)$-approximations in the Congest model:
1. For Steiner Forest specified via input components, where each node knows
the identifier of one of $k$ disjoint subsets of $V$, we achieve a
deterministic $(2+\epsilon)$-approximation in $O(\sqrt{n}+D+k)$ rounds, where
$D$ is the hop diameter of the graph.
2. For Steiner Forest specified via symmetric connection requests, where
connection requests are issued to pairs of nodes, we leverage randomized
equality testing to reduce the running time to $O(\sqrt{n}+D)$, succeeding with
high probability.
3. For Point-to-Point Connection, we provide a $(2+\epsilon)$-approximation
in $O(\sqrt{n}+D)$ rounds.
4. For Facility Placement and Connection, a relative of non-metric Facility
Location, we obtain a $(2+\epsilon)$-approximation in $O(\sqrt{n}+D)$ rounds.
We further show how to replace the $\sqrt{n}+D$ term by the complexity of
solving Partwise Aggregation, achieving (near-)universal optimality in any
setting in which a solution to Partwise Aggregation in near-shortcut-quality
time is known.

The task of min-plus matrix multiplication often arises in the context of
distances in graphs and is known to be fine-grained equivalent to the All-Pairs
Shortest Path problem. The non-crossing property of shortest paths in planar
graphs gives rise to Monge matrices; the min-plus product of $n\times n$ Monge
matrices can be computed in $O(n^2)$ time. Grid graphs arising in sequence
alignment problems, such as longest common subsequence or longest increasing
subsequence, are even more structured. Tiskin [SODA'10] modeled their behavior
using simple unit-Monge matrices and showed that the min-plus product of such
matrices can be computed in $O(n\log n)$ time. Russo [SPIRE'11] showed that the
min-plus product of arbitrary Monge matrices can be computed in time
$O((n+\delta)\log^3 n)$ parameterized by the core size $\delta$, which is
$O(n)$ for unit-Monge matrices.
In this work, we provide a linear bound on the core size of the product
matrix in terms of the core sizes of the input matrices and show how to solve
the core-sparse Monge matrix multiplication problem in $O((n+\delta)\log n)$
time, matching the result of Tiskin for simple unit-Monge matrices. Our
algorithm also allows $O(\log \delta)$-time witness recovery for any given
entry of the output matrix. As an application of this functionality, we show
that an array of size $n$ can be preprocessed in $O(n\log^3 n)$ time so that
the longest increasing subsequence of any sub-array can be reconstructed in
$O(l)$ time, where $l$ is the length of the reported subsequence; in
comparison, Karthik C. S. and Rahul [arXiv'24] recently achieved
$O(l+n^{1/2}\log^3 n)$-time reporting after $O(n^{3/2}\log^3 n)$-time
preprocessing. Our faster core-sparse Monge matrix multiplication also enabled
reducing two logarithmic factors in the running times of the recent algorithms
for edit distance with integer weights [Gorbachev & Kociumaka, arXiv'24].

For the vertex selection problem $(\sigma,\rho)$-DomSet one is given two
fixed sets $\sigma$ and $\rho$ of integers and the task is to decide whether we
can select vertices of the input graph, such that, for every selected vertex,
the number of selected neighbors is in $\sigma$ and, for every unselected
vertex, the number of selected neighbors is in $\rho$. This framework covers
Independent Set and Dominating Set for example.
We investigate the case when $\sigma$ and $\rho$ are periodic sets with the
same period $m\ge 2$, that is, the sets are two (potentially different) residue
classes modulo $m$. We study the problem parameterized by treewidth and present
an algorithm that solves in time $m^{tw} \cdot n^{O(1)}$ the decision,
minimization and maximization version of the problem. This significantly
improves upon the known algorithms where for the case $m \ge 3$ not even an
explicit running time is known. We complement our algorithm by providing
matching lower bounds which state that there is no $(m-\epsilon)^{pw} \cdot
n^{O(1)}$ unless SETH fails. For $m = 2$, we extend these bound to the
minimization version as the decision version is efficiently solvable.

We initiate the study of the following general clustering problem. We seek to
partition a given set $P$ of data points into $k$ clusters by finding a set $X$
of $k$ centers and assigning each data point to one of the centers. The cost of
a cluster, represented by a center $x\in X$, is a monotone, symmetric norm $f$
(inner norm) of the vector of distances of points assigned to $x$. The goal is
to minimize a norm $g$ (outer norm) of the vector of cluster costs. This
problem, which we call $(f,g)$-Clustering, generalizes many fundamental
clustering problems such as $k$-Center, $k$-Median , Min-Sum of Radii, and
Min-Load $k$-Clustering . A recent line of research (Chakrabarty, Swamy
[STOC'19]) studies norm objectives that are oblivious to the cluster structure
such as $k$-Median and $k$-Center. In contrast, our problem models
cluster-aware objectives including Min-Sum of Radii and Min-Load
$k$-Clustering.
Our main results are as follows. First, we design a constant-factor
approximation algorithm for $(\textsf{top}_\ell,\mathcal{L}_1)$-Clustering
where the inner norm ($\textsf{top}_\ell$) sums over the $\ell$ largest
distances. Second, we design a constant-factor approximation\ for
$(\mathcal{L}_\infty,\textsf{Ord})$-Clustering where the outer norm is a convex
combination of $\textsf{top}_\ell$ norms (ordered weighted norm).

In this paper, we study the problem of finding an envy-free allocation of
indivisible goods among multiple agents. EFX, which stands for envy-freeness up
to any good, is a well-studied relaxation of the envy-free allocation problem
and has been shown to exist for specific scenarios. For instance, EFX is known
to exist when there are only three agents [Chaudhury et al, EC 2020], and for
any number of agents when there are only two types of valuations [Mahara,
Discret. Appl. Math 2023].
We show that EFX allocations exist for any number of agents when there are at
most three types of additive valuations.

Lagarias and Odlyzko (J.~ACM~1985) proposed a polynomial time algorithm for
solving ``\emph{almost all}'' instances of the Subset Sum problem with $n$
integers of size $\Omega(\Gamma_{\text{LO}})$, where
$\log_2(\Gamma_{\text{LO}}) > n^2 \log_2(\gamma)$ and $\gamma$ is a parameter
of the lattice basis reduction ($\gamma > \sqrt{4/3}$ for LLL). The algorithm
of Lagarias and Odlyzko is a cornerstone result in cryptography. However, the
theoretical guarantee on the density of feasible instances has remained
unimproved for almost 40 years.
In this paper, we propose an algorithm to solve ``almost all'' instances of
Subset Sum with integers of size $\Omega(\sqrt{\Gamma_{\text{LO}}})$ after a
single call to the lattice reduction. Additionally, our argument allows us to
solve the Subset Sum problem for multiple targets while the previous approach
could only answer one target per call to lattice basis reduction. We introduce
a modular arithmetic approach to the Subset Sum problem. The idea is to use the
lattice reduction to solve a linear system modulo a suitably large prime. We
show that density guarantees can be improved, by analysing the lengths of the
LLL reduced basis vectors, of both the primal and the dual lattices
simultaneously.

A set of $m$ indivisible goods is to be allocated to a set of $n$ agents.
Each agent $i$ has an additive valuation function $v_i$ over goods. The value
of a good $g$ for agent $i$ is either $1$ or $s$, where $s$ is a fixed rational
number greater than one, and the value of a bundle of goods is the sum of the
values of the goods in the bundle. An \emph{allocation} $X$ is a partition of
the goods into bundles $X_1$, \ldots, $X_n$, one for each agent. The \emph{Nash
Social Welfare} ($\NSW$) of an allocation $X$ is defined as \[ \NSW(X) = \left(
\prod_i v_i(X_i) \right)^{\sfrac{1}{n}}.\] The \emph{$\NSW$-allocation}
maximizes the Nash Social Welfare. In~\cite{NSW-twovalues-halfinteger} it was
shown that the $\NSW$-allocation can be computed in polynomial time, if $s$ is
an integer or a half-integer, and that the problem is NP-complete otherwise.
The proof for the half-integer case is quite involved. In this note we give a
simpler and shorter proof

A binary code Enc$:\{0,1\}^k \to \{0,1\}^n$ is $(0.5-\epsilon,L)$-list
decodable if for all $w \in \{0,1\}^n$, the set List$(w)$ of all messages $m
\in \{0,1\}^k$ such that the relative Hamming distance between Enc$(m)$ and $w$
is at most $0.5 -\epsilon$, has size at most $L$. Informally, a $q$-query local
list-decoder for Enc is a randomized procedure Dec$:[k]\times [L] \to \{0,1\}$
that when given oracle access to a string $w$, makes at most $q$ oracle calls,
and for every message $m \in \text{List}(w)$, with high probability, there
exists $j \in [L]$ such that for every $i \in [k]$, with high probability,
Dec$^w(i,j)=m_i$.
We prove lower bounds on $q$, that apply even if $L$ is huge (say
$L=2^{k^{0.9}}$) and the rate of Enc is small (meaning that $n \ge 2^{k}$):
1. For $\epsilon \geq 1/k^{\nu}$ for some universal constant $0< \nu < 1$, we
prove a lower bound of $q=\Omega(\frac{\log(1/\delta)}{\epsilon^2})$, where
$\delta$ is the error probability of the local list-decoder. This bound is
tight as there is a matching upper bound by Goldreich and Levin (STOC 1989) of
$q=O(\frac{\log(1/\delta)}{\epsilon^2})$ for the Hadamard code (which has
$n=2^k$). This bound extends an earlier work of Grinberg, Shaltiel and Viola
(FOCS 2018) which only works if $n \le 2^{k^{\gamma}}$ for some universal
constant $0<\gamma <1$, and the number of coins tossed by Dec is small (and
therefore does not apply to the Hadamard code, or other codes with low rate).
2. For smaller $\epsilon$, we prove a lower bound of roughly $q =
\Omega(\frac{1}{\sqrt{\epsilon}})$. To the best of our knowledge, this is the
first lower bound on the number of queries of local list-decoders that gives $q
\ge k$ for small $\epsilon$.
We also prove black-box limitations for improving some of the parameters of
the Goldreich-Levin hard-core predicate construction.

The traveling salesman (or salesperson) problem, short TSP, is a problem of
strong interest to many researchers from mathematics, economics, and computer
science. Manifold TSP variants occur in nearly every scientific field and
application domain: engineering, physics, biology, life sciences, and
manufacturing just to name a few. Several thousand papers are published on
theoretical research or application-oriented results each year. This paper
provides the first systematic survey on the best currently known
approximability and inapproximability results for well-known TSP variants such
as the "standard" TSP, Path TSP, Bottleneck TSP, Maximum Scatter TSP,
Generalized TSP, Clustered TSP, Traveling Purchaser Problem, Profitable Tour
Problem, Quota TSP, Prize-Collecting TSP, Orienteering Problem, Time-dependent
TSP, TSP with Time Windows, and the Orienteering Problem with Time Windows. The
foundation of our survey is the definition scheme T3CO, which we propose as a
uniform, easy-to-use and extensible means for the formal and precise definition
of TSP variants. Applying T3CO to formally define the variant studied by a
paper reveals subtle differences within the same named variant and also brings
out the differences between the variants more clearly. We achieve the first
comprehensive, concise, and compact representation of approximability results
by using T3CO definitions. This makes it easier to understand the
approximability landscape and the assumptions under which certain results hold.
Open gaps become more evident and results can be compared more easily.