
We study the 2ary constraint satisfaction problems (2CSPs), which can be
stated as follows: given a constraint graph $G=(V,E)$, an alphabet set $\Sigma$
and, for each $\{u, v\}\in E$, a constraint $C_{uv} \subseteq
\Sigma\times\Sigma$, the goal is to find an assignment $\sigma: V \to \Sigma$
that satisfies as many constraints as possible, where a constraint $C_{uv}$ is
satisfied if $(\sigma(u),\sigma(v))\in C_{uv}$.
While the approximability of 2CSPs is quite well understood when $\Sigma$
is constant, many problems are still open when $\Sigma$ becomes super
constant. One such problem is whether it is hard to approximate 2CSPs to
within a polynomial factor of $\Sigma V$. Bellare et al. (1993) suggested
that the answer to this question might be positive. Alas, despite efforts to
resolve this conjecture, it remains open to this day.
In this work, we separate $V$ and $\Sigma$ and ask a related but weaker
question: is it hard to approximate 2CSPs to within a polynomial factor of
$V$ (while $\Sigma$ may be superpolynomial in $V$)? Assuming the
exponential time hypothesis (ETH), we answer this question positively by
showing that no polynomial time algorithm can approximate 2CSPs to within a
factor of $V^{1  o(1)}$. Note that our ratio is almost linear, which is
almost optimal as a trivial algorithm gives a $V$approximation for 2CSPs.
Thanks to a known reduction, our result implies an ETHhardness of
approximating Directed Steiner Network with ratio $k^{1/4  o(1)}$ where $k$ is
the number of demand pairs. The ratio is roughly the square root of the best
known ratio achieved by polynomial time algorithms (Chekuri et al., 2011;
Feldman et al., 2012).
Additionally, under GapETH, our reduction for 2CSPs not only rules out
polynomial time algorithms, but also FPT algorithms parameterized by $V$.
Similar statement applies for DSN parameterized by $k$.

The logdensity method is a powerful algorithmic framework which in recent
years has given rise to the bestknown approximations for a variety of
problems, including Densest$k$Subgraph and Bipartite Small Set Vertex
Expansion. These approximations have been conjectured to be optimal based on
various instantiations of a general conjecture: that it is hard to distinguish
a fully random combinatorial structure from one which contains a similar
planted substructure with the same "logdensity".
We bolster this conjecture by showing that in a random hypergraph with edge
probability $n^{\alpha}$, $\tilde\Omega(\log n)$ rounds of SheraliAdams with
cannot rule out the existence of a $k$subhypergraph with edge density
$k^{\alphao(1)}$, for any $k$ and $\alpha$. This holds even when the bound on
the objective function is lifted. This gives strong integrality gaps which
exactly match the gap in the above distinguishing problems, as well as the
bestknown approximations, for Densest $k$Subgraph, Smallest $p$Edge
Subgraph, their hypergraph extensions, and Small Set Bipartite Vertex Expansion
(or equivalently, Minimum $p$Union). Previously, such integrality gaps were
known only for Densest $k$Subgraph for one specific parameter setting.

We study the parameterized complexity of approximating the $k$Dominating Set
(DomSet) problem where an integer $k$ and a graph $G$ on $n$ vertices are given
as input, and the goal is to find a dominating set of size at most $F(k) \cdot
k$ whenever the graph $G$ has a dominating set of size $k$. When such an
algorithm runs in time $T(k) \cdot poly(n)$ (i.e., FPTtime) for some
computable function $T$, it is said to be an $F(k)$FPTapproximation algorithm
for $k$DomSet. We prove the following for every computable functions $T, F$
and every constant $\varepsilon > 0$:
$\bullet$ Assuming $W[1]\neq FPT$, there is no $F(k)$FPTapproximation
algorithm for $k$DomSet.
$\bullet$ Assuming the Exponential Time Hypothesis (ETH), there is no
$F(k)$approximation algorithm for $k$DomSet that runs in $T(k) \cdot
n^{o(k)}$ time.
$\bullet$ Assuming the Strong Exponential Time Hypothesis (SETH), for every
integer $k \geq 2$, there is no $F(k)$approximation algorithm for $k$DomSet
that runs in $T(k) \cdot n^{k  \varepsilon}$ time.
$\bullet$ Assuming the $k$Sum Hypothesis, for every integer $k \geq 3$,
there is no $F(k)$approximation algorithm for $k$DomSet that runs in $T(k)
\cdot n^{\lceil k/2 \rceil  \varepsilon}$ time.
Our results are obtained by establishing a connection between communication
complexity and hardness of approximation, generalizing the ideas from a recent
breakthrough work of Abboud et al. [FOCS 2017]. Specifically, we show that to
prove hardness of approximation of a certain parameterized variant of the label
cover problem, it suffices to devise a specific protocol for a communication
problem that depends on which hypothesis we rely on. Each of these
communication problems turns out to be either a well studied problem or a
variant of one; this allows us to easily apply known techniques to solve them.

We study the problem of deleting the smallest set $S$ of vertices (resp.\
edges) from a given graph $G$ such that the induced subgraph (resp.\ subgraph)
$G \setminus S$ belongs to some class $\mathcal{H}$.
We consider the case where graphs in $\mathcal{H}$ have treewidth bounded by
$t$, and give a general framework to obtain approximation algorithms for both
vertex and edgedeletion settings from approximation algorithms for certain
natural graph partitioning problems called $k$Subset Vertex Separator and
$k$Subset Edge Separator, respectively.
For the vertex deletion setting, our framework combined with the current best
result for $k$Subset Vertex Separator, yields a significant improvement in the
approximation ratios for basic problems such as $k$Treewidth Vertex Deletion
and Planar$F$ Vertex Deletion. Our algorithms are simpler than previous works
and give the first uniform approximation algorithms under the natural
parameterization.
For the edge deletion setting, we give improved approximation algorithms for
$k$Subset Edge Separator combining ideas from LP relaxations and important
separators. We present their applications in boundeddegree graphs, and also
give an APXhardness result for the edge deletion problems.

The $k$Even Set problem is a parameterized variant of the Minimum Distance
Problem of linear codes over $\mathbb F_2$, which can be stated as follows:
given a generator matrix $\mathbf A$ and an integer $k$, determine whether the
code generated by $\mathbf A$ has distance at most $k$. Here, $k$ is the
parameter of the problem. The question of whether $k$Even Set is fixed
parameter tractable (FPT) has been repeatedly raised in literature and has
earned its place in Downey and Fellows' book (2013) as one of the "most
infamous" open problems in the field of Parameterized Complexity.
In this work, we show that $k$Even Set does not admit FPT algorithms under
the (randomized) Gap Exponential Time Hypothesis (GapETH) [Dinur'16,
ManurangsiRaghavendra'16]. In fact, our result rules out not only exact FPT
algorithms, but also any constant factor FPT approximation algorithms for the
problem. Furthermore, our result holds even under the following weaker
assumption, which is also known as the Parameterized Inapproximability
Hypothesis (PIH) [Lokshtanov et al.'17]: no (randomized) FPT algorithm can
distinguish a satisfiable 2CSP instance from one which is only
$0.99$satisfiable (where the parameter is the number of variables).
We also consider the parameterized $k$Shortest Vector Problem (SVP), in
which we are given a lattice whose basis vectors are integral and an integer
$k$, and the goal is to determine whether the norm of the shortest vector (in
the $\ell_p$ norm for some fixed $p$) is at most $k$. Similar to $k$Even Set,
this problem is also a longstanding open problem in the field of Parameterized
Complexity. We show that, for any $p > 1$, $k$SVP is hard to approximate (in
FPT time) to some constant factor, assuming PIH. Furthermore, for the case of
$p = 2$, the inapproximability factor can be amplified to any constant.

The Directed Steiner Network (DSN) problem takes as input a directed
edgeweighted graph $G=(V,E)$ and a set $\mathcal{D}\subseteq V\times V$ of $k$
demand pairs. The aim is to compute the cheapest network $N\subseteq G$ for
which there is an $s\to t$ path for each $(s,t)\in\mathcal{D}$. It is known
that this problem is notoriously hard as there is no
$k^{1/4o(1)}$approximation algorithm under GapETH, even when parametrizing
the runtime by $k$ [Dinur & Manurangsi, ITCS 2018]. In light of this, we
systematically study several special cases of DSN and determine their
parameterized approximability for the parameter $k$.
For the biDSN$_\text{Planar}$ problem, the aim is to compute a planar
optimum solution $N\subseteq G$ in a bidirected graph $G$, i.e., for every edge
$uv$ of $G$ the reverse edge $vu$ exists and has the same weight. This problem
is a generalization of several wellstudied special cases. Our main result is
that this problem admits a parameterized approximation scheme (PAS) for $k$. We
also prove that our result is tight in the sense that (a) the runtime of our
PAS cannot be significantly improved, and (b) it is unlikely that a PAS exists
for any generalization of biDSN$_\text{Planar}$, unless FPT=W[1].
One important special case of DSN is the Strongly Connected Steiner Subgraph
(SCSS) problem, for which the solution network $N\subseteq G$ needs to strongly
connect a given set of $k$ terminals. It has been observed before that for SCSS
a parameterized $2$approximation exists when parameterized by $k$ [Chitnis et
al., IPEC 2013]. We give a tight inapproximability result by showing that for
$k$ no parameterized $(2\varepsilon)$approximation algorithm exists under
GapETH. Additionally we show that when restricting the input of SCSS to
bidirected graphs, the problem remains NPhard but becomes FPT for $k$.

Consider the following asynchronous, opportunistic communication model over a
graph $G$: in each round, one edge is activated uniformly and independently at
random and (only) its two endpoints can exchange messages and perform local
computations. Under this model, we study the following random process: The
first time a vertex is an endpoint of an active edge, it chooses a random
number, say $\pm 1$ with probability $1/2$; then, in each round, the two
endpoints of the currently active edge update their values to their average. We
show that, if $G$ exhibits a twocommunity structure (for example, two
expanders connected by a sparse cut), the values held by the nodes will
collectively reflect the underlying community structure over a suitable phase
of the above process, allowing efficient and effective recovery in important
cases.
In more detail, we first provide a firstmoment analysis showing that, for a
large class of almostregular clustered graphs that includes the stochastic
block model, the expected values held by all but a negligible fraction of the
nodes eventually reflect the underlying cut signal. We prove this property
emerges after a mixing period of length $\mathcal O(n\log n)$. We further
provide a secondmoment analysis for a more restricted class of regular
clustered graphs that includes the regular stochastic block model. For this
case, we are able to show that most nodes can efficiently and locally identify
their community of reference over a suitable time window. This results in the
first opportunistic protocols that approximately recover community structure
using only polylogarithmic work per node. Even for the above class of regular
graphs, our second moment analysis requires new concentration bounds on the
product of certain random matrices that are technically challenging and
possibly of independent interest.

We study the problem of finding a small subset of items that is
\emph{agreeable} to all agents, meaning that all agents value the subset at
least as much as its complement. Previous work has shown worstcase bounds,
over all instances with a given number of agents and items, on the number of
items that may need to be included in such a subset. Our goal in this paper is
to efficiently compute an agreeable subset whose size approximates the size of
the smallest agreeable subset for a given instance. We consider three
wellknown models for representing the preferences of the agents: ordinal
preferences on single items, the value oracle model, and additive utilities. In
each of these models, we establish virtually tight bounds on the approximation
ratio that can be obtained by algorithms running in polynomial time.

We consider questions that arise from the intersection between the areas of
polynomialtime approximation algorithms, subexponentialtime algorithms, and
fixedparameter tractable algorithms. The questions, which have been asked
several times (e.g., [Marx08, FGMS12, DF13]), are whether there is a
nontrivial FPTapproximation algorithm for the Maximum Clique (Clique) and
Minimum Dominating Set (DomSet) problems parameterized by the size of the
optimal solution. In particular, letting $\text{OPT}$ be the optimum and $N$ be
the size of the input, is there an algorithm that runs in
$t(\text{OPT})\text{poly}(N)$ time and outputs a solution of size
$f(\text{OPT})$, for any functions $t$ and $f$ that are independent of $N$ (for
Clique, we want $f(\text{OPT})=\omega(1)$)?
In this paper, we show that both Clique and DomSet admit no nontrivial
FPTapproximation algorithm, i.e., there is no
$o(\text{OPT})$FPTapproximation algorithm for Clique and no
$f(\text{OPT})$FPTapproximation algorithm for DomSet, for any function $f$
(e.g., this holds even if $f$ is the Ackermann function). In fact, our results
imply something even stronger: The best way to solve Clique and DomSet, even
approximately, is to essentially enumerate all possibilities. Our results hold
under the Gap Exponential Time Hypothesis (GapETH) [Dinur16, MR16], which
states that no $2^{o(n)}$time algorithm can distinguish between a satisfiable
3SAT formula and one which is not even $(1  \epsilon)$satisfiable for some
constant $\epsilon > 0$.
Besides Clique and DomSet, we also rule out nontrivial FPTapproximation for
Maximum Balanced Biclique, Maximum Subgraphs with Hereditary Properties, and
Maximum Induced Matching in bipartite graphs. Additionally, we rule out
$k^{o(1)}$FPTapproximation algorithm for Densest $k$Subgraph although this
ratio does not yet match the trivial $O(k)$approximation algorithm.

The problem of dividing resources fairly occurs in many practical situations
and is therefore an important topic of study in economics. In this paper, we
investigate envyfree divisions in the setting where there are multiple players
in each interested party. While all players in a party share the same set of
resources, each player has her own preferences. Under additive valuations drawn
randomly from probability distributions, we show that when all groups contain
an equal number of players, a welfaremaximizing allocation is likely to be
envyfree if the number of items exceeds the total number of players by a
logarithmic factor. On the other hand, an envyfree allocation is unlikely to
exist if the number of items is less than the total number of players. In
addition, we show that a simple truthful mechanism, namely the random
assignment mechanism, yields an allocation that satisfies the weaker notion of
approximate envyfreeness with high probability.

We study the complexity of computing the VC Dimension and Littlestone's
Dimension. Given an explicit description of a finite universe and a concept
class (a binary matrix whose $(x,C)$th entry is $1$ iff element $x$ belongs to
concept $C$), both can be computed exactly in quasipolynomial time ($n^{O(\log
n)}$). Assuming the randomized Exponential Time Hypothesis (ETH), we prove
nearly matching lower bounds on the running time, that hold even for
approximation algorithms.

The Small Set Expansion Hypothesis (SSEH) is a conjecture which roughly
states that it is NPhard to distinguish between a graph with a small subset of
vertices whose edge expansion is almost zero and one in which all small subsets
of vertices have expansion almost one. In this work, we prove inapproximability
results for the following graph problems based on this hypothesis:
 Maximum Edge Biclique (MEB): given a bipartite graph $G$, find a complete
bipartite subgraph of $G$ with maximum number of edges.
 Maximum Balanced Biclique (MBB): given a bipartite graph $G$, find a
balanced complete bipartite subgraph of $G$ with maximum number of vertices.
 Minimum $k$Cut: given a weighted graph $G$, find a set of edges with
minimum total weight whose removal partitions $G$ into $k$ connected
components.
 Densest AtLeast$k$Subgraph (DAL$k$S): given a weighted graph $G$, find a
set $S$ of at least $k$ vertices such that the induced subgraph on $S$ has
maximum density (the ratio between the total weight of edges and the number of
vertices).
We show that, assuming SSEH and NP $\nsubseteq$ BPP, no polynomial time
algorithm gives $n^{1  \varepsilon}$approximation for MEB or MBB for every
constant $\varepsilon > 0$. Moreover, assuming SSEH, we show that it is NPhard
to approximate Minimum $k$Cut and DAL$k$S to within $(2  \varepsilon)$ factor
of the optimum for every constant $\varepsilon > 0$.
The ratios in our results are essentially tight since trivial algorithms give
$n$approximation to both MEB and MBB and efficient $2$approximation
algorithms are known for Minimum $k$Cut [SV95] and DAL$k$S [And07, KS09].
Our first result is proved by combining a technique developed by Raghavendra
et al. [RST12] to avoid locality of gadget reductions with a generalization of
Bansal and Khot's long code test [BK09] whereas our second result is shown via
elementary reductions.

In the Densest $k$Subgraph problem, given an undirected graph $G$ and an
integer $k$, the goal is to find a subgraph of $G$ on $k$ vertices that
contains maximum number of edges. Even though the stateoftheart algorithm
for the problem achieves only $O(n^{1/4 + \varepsilon})$ approximation ratio
(Bhaskara et al., 2010), previous attempts at proving hardness of
approximation, including those under average case assumptions, fail to achieve
a polynomial ratio; the best ratios ruled out under any worst case assumption
and any average case assumption are only any constant (Raghavendra and Steurer,
2010) and $2^{\Omega(\log^{2/3} n)}$ (Alon et al., 2011) respectively.
In this work, we show, assuming the exponential time hypothesis (ETH), that
there is no polynomialtime algorithm that approximates Densest $k$Subgraph to
within $n^{1/(\log \log n)^c}$ factor of the optimum, where $c > 0$ is a
universal constant independent of $n$. In addition, our result has "perfect
completeness", meaning that we prove that it is ETHhard to even distinguish
between the case in which $G$ contains a $k$clique and the case in which every
induced $k$subgraph of $G$ has density at most $1/n^{1/(\log \log n)^c}$ in
polynomial time.
Moreover, if we make a stronger assumption that there is some constant
$\varepsilon > 0$ such that no subexponentialtime algorithm can distinguish
between a satisfiable 3SAT formula and one which is only $(1 
\varepsilon)$satisfiable (also known as GapETH), then the ratio above can be
improved to $n^{f(n)}$ for any function $f$ whose limit is zero as $n$ goes to
infinity (i.e. $f \in o(1)$).

We prove the computational intractability of rotating and placing $n$ square
tiles into a $1 \times n$ array such that adjacent tiles are compatibleeither
equal edge colors, as in edgematching puzzles, or matching tab/pocket shapes,
as in jigsaw puzzles. Beyond basic NPhardness, we prove that it is NPhard
even to approximately maximize the number of placed tiles (allowing blanks),
while satisfying the compatibility constraint between nonblank tiles, within a
factor of 0.9999999851. (On the other hand, there is an easy $1 \over
2$approximation.) This is the first (correct) proof of inapproximability for
edgematching and jigsaw puzzles. Along the way, we prove NPhardness of
distinguishing, for a directed graph on $n$ nodes, between having a Hamiltonian
path (length $n1$) and having at most $0.999999284 (n1)$ edges that form a
vertexdisjoint union of paths. We use this gap hardness and gappreserving
reductions to establish similar gap hardness for $1 \times n$ jigsaw and
edgematching puzzles.

We construct an improved integrality gap instance for the
CalinescuKarloffRabani LP relaxation of the Multiway Cut problem. In
particular, for $k \geqslant 3$ terminals, our instance has an integrality
ratio of $6 / (5 + \frac{1}{k  1})  \varepsilon$, for every constant
$\varepsilon > 0$. For every $k \geqslant 4$, our result improves upon a
longstanding lower bound of $8 / (7 + \frac{1}{k  1})$ by Freund and Karloff
(2000). Due to Manokaran et al.'s result (2008), our integrality gap also
implies Unique Games hardness of approximating Multiway Cut of the same ratio.

A $(k \times l)$birthday repetition $\mathcal{G}^{k \times l}$ of a
twoprover game $\mathcal{G}$ is a game in which the two provers are sent
random sets of questions from $\mathcal{G}$ of sizes $k$ and $l$ respectively.
These two sets are sampled independently uniformly among all sets of questions
of those particular sizes. We prove the following birthday repetition theorem:
when $\mathcal{G}$ satisfies some mild conditions, $val(\mathcal{G}^{k \times
l})$ decreases exponentially in $\Omega(kl/n)$ where $n$ is the total number of
questions. Our result positively resolves an open question posted by Aaronson,
Impagliazzo and Moshkovitz (CCC 2014).
As an application of our birthday repetition theorem, we obtain new
finegrained hardness of approximation results for dense CSPs. Specifically, we
establish a tight tradeoff between running time and approximation ratio for
dense CSPs by showing conditional lower bounds, integrality gaps and
approximation algorithms. In particular, for any sufficiently large $i$ and for
every $k \geq 2$, we show the following results:
 We exhibit an $O(q^{1/i})$approximation algorithm for dense Max $k$CSPs
with alphabet size $q$ via $O_k(i)$level of SheraliAdams relaxation.
 Through our birthday repetition theorem, we obtain an integrality gap of
$q^{1/i}$ for $\tilde\Omega_k(i)$level Lasserre relaxation for fullydense Max
$k$CSP.
 Assuming that there is a constant $\epsilon > 0$ such that Max 3SAT cannot
be approximated to within $(1\epsilon)$ of the optimal in subexponential
time, our birthday repetition theorem implies that any algorithm that
approximates fullydense Max $k$CSP to within a $q^{1/i}$ factor takes
$(nq)^{\tilde \Omega_k(i)}$ time, almost tightly matching the algorithmic
result based on SheraliAdams relaxation.

We prove that it is NPhard to dissect one simple orthogonal polygon into
another using a given number of pieces, as is approximating the fewest pieces
to within a factor of $1+1/1080\varepsilon$.

In this paper, we prove an almostoptimal hardness for Max $k$CSP$_R$ based
on Khot's Unique Games Conjecture (UGC). In Max $k$CSP$_R$, we are given a set
of predicates each of which depends on exactly $k$ variables. Each variable can
take any value from $1, 2, \dots, R$. The goal is to find an assignment to
variables that maximizes the number of satisfied predicates.
Assuming the Unique Games Conjecture, we show that it is NPhard to
approximate Max $k$CSP$_R$ to within factor $2^{O(k \log k)}(\log
R)^{k/2}/R^{k  1}$ for any $k, R$. To the best of our knowledge, this result
improves on all the known hardness of approximation results when $3 \leq k =
o(\log R/\log \log R)$. In this case, the previous best hardness result was
NPhardness of approximating within a factor $O(k/R^{k2})$ by Chan. When $k =
2$, our result matches the best known UGChardness result of Khot, Kindler,
Mossel and O'Donnell.
In addition, by extending an algorithm for Max 2CSP$_R$ by Kindler, Kolla
and Trevisan, we provide an $\Omega(\log R/R^{k  1})$approximation algorithm
for Max $k$CSP$_R$. This algorithm implies that our inapproximability result
is tight up to a factor of $2^{O(k \log k)}(\log R)^{k/2  1}$. In comparison,
when $3 \leq k$ is a constant, the previously known gap was $O(R)$, which is
significantly larger than our gap of $O(\text{polylog } R)$.
Finally, we show that we can replace the Unique Games Conjecture assumption
with Khot's $d$to1 Conjecture and still get asymptotically the same hardness
of approximation.

The projection games (aka LabelCover) problem is of great importance to the
field of approximation algorithms, since most of the NPhardness of
approximation results we know today are reductions from LabelCover. In this
paper we design several approximation algorithms for projection games: 1. A
polynomialtime approximation algorithm that improves on the previous best
approximation by Charikar, Hajiaghayi and Karloff. 2. A subexponential time
algorithm with much tighter approximation for the case of smooth projection
games. 3. A polynomialtime approximation scheme (PTAS) for projection games on
planar graphs and a tight running time lower bound for such approximation
schemes.

In this paper, we present a polynomialtime algorithm that approximates
sufficiently highvalue Max 2CSPs on sufficiently dense graphs to within
$O(N^{\varepsilon})$ approximation ratio for any constant $\varepsilon > 0$.
Using this algorithm, we also achieve similar results for free games,
projection games on sufficiently dense random graphs, and the Densest
$k$Subgraph problem with sufficiently dense optimal solution. Note, however,
that algorithms with similar guarantees to the last algorithm were in fact
discovered prior to our work by Feige et al. and Suzuki and Tokuyama.
In addition, our idea for the above algorithms yields the following
byproduct: a quasipolynomial time approximation scheme (QPTAS) for
satisfiable dense Max 2CSPs with better running time than the known
algorithms.